Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles

Postby Luke » Sat Apr 18, 2009 12:35 am

Thanks everyone for your insights and information. I think I understand exactly what you're saying in regards to the ALS/NL issue. I'm striking 3 and 4 from my list as lacking perspective.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Sat Apr 18, 2009 2:54 am

Luke451,

Don't be too quick to strike away! Our favorite 6 cells (r179c4 and r179c5) from an ALS loop perspective:
Code: Select all
do_alschains - reducing r1c2.<45679> by <6> loop type (1) leg[1]
do_alschains - reducing r1c6.<4568> by <6> loop type (1) leg[1]
do_alschains - reducing r1c9.<45689> by <6> loop type (1) leg[1]
do_alschains - reducing r2c6.<234568> by <6> loop type (1) leg[1]
do_alschains - reducing r3c4.<2368> by <6> loop type (1) leg[1]
do_alschains - reducing r3c6.<234568> by <6> loop type (1) leg[1]

do_alschains - reducing r8c5.<23569> by <5> loop type (1) leg[2]

do_alschains - reducing r3c4.<238> by <8> loop type (1) leg[3]

do_alschains - reducing r8c5.<2369> by <2> loop type (2) als[3]
do_alschains - reducing r8c6.<235689> by <2> loop type (2) als[3]
do_alschains - reducing r9c1.<2468> by <2> loop type (2) als[3]
do_alschains - reducing r9c2.<2346> by <2> loop type (2) als[3]
do_alschains - reducing r8c5.<369> by <3> loop type (2) als[3]
do_alschains - reducing r8c6.<35689> by <3> loop type (2) als[3]
do_alschains - reducing r8c5.<69> by <6> loop type (2) als[3]
do_alschains - reducing r8c6.<5689> by <6> loop type (2) als[3]

do_alschains - reducing r5c5.<2369> by <6> base/cover
do_alschains - cover {2r9 68c4 56c5 3b8}

do_alschains - als[4x5/5]-loop r1c4.<n68> -6- r1c5.<n56> -5- b8x1278.<n23568> -8- r1c4.<n68>

I won't attempt to put this into NL notation, but the loop seems decently clear in the ALS chain notation.

The eliminations labeled "loop type (1)" are due to the RCDs on each leg (as identified within the brackets) of the loop.
The eliminations labeled "loop type (2)" are due to each ALS (as identified within the brackets) being collapsed into a LS by the entry/exit RCDs.
The final elimination labeled "base/cover" is our newly discovered elimination beyond the scope of the normal elimination rules, but "caught" by base/cover logic.

I was missing the type (2) eliminations until reading this: http://forum.enjoysudoku.com/viewtopic.php?p=67198#p67198 Thanks, Ron!

So, at least for this ALS dual-linked pair, it can be expressed as a continuous NL with exactly the same 16 + 1 eliminations that result from the dual-linked rules + the same base/cover r5c5<>6 new elimination. Whether this is easier or harder to visualize/locate is highly debatable if not contentious.

My manual skills are sadly insufficient to find these structures in anything but the simplest of forms. That's why I love IBM's '73 ad campaign slogan, "Think of the computer as energy. As mental energy. Power to get things done." That pretty much changed my life. For better or worse remains to be seen. Think Skynet...

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

off topic

Postby StrmCkr » Sat Apr 18, 2009 3:05 am

Think Skynet...

and
watch
the rise of the machines.

:)
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1416
Joined: 05 September 2006

Postby PIsaacson » Sat Apr 18, 2009 5:22 am

ronk wrote: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.
Should ALS1 (or ALS2) be confined to a box-line intersection, U1 (or U2) is a box. "Non-RCC-like" means both RCC1 and RCC2.

I needed some time to review this and I have some questions:

1) Regardless of the sector (U1) containing ALS1, aren't the CECs for each non-RCC-like candidate located in the peers of the combined non-RCC-like candidate's containing sectors? For example, if an NRL candidate is contained in a single cell, then you can examine the peers of the containing row, column and box for potential eliminations.

2) Am I misinterpreting the U1/U2/U3/U4 significance? They are clearly not always single sector covers when searching for eliminations since they depend upon the union of the defining NRL or RL candidates and their intersecting sector peers, rather than the ALS(s) as a whole. I guess this depends on the validity/interpretation of (1).

3) The statement "Should ALS1 (or ALS2)..." confuses me. Why doesn't an ALS in a box-line intersection have the ability to cover both its containing box and line? And even rows/cols outside of the containing line depending on the location(s) of the NRLs or RLs? Again, this seems to depend on the answer to (1).

Only U3 and U4 make sense to me. U1 and U2 vary depending upon the NRL under consideration. Is this somehow implied somewhere? I think I am missing the forest for the trees...

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

Postby aran » Sat Apr 18, 2009 1:42 pm

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

No.
ALS-xz works like this :
{z a b x} {x c d z}
where
x is the RCD for the two ALS
z is a candidate common to both ALS
a b c d are the remaining candidates in the ALS
then any outside z which sees both internal z is eliminated since it generates a contradiction by removing one candidate from one set and two candidates from the other.
Of course that could be written as a chain
z=ax-x=bz
ie either z true in first set or bz true in second set
Hence any z seen by either set is eliminated.
It is better to think in terms of contradiction because that broadens the mind in these circumstances : one sees the fundamental principle : that anything which removes something from both sets is false.
eg if p removes b from first set and c from second set then <p>
That allows strategies to be developed.

Whereas in dual-linked ALS
we have
{a b x y} {x y c d}
where x y are the 2 RCDs and a b c d other candidates.
No talk of z here.
Multiple eliminations are possible :
any outside a which sees a
any outside b which sees b
any outisde c which sees c
any outside d which sees d
any many other possibilities.

No need in this set-up to have the faintest notion of ALS chains looping back or whatever.
It is child's play that any outside a which sees a in the first set is false : because it locks that set which then takes up both RCDs so there is now one too few candidates for the second set.

Dual-linked ALS is therefore a very different ball game and ALS-xz is inappropriate to describe this powerful structure.
Luke451 wrote:2. A "doubly-linked als-xz" carries a much bigger wallop than it's component als-xz's considered separately

It's thoroughbreds and carthorses
Luke451 wrote:3. Every "d-l als-xz" can be written as a continuous nice loop

Yes but it takes two loops to establish the eliminations which oh so simple non nonsense logic does straight away :
take 1 above
abx=y-y=cdx-x=aby-abx
cdx=y-y=aby-y=cdy-cdx
Luke451 wrote:4. The pattern derives its aforementioned wallop from the fact that they are continuous nice loops

I would say that simple logic as explained above is enough and better.
Otherwise nice-loops get there.
Luke451 wrote:5. "RCD" stands for "dual restricted common."

No.
Restricted common digit
ie a digit which cannot appear in both sets (though it may appear in neither)
or put another way : there is a weak link between RCDs
Luke451 wrote:6. "Doubly-linked" and "Dual-linked" mean the same thing

Yes. Au choix.
Luke451 wrote:7. A restricted common can be a pair, no problem

Once you have the weak-link notion firmly in place, all is clear
Luke451 wrote:Are there elims possible beyond the scope of any underlying cont NL?

Yes
but here I must quote myself...
Consider that there cannot be a third RCD.
If there was, those RCDs would have to split 3/0 or 2/1 : either way one of the sets will be short-changed : it will have too few candidates.
So there can be no third RCD.
Therefore anything which would bring about such a situation is false.
Simple when you see it, permanently valid.
Once again, no need to have the foggiest notion about chains, ALS and all the rest.
I gave an example of that in practice above.
Up stood Ronk giving rise to this exchange

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


Had I been stuck for words, I wouldn't have used the elegance v sledgehammer comparison....
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Sat Apr 18, 2009 4:07 pm

PIsaacson wrote:1) Regardless of the sector (U1) containing ALS1, aren't the CECs for each non-RCC-like candidate located in the peers of the combined non-RCC-like candidate's containing sectors? For example, if an NRL candidate is contained in a single cell, then you can examine the peers of the containing row, column and box for potential eliminations.
...
I guess [ed: (2)] depends on the validity/interpretation of (1).
...
Again, [ed: (3)] seems to depend on the answer to (1).

In the context of a doubly-linked ALS xz-rule, I don't recall seeing a non-RCC-like candidate confined to a single cell. If you run across one, please post it here.

Let's take the simpler, but comparable, case of this naked pair.
Code: Select all
 4     7     89    | 89    6     5     | 3      2     1
 6     18    189   | 2     17    3     | 79-8   5     4
 3     5     2     | 149-8 147   14-8  | 79-68 *68   *68
-------------------+-------------------+------------------
 7     18    3     | 5     2     14    | 468    68    9
 5     4     6     | 7     8     9     | 2      1     3
 9     2     18    | 14    3     6     | 48     7     5
-------------------+-------------------+------------------
 8     6     4     | 3     5     2     | 1      9     7
 2     9     7     | 1468  14    148   | 5      3     68
 1     3     5     | 68    9     7     | 68     4     2

For the <68> naked pair in r3c89, do you view the eliminations r3c467<>68 and r23c7<>68 as due to one step, or two steps? If your answer is "one", even though two cover sets 68r3 and 68b3 are required, then we're probably at an impasse.

BTW Angus Johnson's Simple Sudoku treats it as two.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Luke » Sat Apr 18, 2009 4:11 pm

Wow, this is suddenly all crystallizing for me:!:
aran wrote:Whereas in dual-linked ALS
we have
{a b x y} {x y c d}
where x y are the 2 RCDs and a b c d other candidates.
No talk of z here.
Multiple eliminations are possible :
any outside a which sees a
any outside b which sees b
any outside c which sees c
any outside d which sees d
any many other possibilities.
Including any outside x or y that can see both x's or both y's?

aran wrote:No need in this set-up to have the faintest notion of ALS chains looping back or whatever.
Claro que si.

....any outside a which sees a in the first set is false : because it locks that set which then takes up both RCDs so there is now one too few candidates for the second set.
Yes. Any digit removed from an ALS locks the set. Having two sets with two RCD's severely limits what can go on around the two sets. That's from where the power comes.:idea:

I've got some work to do now. For anyone else in my boat, I would suggest taking this information and applying it to ronk's opening example in this thread.

It is child's play...

Wanna ride bikes?
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby hobiwan » Sat Apr 18, 2009 4:55 pm

ronk wrote:Let's take the simpler, but comparable, case of this naked pair.
Code: Select all
 4     7     89    | 89    6     5     | 3      2     1
 6     18    189   | 2     17    3     | 79-8   5     4
 3     5     2     | 149-8 147   14-8  | 79-68 *68   *68
-------------------+-------------------+------------------
 7     18    3     | 5     2     14    | 468    68    9
 5     4     6     | 7     8     9     | 2      1     3
 9     2     18    | 14    3     6     | 48     7     5
-------------------+-------------------+------------------
 8     6     4     | 3     5     2     | 1      9     7
 2     9     7     | 1468  14    148   | 5      3     68
 1     3     5     | 68    9     7     | 68     4     2

For the <68> naked pair in r3c89, do you view the eliminations r3c467<>68 and r23c7<>68 as due to one step, or two steps? If your answer is "one", even though two cover sets 68r3 and 68b3 are required, then we're probably at an impasse.

I call it a Locked Pair and treat it as one.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Sat Apr 18, 2009 5:31 pm

aran wrote:Up stood Ronk giving rise to this exchange
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
Had I been stuck for words, I wouldn't have used the elegance v sledgehammer comparison....

As to "up stood", I believe I've a perfect right to stand up and express my opinion, especially on my own thread. Another opinion of mine is ... elimination-by-contradiction is not elegant.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Sat Apr 18, 2009 7:36 pm

ronk wrote:In the context of a doubly-linked ALS xz-rule, I don't recall seeing a non-RCC-like candidate confined to a single cell. If you run across one, please post it here.
I keep forgetting that a doubly-linked ALS xz is a specific form of a dual-linked ALS set. I'll have to write a filter to see if there is such a beast since my ALS engine doesn't currently categorize dual-linked ALSs. Great! More work...
ronk wrote:Let's take the simpler, but comparable, case of this naked pair... Do you view the eliminations ... as due to one step, or two steps?
It depends on the context. The answer is I'm schizoid enough to have coded it both ways. In my simple subset logic, it would find the same 2 cells twice, once in sector r3 and again in sector b3. Each would apply eliminations confined to its sector. But in my distributed disjoint subset logic, it would only find those cells once, and it would apply the eliminations en-masse across both cover sets.
Code: Select all
do_dds - reducing r3c7.<6789> by <6>
do_dds - reducing r2c7.<789> by <8>
do_dds - reducing r3c4.<1489> by <8>
do_dds - reducing r3c6.<148> by <8>
do_dds - reducing r3c7.<789> by <8>
do_dds - dds[1x2] b3.<68> at r3c8.<68> r3c9.<68>
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sat Apr 18, 2009 8:42 pm

hobiwan wrote:I call it a Locked Pair and treat it as one.

OK, so that simplified example, extracted from my lockedpairs.dat file BTW, might be a little too simple.

But, to address my question, is a locked pair step equivalent to two naked pair steps, or one?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Sun Apr 19, 2009 1:58 am

Luke451 wrote:
aran wrote:Whereas in dual-linked ALS
we have
{a b x y} {x y c d}
where x y are the 2 RCDs and a b c d other candidates.
No talk of z here.
Multiple eliminations are possible :
any outside a which sees a
any outside b which sees b
any outside c which sees c
any outside d which sees d
any many other possibilities.
Including any outside x or y that can see both x's or both y's?

Yes indeed
Also note that any non-RCD k in one set can will eliminate any non-RCD k it sees in the other set.
These "inside" eliminations being known as cannibalizing.
aran
 
Posts: 334
Joined: 02 March 2007

Postby aran » Sun Apr 19, 2009 2:30 am

ronk wrote:
aran wrote:Up stood Ronk giving rise to this exchange
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
Had I been stuck for words, I wouldn't have used the elegance v sledgehammer comparison....

As to "up stood", I believe I've a perfect right to stand up and express my opinion, especially on my own thread. Another opinion of mine is ... elimination-by-contradiction is not elegant.

A perfect right which I defend and respect.
I was however astonished by your statement which strikes me as a failure.
Sudoku logic may be Boolean, but reasoning associated with Sudoku must not be.
The idea that an approach is either good or bad, and that contradiction is "bad" is blinkered thinking.
Equating for example the search for a contradiction via a chain from a bivalue with the simple logic behind the third RCD is staggering.
To circumnavigate that simple logic by contradiction which is easy to remember, easy to apply, and which requires no knowledge of any jargon, yes to avoid it because it doesn't fit into your idee fixe by resorting to some als-xz specific to the elimination is just extraordinary.

As you well know virtually any elimination can be presented as a contradiction.
There are those that are first seen in other ways, and there are those first seen as contradictions.
I would have thought that ALS-xz is an example of the latter.

Why do you think there is reference here and there to "cec" (candidate elimination cells) if it is not that contradiction is the prime mover ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Sun Apr 19, 2009 3:52 am

Ron,

Not a single cell example, but it does show that an non-RCC-link candidate can span 2 cover sets (depending upon POV).

From the royle17 36628 collection #7273:
Code: Select all
000200804000900301100000000500306010000040000000008000084635100000700050025000000

+-------------------------+---------------+-------------------------+
| 369   35679    3679     | 2   1567  137 | 8        679   4        |
| 48-2  4567     2678     | 9   5678  47  | 3        267   1        |
| 1     34679    236789   | 48  678   347 | 2579     2679  2579     |
+-------------------------+---------------+-------------------------+
| 5     479      789-2    | 3   279   6   | 2479     1     2789     |
| (28)  13679    13679-28 | 15  4     279 | 25679    (38)  25679-38 |
| (24)  13679-4  13679-2  | 15  279   8   | 25679-4  (34)  25679-3  |
+-------------------------+---------------+-------------------------+
| 79    8        4        | 6   3     5   | 1        279   279      |
| 369   1369     1369     | 7   289   249 | 469      5     3689     |
| 3679  2        5        | 48  189   149 | 4679     48-3  36789    |
+-------------------------+---------------+-------------------------+


From one perspective: ALS A r56c1 {248} -48- ALS B r56c8 {348}

The NRL {2} in ALS A eliminates r456c3<>2 in cover b4 as well as r2c2<>2 in c1
The NRL {3} in ALS B eliminates r56c9<>3 in cover b6 as well as r9c8<>3 in c8

I don't know if this is a good example because it can be viewed in several alternate ways as an ALS/XY loop, or as r5c18-23-r6c18 or r56c1-48-r56c8 DL ALS-XZs. From the r5c18-23-r6c18 POV, there are no multi-cover NRL eliminations.

I thought it was an interesting little example since it's a really simple 4 cell structure with 11 eliminations. I only have about 900 more DL ALSs to review, looking for that single cell...
Last edited by PIsaacson on Sun Apr 19, 2009 7:05 am, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sun Apr 19, 2009 5:44 am

aran wrote:I was however astonished by your statement which strikes me as a failure.
...
blinkered thinking ... staggering ... extraordinary

aran, nice rant, but take the rants elsewhere.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques