ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

Postby StrmCkr » Tue Feb 17, 2009 9:37 am

I'll be surprised if that's due to anything other than coincidence.

not a coincedence.

if the engine is based off of the work of whom paul lists.

some things are more complicated
or an alternative view on the same things.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby ronk » Tue Feb 17, 2009 10:30 am

ronk wrote:
PIsaacson wrote:
daj95376 wrote:It seems to me, after examining your first two examples, that you also have an alternate way of finding XY-Loops.

I like it! Even though the XY-loops involve other cells, it accounts for the reductions. Yikes, now I need to see if all the other cases can be subsumed by XY-loops/chains.

I'll be surprised if that's due to anything other than coincidence.

StrmCkr wrote:not a coincedence.

if the engine is based off of the work of whom paul lists.

some things are more complicated
or an alternative view on the same things.

PIsaacson has since posted three more examples with the same type of doubly-linked overlapping ALS chains here and here. Can you show us the continuous xy-chain that produces the same eliminations for even one of those examples:?:
Last edited by ronk on Tue Feb 17, 2009 6:55 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby StrmCkr » Tue Feb 17, 2009 10:53 am

some of pauls work is creating intresting affects.

only a few of them are comming up as altreantives.
and they have been listed out already.

im mearly remakring on somethign entirly offtopic.
and im not going to stray that way again.

:)

im still analizing what paul is doing.
cant comment too much either till i understant entirely what he is accomplishing.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby PIsaacson » Tue Feb 17, 2009 11:07 am

Regarding ALS XY-rings or continuous loops:

I have modified the code to allow full continuous loops for any sized ALS chain. For instance, the new code can act as an XY-chain engine by using:

sudoku -bv -A2 -B10 <puzzle>

This restricts the ALSs to bi-value cells and attempts to chain them using the normal ALS RCD rules. I had to eliminate a check that prevented ALSs from belonging to the same house/sector, but after that, this works fine as an XY-chain finder. I also reworked the code the checks for and skipped chains looping back to the origin ALS. Now it detects them and reports them as:

als[sxn/m]-loop and flags the eliminations with the loop keyword.

I have run numerous tests now using larger puzzle sets (but beware the run times if you ask for large ALS sizes and long chains), and it seems legal to have any sized/overlapped ALSs constructing a ring/loop. The eliminations are CEC peers of the RCDs for each leg of the ring/loop. This allows finding such things as overlapping/cannibalistic loops and they do indeed exist. I'll upload the new code/executables tonight, so feel free to experiment yet again. Try this:

sudoku -bv -A4 -B4 royle17.txt > log
grep "als+c.*loop" log

You should find 109 overlapping cannibalistic loops in the log.

Now for the bad news: Loops are not necessary since the prior version of the code found all the equivalent ALS chains in the loop as if it were "sliced" along each leg. There are no new reductions found, the loops just "bundle" them into one convenient spot at the 1st instance of loop discovery. I'm leaving the loop detection code in for now since it's rather interesting to see XY-rings/loops extended to full ALS-rings/loops. BYW, what is the formal name for such things?
Last edited by PIsaacson on Tue Feb 17, 2009 7:12 am, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Tue Feb 17, 2009 11:10 am

StrmCkr wrote:im still analizing what paul is doing.
cant comment too much either till i understant entirely what he is accomplishing.

Too bad you didn't think of that before you challenged my statement.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby StrmCkr » Tue Feb 17, 2009 11:24 am

the remark was not for you personally ronk

was about something offhand.
regarding just a radom curiosity i noticed.

and perhaps i should have worded it better or not at all:)

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

Postby PIsaacson » Tue Feb 17, 2009 11:41 am

Gentlemen (and ladies if present),

I need serious help in developing rules for bringing AHSs into this picture. My engine produces the paired AHS for each ALS and they are just sitting there begging to come to the party. I use these beasts in nice-loops, but while I found it relatively easy to work out the rules for weak link propagation for an AHS in a nice-loop chain, I can't seem to get my head around how to directly combine:

AHS to ALS
ALS to AHS (probably a symmetrical set of rules to the above)
AHS to AHS

