Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles

Postby aran » Thu Apr 16, 2009 2:39 am

ronk wrote:
aran wrote:I don't follow Ronk's point neither there nor here :
Ronk wrote:There are 14 eliminations for this complementary doubly-linked AHS-xz. Since eliminations r6c2<>1 and r49c4<>7 do not exist, I consider these eliminations an "overstatement" for the original ALS-xz.

which could read like a calling into question of those eliminations.

Sort of, I suppose. Some of the eliminations cannot occur simultaneously with rank 0 set logic. Specifically, given r23c234 as the base set, I'm saying rank 0 set logic cannot be constructed with both 1b1 and 1c2 in the cover set. Ditto for 7b2 and 7c4.

I entirely agree with that last statement, but that doesn't tie to the earlier one (or I don't see how).
There are two rank 0 structures in relation to r23c234 :
1c2 4r3 6r2 8b1 7b1 7c4
1c2 4r3 6r2 8b1 7r2 7r3
ie all that varies is the cover for the 7s
From the first 17 eliminations.
From the second the additional <7> r3c9.
<1>r6c2 follows directly whichever cover set is chosen.
<7>r49c4 requires the first cover set.
aran
 
Posts: 334
Joined: 02 March 2007

Postby hobiwan » Thu Apr 16, 2009 8:50 am

ronk wrote:However, I do expect posters and programmers who claim to be using the ALS-xz to use N cover sets for N base sets, not N+1 cover sets, not N+2 cover sets, etc. (stated as an over-simplification of superposition.)

So what exactly are the consequences of this? For hobiwan's ALS xz above, I would probably select 1b1 and 7b2 to be cover set members, because they have more eliminations than cover sets 1c2 and 7c4, respectively. This merely leaves 1b1\c2 and 7b2\c4 as eliminations for the simpler locked candidates technique.

I seem to be the last one here, who doesn't speak sudoku set logic fluently:D , so I can't say anything to those arguments. But I still think that techniques described here should be understandable without a background in math.

That said, I can follow your first argument (only 1b1, instead of 1b1 and 1c2). You made that point twice in the last time (once with continuous nice loops, once with SDCs), and it does make the techniques easier.

But I can't follow you on the second case (only 7b2 instead of 7b2 and 7c4). Just image how a tutorial style description of that argument would look like:
All candidates that are not RCDs can be eliminated from all cells, that see all ALS cells. If, however, the ALS happen to be locked in two houses instead of only one, you may only eliminate candidates from one of those houses (pick the house that provides the most eliminations).

I think "counterintuitive" sums it up nicely:D
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Thu Apr 16, 2009 1:22 pm

hobiwan wrote:But I can't follow you on the second case (only 7b2 instead of 7b2 and 7c4). Just image how a tutorial style description of that argument would look like:
All candidates that are not RCDs can be eliminated from all cells, that see all ALS cells. If, however, the ALS happen to be locked in two houses instead of only one, you may only eliminate candidates from one of those houses (pick the house that provides the most eliminations).

I think "counterintuitive" sums it up nicely:D

OK, my "most eliminations" point was totally bogus.:( And since you've paraphrased a definition for me, I'm forced to write my own.:)

Doubly-linked ALS xz-rule: When ALS1 in unit U1 (row, column, box, sector, house) and ALS2 in U2 are doubly-linked by RCC1 in U3 and RCC2 in U4, except for the candidates of ALS1 and ALS2, the following eliminations are valid:
  • in U1, all non-RCC-like candidates of ALS1,
  • in U2, all non-RCC-like candidates of ALS2.
  • in U3, all RCC1-like candidates, and
  • in U4, all RCC2-like candidates.
"Non-RCC-like" means both RCC1 and RCC2.


aran wrote:
ronk wrote:Specifically, given r23c234 as the base set, I'm saying rank 0 set logic cannot be constructed with both 1b1 and 1c2 in the cover set. Ditto for 7b2 and 7c4.

I entirely agree with that last statement, but that doesn't tie to the earlier one (or I don't see how).

I've made several earlier statements; I'm certainly not going to guess which one.

aran wrote:There are two rank 0 structures in relation to r23c234 :
1c2 4r3 6r2 8b1 7b1 7c4
1c2 4r3 6r2 8b1 7r2 7r3
ie all that varies is the cover for the 7s
From the first 17 eliminations.
...

Huh? Without 1b1 and 7b2, you've lost r1c1<>1 and r1c56<>7.

[edit: deleted the sentence "Should ALS1 (or ALS2) be confined to a box-line intersection, U1 (or U2) is a box."]
Last edited by ronk on Tue Apr 21, 2009 9:32 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Thu Apr 16, 2009 3:27 pm

ronk wrote:
aran wrote:There are two rank 0 structures in relation to r23c234 :
1c2 4r3 6r2 8b1 7b1 7c4
1c2 4r3 6r2 8b1 7r2 7r3
ie all that varies is the cover for the 7s
From the first 17 eliminations.
...

Huh? Without 1b1 and 7b2, you've lost r1c1<>1 and r1c56<>7.

You're right. I was a bit sloppy there.
I'd better explain that I look on Dual-Linked ALSs from a purely logical point of view and write them down like this (using the current example}
{17846} {467} with the RCDs in bold. Then on logic alone
(using candidiate 1 as an example) ; any candidate 1 which sees 1 in the first set must be and is eliminated ie <1> r12c1+r6c2.
What you are highlighting is that using a base set/cover set approach, it may take a number of different covers to achieve the same conclusion eg here having first c2, then b1 as the cover for 1.
Valid point and interesting as is the fact the logic alone as described above is simpler and more effective.
PS the above doesn't catch <7>r3c9 directly, although it could be reasoned like this :
r3c9=7=>7 now becomes a third RCD (as 7r3c23 would disappear) : impossible since the second set can only have 2 placements=><7>r3c9.
aran
 
Posts: 334
Joined: 02 March 2007

Postby hobiwan » Thu Apr 16, 2009 5:06 pm

ronk wrote:And since you've paraphrased a definition for me, I'm forced to write my own.:)

Nice definition, although I still think the restriction to boxes is neither necessary nor intuitive (I do understand where it comes from).

Since this is your thread, I will try not to post anything here that doesn't comply to your definition, but I won't change my solver's code.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby aran » Thu Apr 16, 2009 8:18 pm

Further to an earlier observation
aran wrote:PS the above doesn't catch <7>r3c9 directly, although it could be reasoned like this :
r3c9=7=>7 now becomes a third RCD (as 7r3c23 would disappear) : impossible since the second set can only have 2 placements=><7>r3c9

in fact there is a general logical point : anything which would create a third RCD is false (at least two RCDs would then be in one of the sets)
This can then be used as a simple rule for possible further eliminations
eg in this from Hobiwan
hobiwan wrote:
Code: Select all
.-----------------------.-------------------------------.-------------------------.
|  3      45-679  2     | A68      A56         45-68    | 4578    1       45-689  |
|  1      456     468   |  9        7          2345-68  | 23458   34568   234568  |
|  4678   45679   46789 |  23-6-8   1          2345-68  | 234578  345689  2345689 |
:-----------------------+-------------------------------+-------------------------:
|  5      23479   3479  |  1        8          239      | 6       349     2349    |
|  246    23469   1     |  5        2369       2369     | 2348    7       23489   |
|  26     8       369   |  7        4          2369     | 1       359     2359    |
:-----------------------+-------------------------------+-------------------------:
|  9      346     3468  | B368     B356        1        | 3458    2       7       |
|  2678   1       3678  |  4       -2-3-5-69  -2-35-689 | 358     3568    3568    |
| -2468  -2346    5     | B2368    B236        7        | 9       3468    1       |
'-----------------------'-------------------------------'-------------------------'

Almost Locked Set XZ-Rule: A=r1c45 - {568}, B=r7c45,r9c45 - {23568}, X=5,8, Z=5,8 => r8c56,r9c12<>2, r8c56<>3, r8c5<>5, r1c269,r238c6,r3c4,r8c5<>6, r3c4<>8

we can immediately conclude <6> r5c5 since if true it creates a third RCD 6 (between 6r1c4 set A and 6r79c4 set B)
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Thu Apr 16, 2009 10:25 pm

aran wrote:in fact there is a general logical point : anything which would create a third RCD is false (at least two RCDs would then be in one of the sets)

That looks like elimination-by-contradiction to me, so I'd rather apply the doubly-linked ALS xz-rule with als:r179c4 and als:r179c5.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Thu Apr 16, 2009 11:04 pm

ronk wrote:
aran wrote:in fact there is a general logical point : anything which would create a third RCD is false (at least two RCDs would then be in one of the sets)

That looks like elimination-by-contradiction to me, so I'd rather apply the doubly-linked ALS xz-rule with als:r179c4 and als:r179c5.

And so what ?
Simple elegance v sledgehammer
aran
 
Posts: 334
Joined: 02 March 2007

Postby Luke » Fri Apr 17, 2009 3:50 am

Mind if I interlope? I hate to always dumb things down, but if there's a break in the action, I have some questions about the basics. Then maybe I'll be able to get a clue as to what in Helsinki y'all are talking about.:)

Here's a list of statements based what I've garnered. True, false, or grey?

1. A "doubly-linked als-xz" is simply an als-xz with not one X, but two (X being a restricted common.)

2. A "doubly-linked als-xz" carries a much bigger wallop than it's component als-xz's considered separately.

3. Every "d-l als-xz" can be written as a continuous nice loop.

4. The pattern derives its aforementioned wallop from the fact that they are continuous nice loops.

5. "RCD" stands for "dual restricted common."

6. "Doubly-linked" and "Dual-linked" mean the same thing.

7. A restricted common can be a pair, no problem.

8. There's no such thing as a dumb question, but there certainly are a lot of inquisitive idiots.


Are there elims possible beyond the scope of any underlying cont NL?

Exactly what words would one use to describe the meaning of the "pipe" (|) symbol?.... say, in usages such as (ALS:r9c3=7|1=r8c3) or (r45c9,r9c9=5|37|9=r45c9.) I have my own answer, but I'd rather hear yours.

Thanks to anyone so kind as to address any of this.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Fri Apr 17, 2009 12:15 pm

Luke451,

I'll take a stab, but there will probably be disagreement, so be prepared for a variety of answers:

1) Yes, but... I'm of the opinion that dual-linked ALSs are a unique category. An ALS-xz that has 2 RCDs is simply one method of forming a dual-linked ALS.

2) Yes, usually... As the solution progresses, it often happens that a dual-linked ALS discovered "late" may not produce many eliminations, if indeed any.

3) Uncertain, but I suspect the answer is "Yes" simply because I believe you can express almost any logical sudoku structure as an NL.

4) Possibly, but I wouldn't put it in those terms. Being a recent convert to Allan Barker's set/link-set logic, I would now say that its "wallop" comes from it being a rank-0 structure with multiple cover sets that provide many eliminations. The exact explanation should come from the experts in this area.

5) RCD - Restricted Common Digit another TLA

6) Yes

7) I would agree except for the "no problem". As I have recently discovered (or re-discovered), two ALSs may be dual-linked by a variety of techniques. Direct line-of-sight for an RCD is just one method. You can use anything that provides a strong link to "bridge" the RCDs such as bi-value cells, bi-local cells, X-cycles, ERs, AURs, ALS chains, NL segments...

8) I resemble that remark...

9) Are there eliminations... Yes!!! That's why I'm striving to understand Allan's set/link-set logic!!! I think of it in these terms: Use standard sudoku techniques (such as finding dual-linked ALSs) to find a base set. Then apply base/cover logic to find additional potential eliminations beyond the scope of the base set discovery technique.

10) I'm not versed in NL notation, so I'll leave the formal definition of the '|' symbol to the experts.

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Fri Apr 17, 2009 12:30 pm

ronk wrote:
aran wrote:in fact there is a general logical point : anything which would create a third RCD is false (at least two RCDs would then be in one of the sets)

That looks like elimination-by-contradiction to me, so I'd rather apply the doubly-linked ALS xz-rule with als:r179c4 and als:r179c5.

Interestingly, if these same 6 cells are described as the dual-linked als r179c4 -23- r179c5, then the standard elimination rules only account for the following 11 eliminations and it requires 2 additional cover sets to produce the other 6 missing eliminations:
Code: Select all
do_alschains - reducing r8c5.<23569> by <2> dual
do_alschains - reducing r8c6.<235689> by <2> dual
do_alschains - reducing r9c1.<2468> by <2> dual
do_alschains - reducing r9c2.<2346> by <2> dual
do_alschains - reducing r8c5.<3569> by <3> dual
do_alschains - reducing r8c6.<35689> by <3> dual
do_alschains - reducing r8c5.<569> by <5> dual
do_alschains - reducing r3c4.<2368> by <6> dual
do_alschains - reducing r5c5.<2369> by <6> dual
do_alschains - reducing r8c5.<69> by <6> dual
do_alschains - reducing r3c4.<238> by <8> dual

do_alschains - reducing r1c2.<45679> by <6> base/cover
do_alschains - reducing r1c6.<4568> by <6> base/cover
do_alschains - reducing r1c9.<45689> by <6> base/cover
do_alschains - reducing r8c6.<5689> by <6> base/cover
do_alschains - cover {6r1 2r9 8c4 5c5 36b8}

do_alschains - reducing r2c6.<234568> by <6> base/cover
do_alschains - reducing r3c6.<234568> by <6> base/cover
do_alschains - cover {2r9 8c4 5c5 6b2 36b8}

do_alschains - als[2x4/5] r179c4.<n2368> -23- r179c5.<n2356>

Also interesting is the fact that you can add cell r8c5 to the 2nd ALS in either POV and obtain two additional eliminations:
Code: Select all
do_alschains - reducing r5c5.<239> by <9> dual
do_alschains - reducing r8c6.<589> by <9> dual

do_alschains - als[2x5/6] r179c4.<n2368> -23- r1789c5.<n23569>
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Fri Apr 17, 2009 4:23 pm

PIsaacson wrote:Also interesting is the fact that you can add cell r8c5 to the 2nd ALS in either POV and obtain two additional eliminations:
Code: Select all
do_alschains - reducing r5c5.<239> by <9> dual
do_alschains - reducing r8c6.<589> by <9> dual

do_alschains - als[2x5/6] r179c4.<n2368> -23- r1789c5.<n23569>

You are including the consequences of consequences of a minimal doubly-linked ALS xz-rule -- by using a non-minimal.

As a consequence of "either POV", we have the naked single r8c5=9. As a consequence of the naked single, we have the so-called eliminations r5c5<>9 and r8c6<>9. We don't normally list the "eliminations" of singles.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Fri Apr 17, 2009 7:26 pm

Luke451,

ad 4:

I prefer looking at Doubly Linked ALS-XZ differently than as Nice Loops. If two ALS are linked via an RCD, one of the ALS turns into a locked set (but we don't know which). If they are doubly linked, however, one of the RCDs has to be exclusively in ALS 1 and the other in ALS 2. Although we still don't know, which RCD will be in which ALS, we do know for certain, that in both ALSs all candidates except the RCDs are locked into the ALS cells (and that is what usually causes the wallop).

The same is true for an ALS link in a Continuous Nice Loop, so nothing wrong with your approach, I just think the above is more intuitive (personal opinion).

ad 1:

Yes and no. As somebody (PIsaacson?) has pointed out before, the main difference between a Standard ALS-XZ and a Doubly Linked ALS-XZ, is that the latter doesn't need a Z (and that is a rather large difference IMO).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby PIsaacson » Fri Apr 17, 2009 8:41 pm

ronk wrote:You are including the consequences of consequences of a minimal doubly-linked ALS xz-rule -- by using a non-minimal... We don't normally list the "eliminations" of singles.
Ron,

I was running my ALS engine in a mode that treats each discovered ALS as if it were the first one encountered -- so there were no accumulative or prior considered eliminations. As such, the following ALS chain reports (in full):
Code: Select all
do_alschains - reducing r8c6.<235689> by <2> dual
do_alschains - reducing r8c6.<35689> by <3> dual
do_alschains - reducing r3c4.<2368> by <6> dual
do_alschains - reducing r5c5.<2369> by <6> dual
do_alschains - reducing r3c4.<238> by <8> dual
do_alschains - reducing r5c5.<239> by <9> dual
do_alschains - reducing r8c6.<5689> by <9> dual

do_alschains - reducing r1c2.<45679> by <6> base/cover
do_alschains - reducing r1c6.<4568> by <6> base/cover
do_alschains - reducing r1c9.<45689> by <6> base/cover
do_alschains - reducing r8c6.<568> by <6> base/cover
do_alschains - cover {6r1 9r8 8c4 5c5 236b8}

do_alschains - reducing r2c6.<234568> by <6> base/cover
do_alschains - reducing r3c6.<234568> by <6> base/cover
do_alschains - cover {9r8 8c4 5c5 6b2 236b8}

do_alschains - als[2x5/6] r179c4.<n2368> -23- r1789c5.<n23569>

The eliminations that would have resulted in assigning r8c5=9 from the smaller r179c4 -23- r179c5 ALS set are not present in the larger r179c4 -23- r1789c5 ALS as defined by the current ALS dual-linked elimination rules. Those flagged as "base/cover" are also not defined by current ALS eliminations rules, but are discovered by 2 different cover sets. So in this case, more is less.

This illustrates something that I've been working on for my base/cover logic. Namely, that it is sometimes beneficial to not just locate all the possible cover sets for a given base set, but to also rotate through all the possible combinations of that base set. I have this working in some test code, but it's really slooooow compared to just finding all the exact cover solutions for a single base set. But then, sometimes less is more...

In any case, neither my ALS nor my base/cover code currently check for naked/hidden singles resulting from eliminations. I defer that to lower level logic. Otherwise, it would have discovered for the r179c4 -23- r179c5 DL ALS that r8c1=2, r6c1=6, r5c1=4, r9c1=8, r3c1=7... with cascading NSs/HSs until the puzzle was completely solved. But I am thinking of including logic to test the base set and cover sets for possible assignments to more closely emulate Xsudo.

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby DonM » Fri Apr 17, 2009 9:36 pm

hobiwan wrote:Luke451,

ad 4:

I prefer looking at Doubly Linked ALS-XZ differently than as Nice Loops. If two ALS are linked via an RCD, one of the ALS turns into a locked set (but we don't know which). If they are doubly linked, however, one of the RCDs has to be exclusively in ALS 1 and the other in ALS 2. Although we still don't know, which RCD will be in which ALS, we do know for certain, that in both ALSs all candidates except the RCDs are locked into the ALS cells (and that is what usually causes the wallop).

The same is true for an ALS link in a Continuous Nice Loop, so nothing wrong with your approach, I just think the above is more intuitive (personal opinion).


My personal opinion also. One of the reasons I promote ALS Chains is because I think that more people are able to advance beyond the early stages of solving by pure pattern solving (Pattern A solving as I call it) than by understanding all the complexities of the underlying logic (hopefully that would come later) that is involved in finding nice loops (Pattern B solving). Likewise, I think a lot of people with limited solving skills can eventually pick out even a basic doubly-linked ALS, long before they can find the comparable nice loop. I still enjoy finding the former as a relaxing exercise. Finding the comparable nice loop isn't so relaxing... for me:)
DonM
2013 Supporter
 
Posts: 487
Joined: 13 January 2008

PreviousNext

Return to Advanced solving techniques