In my nice-loop code, I generate a strong link from an external cell/candidate false to the AHS extraneous candidate true (not part of the N candidate N+1 cell structure) - AHS becomes an LS due to the extraneous candidate true, LS is weak linked to all other extraneous candidates becoming false as well as any peers of the newly formed LS becoming false. What am I missing for using this for ALS/AHS chains??? The only solutions I've come with all involve helper/bridge cells which makes it more like grouped nice-loops. I'm waiting for that "Eureka!" (no pun intended) moment, but it has yet to happen.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby champagne » Tue Feb 17, 2009 3:03 pm

PIsaacson wrote:Gentlemen (and ladies if present),

I need serious help in developing rules for bringing AHSs into this picture. My engine produces the paired AHS for each ALS and they are just sitting there begging to come to the party. I use these beasts in nice-loops, but while I found it relatively easy to work out the rules for weak link propagation for an AHS in a nice-loop chain, I can't seem to get my head around how to directly combine:

AHS to ALS
ALS to AHS (probably a symmetrical set of rules to the above)
AHS to AHS

In my nice-loop code, I generate a strong link from an external cell/candidate false to the AHS extraneous candidate true (not part of the N candidate N+1 cell structure) - AHS becomes an LS due to the extraneous candidate true, LS is weak linked to all other extraneous candidates becoming false as well as any peers of the newly formed LS becoming false. What am I missing for using this for ALS/AHS chains??? The only solutions I've come with all involve helper/bridge cells which makes it more like grouped nice-loops. I'm waiting for that "Eureka!" (no pun intended) moment, but it has yet to happen.


Hi,

I just oveviewed that thread, so I can miss some already written things but I can tell easily how I handle that situation.

1) ALS and HS can always be combined full filling a set (row, column, box).

Consequently, you can always define strong links between 2 conjugated AHS;ALS.

2) I am then focusing on the AHS, defining weak links between the unknown groups. (as between candidates within a cell)

3) I define the SIS as well (choice in my terminology) as for a cell.

This is enough to bring that stuff in the standard processing. (overlapping of AHS does not interfere in that process).

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby PIsaacson » Tue Feb 17, 2009 5:43 pm

Champagne,

Could you please provide a diagram to illustrate your logic? Think of me as a slow, but dedicated, learner...

If I knew nice-loop or Eureka notation better, this would probably be a lot easier to convey, so forgive my strange quasi nice-loop/TM diagram of what I have been experimenting with:

1) some cell Dx false == b/b ==> 2) Dx extra true + AHS (core) --> 3) LS (core+Dx) true == b/b ==> some cell Dx false

Let me describe my thoughts/reasons for this three step process:

1) Assume an external cell contains a candidate Dx that is bi-value/bi-location linked to a Dx non-core candidate of the AHS.
2) This makes the Dx within the AHS true and promotes the AHS to a locked set consisting of the core digits + Dx.
3) The LS will cause b/b linked external cells' Dx candidates to become false.

The b/b requirement is to provide reversibility, which I believe is crucial for ALS chains. It should allow these 3-step encapsulated AHSs to plug into an ALS chain fairly easily. What I don't like is forcing the entry/exit digits to be the same - it seems like a violation of the current RCD adjacency rule. I also don't like that it's a short nice-loop/AIC chain. If we start allowing "bridging" cells to extend/modify links in ALS chains, then we might as well just use them as grouped nice-loops. As I stated previously, I obviously need help.

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

Postby champagne » Tue Feb 17, 2009 6:19 pm

Hi Paul,

I suggest to illustrate the concept thru a well known Nice Loop

Code: Select all
6      289    27e9   |2789   4      15789     |125    129     3     
489    1      2349   |23689  2568   689       |246    7       569   
479    2349   5      |23679  1267   1679      |8      12469   169   
--------------------------------------------------------------------
14789  4689   14679  |5      678    2         |13467  134689  16789 
3      5A68   167    |4c678  9      4678      |1567   168     2     
45789  2d4689 24679  |1      678    3         |467    4689    56789
--------------------------------------------------------------------
145    346    8      |2467   12567  1467      |9      23      167   
149    7      13469  |24689  1268   14689     |23     5       168   
2      569    169    |6789   3      156789    |167    168     4     


Conjugated AC/AHS;ALS
r7c2r8c3 ; r78c1r9c23
r2c3r3c2 ; r1c23r23c1
r2c7r3c8 ; r1c78r23c9


Empty rectangle '6' in box 9

And the Nice loop produced by the solver

Code: Select all
[]6r9c78 - 6r9c23 = AC:r7c2r8c3(6r7c2r8c3 - 4r7c2r8c3) = 4r78c1 - 4r23c1
                  = AC:r2c3r3c2(4r2c3r3c2 - 2r2c3r3c2) = 2r1c23 - 2r1c78
                  = AC:r2c7r3c8(2r2c7r3c8.å - 6r2c7r3c8)
                  = 6r23c9 - 6r78c9

In such a case, Ronk would prefere the shorter form using exclusively "ALS" that I write in that way

Code: Select all
[]6r9c78 - 6r9c23 = || = 4r78c1 - 4r23c1  = || = 2r1c23 - 2r1c78  = ||= 6r23c9 - 6r78c9
                  ALS r78c1r9c23       ALS r1c23r23c1          ALS  r1c78r23c9


But this is not any more reflecting the logic of the solver.

May be starting from that example your can raise more precise questions.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Tue Feb 17, 2009 8:24 pm

PI wrote:... but while I found it relatively easy to work out the rules for weak link propagation for an AHS in a nice-loop chain, I can't seem to get my head around how to directly combine:

AHS to ALS
ALS to AHS (probably a symmetrical set of rules to the above)
AHS to AHS

Hi Paul,

By "directly combine", do you mean:
Linked mixed ALS/AHS in an AXS chain, similar to an ALS chain,
Or multiply linked AHS to ALS,
Or overlapped ALS and AHS similar to Myth's CoALS (CoAXS?).

Or all of the above, ie full integration.

Maybe I can draw some pictures, and would like to see as well.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Tue Feb 17, 2009 10:01 pm

here PIsaacson wrote:ruud_top10000 #2916
[...]
do_alschains - reducing r8c1.<2469> by <2> dual
do_alschains - reducing r8c2.<12569> by <2> dual
do_alschains - reducing r7c1.<2479> by <4> dual
do_alschains - reducing r7c4.<24579> by <4> dual
do_alschains - reducing r8c1.<469> by <4> dual
do_alschains - reducing r7c2.<12579> by <5> dual
do_alschains - reducing r7c4.<2579> by <5> dual
do_alschains - reducing r8c2.<1569> by <5> dual
do_alschains - reducing r7c4.<279> by <9> dual
do_alschains - als+c[2x7/7] b7x378.<2457> +27+ r7c123689.<1234579>

[...]

ruud_top10000 #8192
[...]
do_alschains - graph contains 234 vertices and 1090 edges
do_alschains - reducing r1c8.<123489> by <2> dual
do_alschains - reducing r2c1.<2389> by <2> dual
do_alschains - reducing r2c7.<1239> by <2> dual
do_alschains - reducing r2c8.<12348> by <2> dual
do_alschains - reducing r1c8.<13489> by <3> dual
do_alschains - reducing r1c8.<1489> by <4> dual
do_alschains - reducing r2c8.<1348> by <4> dual
do_alschains - reducing r5c9.<2457> by <4> dual
do_alschains - reducing r2c1.<389> by <8> dual
do_alschains - reducing r1c8.<189> by <9> dual
do_alschains - als+c[2x7/7] b3x367.<2349> +39+ r2c246789.<1234689>

here PIsaacson wrote:Top50000 #35664 after elementary constraint processing
[...]
do_alschains - reducing r3c1.<4579> by <5> dual
do_alschains - reducing r2c2.<23789> by <7> dual
do_alschains - reducing r3c2.<23479> by <7> dual
do_alschains - reducing r5c1.<178> by <8> dual
do_alschains - reducing r1c2.<39> by <9> dual
do_alschains - reducing r2c1.<1789> by <9> dual
do_alschains - reducing r2c2.<2389> by <9> dual
do_alschains - reducing r3c1.<479> by <9> dual
do_alschains - reducing r3c2.<2349> by <9> dual
do_alschains - als+c[2x6/6] b1x169.<1579> +17+ r12368c1.<145789>

Although there are a few inconsequential differences in the eliminations, each of the above has a complementary hidden Sue De Coq (SDC). So that others have a chance to identify these SDCs, I'll delay posting them until the morning of 2/21.

Along with PIsaacson's first two examples here, that's five of five that have complementary hidden SDCs. (The other examples in his opening post do not have an "als+c" deduction.)

[edit: pzl #35664 was #35644]
Last edited by ronk on Thu Feb 19, 2009 1:59 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Wed Feb 18, 2009 12:42 am

PIsaacson wrote:I use these beasts in nice-loops, but while I found it relatively easy to work out the rules for weak link propagation for an AHS in a nice-loop chain, I can't seem to get my head around how to directly combine:

AHS to ALS
ALS to AHS (probably a symmetrical set of rules to the above)
AHS to AHS

Perhaps these four different ALS/AHS combinations for the same eliminations -- r79c6<>9, r2c5<>7, r8c7<>1 -- will be helpful. It's from #432 of the top1465. Unfortunately it's buried beneath a few other ALS-xz steps. If there's interest, I can search for a similar example that surfaces after SSTS.

ALS in both R8 and C5
Code: Select all
+---------------+-----------------------+--------------------+
| 1    2    38  | 4      5       6      | 37    78     9     |
| 4    358  6   | 1378   289-7   1379   | 125   125    1358  |
| 7    358  9   | 138    28      13     | 1245  12456  13568 |
+---------------+-----------------------+--------------------+
| 2    38   7   | 5      1       4      | 6     9      38    |
| 6    4    1   | 9      3       8      | 57    57     2     |
| 38   9    5   | 67     (67)    2      | 13    18     4     |
+---------------+-----------------------+--------------------+
| 39   6    34  | 2      (479)   1357-9 | 8     145    157   |
| 5    7    2   | (168)  (489)   (19)   | 49-1  3      (16)  |
| 389  1    348 | 367    (4679)  357-9  | 2459  2456   567   |
+---------------+-----------------------+--------------------+
     7 Sets = {8N469 6789N5}
     7 Links = {16r8 67c5 489b8}


ALS in R8 and AHS in C5
Code: Select all
+---------------+------------------------+--------------------+
| 1    2    38  | 4      5        6      | 37    78     9     |
| 4    358  6   | 1378   -7(289)  1379   | 125   125    1358  |
| 7    358  9   | 138    (28)     13     | 1245  12456  13568 |
+---------------+------------------------+--------------------+
| 2    38   7   | 5      1        4      | 6     9      38    |
| 6    4    1   | 9      3        8      | 57    57     2     |
| 38   9    5   | 67     67       2      | 13    18     4     |
+---------------+------------------------+--------------------+
| 39   6    34  | 2      47(9)    1357-9 | 8     145    157   |
| 5    7    2   | (168)  4(89)    (19)   | 49-1  3      (16)  |
| 389  1    348 | 367    467(9)   357-9  | 2459  2456   567   |
+---------------+------------------------+--------------------+
     6 Sets = {289C5 8N469}
     6 Links = {16r8 23n5 89b8}


AHS in R8 and ALS in C5
Code: Select all
+---------------+----------------------+----------------------+
| 1    2    38  | 4     5       6      | 37      78     9     |
| 4    358  6   | 1378  289-7   1379   | 125     125    1358  |
| 7    358  9   | 138   28      13     | 1245    12456  13568 |
+---------------+----------------------+----------------------+
| 2    38   7   | 5     1       4      | 6       9      38    |
| 6    4    1   | 9     3       8      | 57      57     2     |
| 38   9    5   | 67    (67)    2      | 13      18     4     |
+---------------+----------------------+----------------------+
| 39   6    34  | 2     (479)   1357-9 | 8       145    157   |
| 5    7    2   | 168   8(49)   1(9)   | -1(49)  3      16    |
| 389  1    348 | 367   (4679)  357-9  | 2459    2456   567   |
+---------------+----------------------+----------------------+
     5 Sets = {49R8 679N5}
     5 Links = {67c5 8n7 49b8}


AHS in both R8 and C5
Code: Select all
+---------------+-----------------------+----------------------+
| 1    2    38  | 4     5        6      | 37      78     9     |
| 4    358  6   | 1378  -7(289)  1379   | 125     125    1358  |
| 7    358  9   | 138   (28)     13     | 1245    12456  13568 |
+---------------+-----------------------+----------------------+
| 2    38   7   | 5     1        4      | 6       9      38    |
| 6    4    1   | 9     3        8      | 57      57     2     |
| 38   9    5   | 67    67       2      | 13      18     4     |
+---------------+-----------------------+----------------------+
| 39   6    34  | 2     47(9)    1357-9 | 8       145    157   |
| 5    7    2   | 168   (489)    1(9)   | -1(49)  3      16    |
| 389  1    348 | 367   467(9)   357-9  | 2459    2456   567   |
+---------------+-----------------------+----------------------+
     5 Sets = {49R8 289C5}
     5 Links = {238n5 8n7 9b8}
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Wed Feb 18, 2009 1:29 am

Hi Allan,

I have to retract my statement regarding bi-directionality/reversibility being a requirement. From working/studying Denis Berthier's nrczt chains, I learned that given a target CEC, it is entirely sufficient to prove the elimination by following a left-to-right implication chain. nrczt chains are not reversible, yet they are certainly valid. So, while currently ALS chains may be/are reversible, it is not essential. Using that viewpoint, my above 3-step process can eliminate the final stage for at least linking AHSs directly to ALSs:

Dx false ==> AHS ==> LS (core+Dx) one of which will be the RCD ==> ALS RCD false ==> LS (ALS-RCD) ...

By "directly combine", I meant something like the above -- directly link but without any intermediate "helping" cells. My problem is that I couldn't figure how to trigger that starting event of making one of the AHS extra digits true without some kind of outside help.

Thanks to Champagne's example, light bulbs are starting to form...

I think Champagne has been trying to lead me to the conclusion that I have to treat ALSs/AHSs as pairs, and then follow the implications of their interactions. If an ALS converts to a LS, then the complement AHS should also convert to a hidden LS. If I'm right, then ALS loops can trigger more eliminations than what I am currently generating -- sorry for the mental meandering but at least that's something I can easily code/test.

So, at any point in an ALS chain, the paired AHS is likewise collapsing into a hidden LS and the implication chain can take alternative paths if the hidden LS can be RCD linked to another ALS? This is exactly what I have been looking for!!! I have GOT to try this!!!

Cheers,
Paul

[edit] I have to qualify my retraction: ALS chains do not need to be reversible, but ALS loops do. The eliminations in an ALS loop depend upon the loop's inference logic being reversible.
Last edited by PIsaacson on Wed Feb 18, 2009 10:06 pm, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Wed Feb 18, 2009 2:43 am

champagne wrote:And the Nice loop produced by the solver

Code: Select all
[]6r9c78 - 6r9c23 = AC:r7c2r8c3(6r7c2r8c3 - 4r7c2r8c3) = 4r78c1 - 4r23c1
                  = AC:r2c3r3c2(4r2c3r3c2 - 2r2c3r3c2) = 2r1c23 - 2r1c78
                  = AC:r2c7r3c8(2r2c7r3c8.å - 6r2c7r3c8)
                  = 6r23c9 - 6r78c9

In such a case, Ronk would prefer the shorter form using exclusively "ALS" that I write in that way

Code: Select all
[]6r9c78 - 6r9c23 = || = 4r78c1 - 4r23c1  = || = 2r1c23 - 2r1c78  = ||= 6r23c9 - 6r78c9
                  ALS r78c1r9c23       ALS r1c23r23c1          ALS  r1c78r23c9

Wow! That's an SK-loop variant (this one with 13 eliminations) I've not seen before. However, in order that the nice loop reflect the 6 eliminations in b1, b3 and b7, I would prefer triply-linking AALSs as follows:

r9c78 -6- aals:r9c23 -159- aals:r78c1 -4- aals:r23c1 -789- aals:r1c23 -2- aals:r1c78 -159- aals:r23c9 -6- r78c9 =6= continuous loop
==> r3c28<>9, r9c46<>6, r46c1<>4, r28c3<>9, r46c9<>6, r1c4<>2, r3c8<>1, r8c3<>1

What is the origin of this puzzle:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques