ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

Postby PIsaacson » Thu Feb 26, 2009 9:09 am

In order to allow ALS chains to fully subsume XY chains, the RCD adjacency rules need to be modified as follows:
Code: Select all
1) ALS(1) -{1}-  ALS(2)  -{n}-      n cannot be 1
2) ALS(1) -{12}- ALS(2)  -{nm}-     nm must be 12
3) ALS(1) -{n}-  ALS(2)  -{12}-     n must be either 1 or 2
4) ALS(1) -{12}- ALS(2)  -{n}       n must be either 1 or 2 depending on:

   Backtrack prior sub-chain {12} dual-links to the beginning (origin) single.

   a) If the number of prior {12}s is odd, then n must be the same as the origin RCD.
   b) If the number of prior {12}s is even, then n cannot be the same as the origin RCD.

   a) als -1- als -12- als -1-            Odd length subchain extends the origin RCD
   b) als -1- als -12- als -12- als -2-   Even length subchain "flips" the origin RCD


Rule (1) conforms with the prior adjacency rule prohibiting RCD reuse in consecutive ALSs.
Rule (2) allows for sub-chains of dual-linked ALSs, specifically conjugate pairs as in XY chains.
Rules (3) and (4) define the entry/exit conditions for such sub-chains.

Loop checking becomes trickier when a potential loop "starts"/"ends" with a dual-link. You have to locate the corresponding origin/terminal ALSs, count the number of dual-linked conjugate pairs in-between, then check that the loop is valid. Since a circle has no end, I skip potential loops that "start" with a dual-link and wait until it is rediscovered with the dual-link sub-chain at the "end" and the terminal ALS at the "start" of the chain. This made the loop checking easier to code. The terms "start" and "end" are only meaningful in terms of how the chain is developed/linked. Once it loops, "start" and "end" are arbitrary at best.

The prior version of my ALS engine found 80333 eliminations in 1183 seconds from the royle17 collection of 36628 puzzles.
The new version found 88075 eliminations in 3247 seconds. A 10% increase in eliminations at the cost of a 3-fold increase in run-time. But there were 1375 unsolved with the old method and only 810 unsolved with the new using only the ALS engine and simple techniques previously documented. That's about a 40% improvement in solving to completion.
Code: Select all
                                         Prior    New

plain ALS                                25340   26150
overlap ALS                              23863   30043
cannibal ALS                              2165    2022
overlap/cannibal ALS                      8013    7601
----------------------------------------------   -----
All ALS types                            59381   65816


plain ALS loop                             566     592
overlap ALS loop                           122     189
cannibal ALS loop                           97     101
overlap/cannibal ALS loop                   26      57
----------------------------------------------   -----
All ALS loops (included in above)          811     939

I'll post the updated code later tonight. Those who want to experiment with comparisons to XY chains can use:

sudoku -bv -A2 -B8 -w <puzzle>

The -w flag switches to the new RCD rules. Testing with/without the -w flag will demonstrate the effectiveness of the new rules, especially for XY chaining example puzzles. If chain length -B8 (which is really 10 for those who read the brief explanation of the options) is insufficient, try a larger number such as -B12. Interestingly, the overlapping ALSs are now more common (and productive in terms of eliminations) than the plain non-overlapping variety.
Last edited by PIsaacson on Thu Feb 26, 2009 11:05 pm, edited 2 times in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Thu Feb 26, 2009 3:39 pm

The executable and source files have been refreshed with the latest changes for the RCD rules. The "-w" switch must be included as a run time option to activate the new rules, otherwise it defaults to the prior RCD adjacency rules. If you have downloaded the prior source, you can "diff -w" to see all the changes.

The AHS code is present, but not functioning correctly - still debugging it, so don't use the "-H" switch unless you want to see lots of incorrect eliminations. But the chains are interesting to review. Look for <hxxxx> which indicates a "hidden" ALS and <nxxxx> which indicates a "naked" ALS.

Also fixed non-looping chains that terminate with a dual-linked ALS pair. That also required back-tracking to the origin RCD and improved the royle17 results to 479 unsolved puzzles, 98638 eliminations and 75159 total ALS chains (with eliminations) discovered. If you ever want to see all the ALS chains considered, and I don't recommend this except for a single puzzle, use the "-V" extra-verbose switch. You will get the full trace output including the entire ALS search tree. It won't make much sense, but it's awesome to see all of the non-productive ALS chains that the engine generates/considers.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Thu Feb 26, 2009 7:21 pm

PIsaacson wrote:In order to allow ALS chains to fully subsume XY chains, the RCD adjacency rules need to be modified as follows:
Code: Select all
1) ALS(1) -{1}-  ALS(2)  -{n}-      n cannot be 1
2) ALS(1) -{12}- ALS2(2) -{nm}-     nm must be 12
3) ALS(1) -{n}-  ALS(2)  -{12}-     n must be either 1 or 2
4) ALS(1) -{12}- ALS(2)  -{n}       n must be either 1 or 2 depending on:

   Backtrack prior sub-chain {12} dual-links to the beginning (origin) single.

   a) If the number of prior {12}s is odd, then n must be the same as the origin RCD.
   b) If the number of prior {12}s is even, then n cannot be the same as the origin RCD.

   a) als -1- als -12- als -1-            Odd length subchain extends the origin RCD
   b) als -1- als -12- als -12- als -2-   Even length subchain "flips" the origin RCD


[...]

Loop checking becomes trickier when a potential loop "starts"/"ends" with a dual-link. You have to locate the corresponding origin/terminal ALSs, count the number of dual-linked conjugate pairs in-between, then check that the loop is valid.

Paul, this seems unbelievably complicated. Doesn't your "-{12}-" and "-12-" notation merely indicate a link between two identical bivalues:?: If so, why are you treating it as doubly-linked in the first place:?:

But perhaps I'm not understanding the notation, so I ask ...
1) Is the "(1)" in "ALS(1)" part of the ALS label, or does it refer to a candidate?
2)Is "ALS2(2)" in rule 2 a typo?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Fri Feb 27, 2009 2:39 am

Ron,

Sorry for the typo, I'll edit the posting and yes, the {12} and -12- indicate RCDs. I was using the {} to indicate hypothetical candidates and the -12- to indicate actual cases. And yes again, the ALS(x) -12- ALS(y) indicates an identical bi-value, but it doesn't have to. It can be any set of dual-linked ALSs. The parentheses are not RCDs, they are simply indicators of different ALSs (labels) since I can't put subscripts in - or at least I don't know how to put in subscripts...

Allowing dual-links to participate in ALS chains had always been problematic with the prior RCD adjacency rules. Allan Barker proved that it was possible, and the desire to have ALS chains exactly replicate XY chains has haunted me ever since. The main reason why these RCD adjacency rules are complex is to allow for the "strings", as I call them, of conjugate links in XY chains. An identical pair of bi-values is indeed a dual-linked ALS. If you consider how they function as either an extension of, or an inversion of their RCD values, then the even/odd rule follows.

Testing my engine both with and without the "-w" switch against various XY chain example puzzles will show the vast difference between the two different sets of RCD rules. In my full solver with both an XY engine as well as the ALS engine, if I select the ALS engine to run first with the new RCD rules, there are only a few additional eliminations found by the XY engine. I'm investigating why they are not completely subsumed, but I suspect it has more to do with my elimination code than the chaining/linking code.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Fri Feb 27, 2009 9:37 am

Just when you thought I was done with odd-ball stuff, here comes another:

If you allow for ALS loops, then you have to allow for the possibility that the loop cannot form successfully and instead, you have proven a contradiction of the starting RCD.

ALS1 -1- ALS2 .... ALSn -1- ALS1 loop with the starting RCD and the ending RCD equal.

Since the starting RCD in ALS1 cannot be both true and false, it can be eliminated from ALS1. In honor of Denis Berthier's nrczt-whips which are also a contradiction of an initial premise, I'm calling these things ALS whips. Forgive me Denis...

I've yet again modified my code (but I'm not going to upload until I get XY chains completely subsumed) and these whips are fairly common. More so than ALS loops. I haven't figured out how to handle whips starting/ending with a dual-link (but I suspect it's going to involve my back-tracking even/odd RCD rule), so I'm just currently studying cases that begin/end with the same single RCD.

Code: Select all
ALS chains/loops/whips
478 puzzles unsolved with 99278 total eliminations

78243 all ALS chain/loop/whip types
31829 "normal" ALS chains - non overlapping and non cannibalistic
30613 overlapping ALS chains
 7211 cannibalistic ALS chains
 8589 overlapping/cannibalistic ALS chains

 1054 all ALS loops
  625 "normal" ALS loops - non overlapping and non cannibalistic
  232 overlapping ALS loops
  103 cannibalistic ALS loops
   94 overlapping/cannibalistic ALS loops

 6968 all ALS whips *** About 9% of all ALS chains now found are whips
 4459 cannibalistic ALS whips
 2809 overlapping/callibalistic ALS whips


I'm searching for other documentation on ALS loops/whips, but without any success. If anyone knows of prior works, please let me know the link(s).

Cheers,
Paul

P.S. As with nrczt whips, I need to modify the code to check for a contradiction anywhere along the length of the ALS chain. It doesn't need to be just the first/starting ALS if the whips theory holds true for ALS chains as it does for nrczt chains.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sat Feb 28, 2009 12:16 am

PIsaacson wrote:If you allow for ALS loops, then you have to allow for the possibility that the loop cannot form successfully and instead, you have proven a contradiction of the starting RCD.

ALS1 -1- ALS2 .... ALSn -1- ALS1 loop with the starting RCD and the ending RCD equal.

Since the starting RCD in ALS1 cannot be both true and false, it can be eliminated from ALS1.

Does ALS1 actually being an ALS contribute anything to these discontinuous loops? If "ALS1" were merely one or more candidate-elimination-cells, there should be many more such loops.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Sat Feb 28, 2009 1:11 am

ronk wrote:Does ALS1 actually being an ALS contribute anything to these discontinuous loops? If "ALS1" were merely one or more candidate-elimination-cells, there should be many more such loops.

I modified the code to allow for the discontinuity/contradiction to occur anywhere within the developing chain ala Denis's whips theory, and the counts did increase some:
Code: Select all
All ALSs                                91408
Plain ALSs                              48472
Overlapping ALSs                        32673
Cannibalistic ALSs                      2729
Overlapping/cannibalistic ALSs          5855

All ALS loops                           1053
Plain ALS loops                         625
Overlapping ALS loops                   231
Cannibalistic ALS loops                 103
Overlapping/cannibalistic ALS loops     94

All ALS whips                           9033
Plain ALS whips                         6587
Overlapping ALS whips                   2446
Cannibalistic ALS whips                 0
Overlapping/cannibalistic ALS whips     0

Without loops/whips, the unsolved count is 1375 puzzles from the royle17 collection with 80333 eliminations. With loops/whips, it's now 478 and 99558 eliminations. I'm not positive, so I'm guessing that these numbers indicate the ALS1 does indeed act as something other than a CEC. Otherwise, it should have been located by the non-loop/whips version. I'm still looking at random samples from the royle17 and top1465 collections.

Here's just a few examples. When I execute against the entire Top1465, I get 198 puzzles containing 628 whips total.
Code: Select all
 Top1465 #13 after elementary eliminations
 
 *-----------------------------------------------------------------------------*
 | 6       57      9       | 234     2345    2345    |A134-7  B1245    8       |
 | 23      58      23      | 7       458     1       |C469    C4569   C569     |
 | 4       578     1       | 69      2358    69      |A37     B25      2357    |
 |-------------------------+-------------------------+-------------------------|
 | 157     9       8       | 123     6       2357    |A17     B12      4       |
 | 157     2       46      | 1489    1457    45789   | 16789   3       1679    |
 | 17      3       46      | 12489   1247    24789   | 5       12689   12679   |
 |-------------------------+-------------------------+-------------------------|
 | 239     1       23      | 5       34      3468    | 34689   7       369     |
 | 8       46      57      | 12346   9       23467   | 1346    1456    1356    |
 | 39      46      57      | 13468   1347    34678   | 2       145689  13569   |
 *-----------------------------------------------------------------------------*

do_alschains - reducing r1c7.<1347> by <4> whip als[1]
do_alschains - als[4x4/8]-whip r134c7.<n1347> -4- r134c8.<n1245> -45- r2c789.<n4569> -4- r134c7.<n1347>


The above example is a whip that causes a contradiction with the 1st ALS in the chain (reducing ... whip als[1])

Code: Select all
 Top1465 #44 after elementary eliminations

 *--------------------------------------------------------------------*
 | 5      6      7      | 24     9      24     |A1-8    3      18     |
 | 29    E39     239    | 8      6      1      |C57     4      57     |
 | 1      4      8      | 3      7      5      | 9      26     26     |
 |----------------------+----------------------+----------------------|
 | 6      2     D35     | 1      4      8      |C357    79     579    |
 | 49    E359    13459  | 7      35     26     | 1345   8      26     |
 | 78     78     1345   | 26     35     9      | 1345   26     15     |
 |----------------------+----------------------+----------------------|
 | 27     1      25     | 9      8      3      | 6      57     4      |
 | 3     E79    B46     | 5      2     B46     |B78     1      789    |
 | 489    589    4569   | 46     1      7      | 2      59     3      |
 *--------------------------------------------------------------------*

do_alschains - reducing r1c7.<18> by <8> whip als[2]
do_alschains - als[6x4/8]-whip r1c7.<n18> -8- r8c367.<n4678> -7- r24c7.<n357> -3- r4c3.<n35> -5- r258c2.<n3579> -7- r8c367.<n4678>


The above example is a whip that causes a contradiction with the 2nd ALS in the chain (reducing ... whip als[2])

I'm using hobiwan's HoDoKu (all possible steps) to correlate eliminations via other techniques. The 1st example seems to be really unique -- the 3 ALSs are in a rather packed formation. The 2nd example is covered by several nice loops including a group NL using a few of the same ALSs. Neither example is duplicated by other ALS chains using either HoDoKu, or my engine without the loops/whips option enabled.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sat Feb 28, 2009 7:59 pm

PIsaacson wrote:do_alschains - reducing r1c7.<1347> by <4> whip als[1]
do_alschains - als[4x4/8]-whip r134c7.<n1347> -4- r134c8.<n1245> -45- r2c789.<n4569> -4- r134c7.<n1347>

This can be shortened to ... r1c7 -4- als:r134c8 -5- als:r2c789 -4- r1c7 ==> r1c7<>4

It could also be viewed as a doubly-linked ALS xz-rule, which happens to be a Sue De Coq.

PIsaacson wrote:do_alschains - reducing r1c7.<18> by <8> whip als[2]
do_alschains - als[6x4/8]-whip r1c7.<n18> -8- r8c367.<n4678> -7- r24c7.<n357> -3- r4c3.<n35> -5- r258c2.<n3579> -7- r8c367.<n4678>

This can be shortened to ... r8c7 -7- als:r24c7 -3- r4c3 -5- als:r258c2 -7- r8c7 ==> r8c7<>7

Neither needs an ALS at the discontinuity (of the discontinuous loops).

PIsaacson wrote:I'm not positive, so I'm guessing that these numbers indicate the ALS1 does indeed act as something other than a CEC. Otherwise, it should have been located by the non-loop/whips version.
[...]
Neither example is duplicated by other ALS chains using either HoDoKu, or my engine without the loops/whips option enabled.

I understand your use of the loop and whip terms to mean continuous loop and discontinuous loop, respectively. If so, I'm not suggesting that you disable "whips", but rather enable them without the requirement for an ALS at the discontinuity.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Sun Mar 01, 2009 3:03 am

ronk wrote:It could also be viewed as a doubly-linked ALS xz-rule, which happens to be a Sue De Coq.

Thanks for pointing this out. I completely skipped looking at SDCs as equivalents. Worse, in my elimination code, I was processing loops/whips before SDCs/dual-linked sets, so the loops/whips were popping up first. If there are no possible eliminations, the ALS chain does not print, so ordering gave precedence to loops/whip. I've changed the ordering to place loops/whips last, and this has reduced their frequency of occurence. But it has not completely eliminated loops/whips. Comparing with and without loops/whips still shows a significant difference in the number of unsolved puzzles.
ronk wrote:I understand your use of the loop and whip terms to mean continuous loop and discontinuous loop, respectively. If so, I'm not suggesting that you disable "whips", but rather enable them without the requirement for an ALS at the discontinuity.

I'm torn between keeping these things "pure" ALS chains or allowing for some slight deviations such as you suggest. The only reason I hesitate is that once you allow something other than an ALS to participate, where do you stop? As for the terms, I find the phrases continuous loop and discontinuous loop amusingly redundant in the first case, and ironically contradictory in the second. But you're correct that I'm implying identical meaning, so I should use terms that have precedence and common understanding. I'll refrain from using loop/whip and defer to the standard terms in the future.

Again, thanks for taking time to study these postings.
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sun Mar 01, 2009 4:40 am

PIsaacson wrote:
ronk wrote:If so, I'm not suggesting that you disable "whips", but rather enable them without the requirement for an ALS at the discontinuity.

I'm torn between keeping these things "pure" ALS chains or allowing for some slight deviations such as you suggest. The only reason I hesitate is that once you allow something other than an ALS to participate, where do you stop?

There is precedent for this exception. On the Forcing chains: Terminology and Definition thread ...

Jeff wrote:xy-chain or y-cycle - a chain, consists of all bivalue cells except at a discontinuity, that makes pure weak inferences between nodes to yield deduction(s). An xy-chain can be of any length. It can be continuous or discontinuous.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Sun Mar 01, 2009 3:10 pm

PIsaacson wrote:The prior version of my ALS engine found 80333 eliminations in 1183 seconds from the royle17 collection of 36628 puzzles.
The new version found 88075 eliminations in 3247 seconds.
A 10% increase in eliminations at the cost of a 3-fold increase in run-time.
But there were 1375 unsolved with the old method and only 810 unsolved with the new using only the ALS engine and simple techniques previously documented. That's about a 40% improvement in solving to completion.Code:
Prior New

plain ALS 25340 26150
overlap ALS 23863 30043
cannibal ALS 2165 2022
overlap/cannibal ALS 8013 7601
---------------------------------------------- -----
All ALS types 59381 65816


plain ALS loop 566 592
overlap ALS loop 122 189
cannibal ALS loop 97 101
overlap/cannibal ALS loop 26 57
---------------------------------------------- -----
All ALS loops (included in above) 811 939

I'll post the updated code later tonight. Those who want to experiment with comparisons to XY chains can use:



Hi Paul,


I react late to that post (I know new data came in between), but I would like to be sure to catch your point.

First of all, the 17 clues puzzles are not very challenging.
I made a test using my own old file of 40886 puzzles (seem to be to-day over 42000). Most of these puzzles don't enter the tagging process.
The overall run was done in 658 seconds, similar to your results
In that list, only 67 puzzles entered level 2 of my process where AHS are active.
If your 88075 eliminations refer specifically to ALS use, it likely means that you search in priority such eliminations.

For me, ALS chains are tougher to find that standard bi values or group bi-values chains, (much more stuff to handle), so I would be reluctant to jump immediately at level 2, what I am doing for "hardest" puzzles.

Another surprise for me is the number of unsolved puzzles.
I guess the number can be explained due to the fact that your engine in not mixing ALS with other stuff.
Could you give one or 2 examples of such puzzles??

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

Postby PIsaacson » Sun Mar 01, 2009 6:16 pm

Hi Champagne,

I chose the royle17 36628 collection because it didn't contain just hard puzzles like the top... variety. With that said, I've also run against many top... collections, specifically the top50000, top10000, top1465, top105, top95 and top50. The results all show that ALSs are commonly found in most every puzzle. I think it's just a matter of how far into the solution process one wants/needs to go in order to take advantage of them.

In my first attempt at ALS chains, I placed that method after other things such as XY chains, nice loops, 3d-medusa etc. By the time the ALS engine was invoked, most of the eliminations it might have found had already been covered by the other methods, so I wasn't very impressed with their "performance". This didn't cause me concern until I started investigating SDCs and their relative frequency. Some maintained that they were rare, but I found that if I scheduled SDCs/ALSs earlier, they started popping up fairly often.

So, with that in mind and for these tests/postings:

My ALS engine executes immediately after very elementary methods are applied. Naked/hidden singles, row/col/box interactions, naked/hidden subsets size 2-4 and basic fish (x-wing, swordfish...) size 2-4. No other higher level methods of executed, so if the puzzle cannot be solved with just those elementary methods and the ALS engine, it remains "unsolved". In fact, if you were to look at the logs you would see that the DLX method kicks in immediately after the ALS engine surrenders. I consider DLX a T&E last ditch method and use it mostly to test that there is a unique valid solution, and that the test methods haven't generated invalid eliminations.

That's probably more than you wanted to know, but it's crucial in order to gauge the relevence of my reported numbers/statistics.

As for bi-value/location pairs:

I still think the ALS engine should completely subsume XY chains and I'm really close. Just a few weird edge cases remain that I need to investigate. If you're talking about b/b plots, then it's a whole different matter and I'm amazed by the additional "power" given to grouped nice loops with the new ALS engine churning out ALSs and AHSs. They work beautifully there and I love seeing NLs with AHSs and ALSs jumping back and forth. But, I still haven't figured out how to effectively use AHSs in ALS chains. I'm following your suggestion/recommendation that I always consider them in pairs, but if I defer the AHS processing after the ALS processing side, it's like I'm going through a tremendous amount of effort (computer time that is) for almost no additional eliminations. More work to do.,,

I'm still reading you web pages on full tagging, so I'm by no means certain of the following: It looks like your level 1 processing is very powerful - similar to 3d-medusa??? I know that when I execute my 3d-medusa before ALS chains, it really reduces the likelihood of the ALS engine finding anything. Same thing if I allow nice loops to run first, or my nrczt-chains. Even XY chains messes things up for me because I've implemented Denis Berthier's hXYzt as well as nrczt chains.

And at long last, I'm not sure what examples you're requesting. Do you want puzzles that the ALS engine, but itself, can't solve? And from any specific puzzle collection?

Here's one that I've been having a lot of fun with. If I run my program with different options, it will either find nothing, or else find some really interesting chains.
Code: Select all
Puzzle: 12.456..94.6......7.9......2.751469.641938..2.95..2..4.6.2..8..572....3..1....... puzzle 1 x.pm

 1         2         38       |4         5         6        |37        78        9       
 4         358       6        |1378      2789      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       13579    |8         145       157     
 5         7         2        |168       489       19       |149       3         16       
 389       1         348      |367       4679      3579     |2459      2456      567     

do_alschains - graph contains 150 vertices and 1232 edges
do_alschains - reducing r2c5.<2789> by <2>
do_alschains - reducing r3c7.<1245> by <2>
do_alschains - reducing r3c8.<12456> by <2>
do_alschains - als+[6x6/9] r3c5.<n28> -8- r8c567.<n1489> -18- r8c49.<n168> -8- b2x4679.<n13789> -9- r8c69.<n169> -6- r3c24569.<n123568>
do_alschains - reducing r3c9.<13568> by <3>
do_alschains - als+[5x6/9] r3c6.<n13> -1- r8c6.<n19> -9- b2x4679.<n13789> -8- r8c4679.<n14689> -4- r3c24567.<n123458>
do_alschains - reducing r7c6.<13579> by <3>
do_alschains - als[6x6/9] r3c6.<n13> -1- r2369c4.<n13678> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r7c3.<n34>
do_alschains - reducing r3c6.<13> by <1> whip als[3]
do_alschains - als[6x6/9]-whip r3c6.<n13> -1- r2369c4.<n13678> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r2c8.<125> by <5>
do_alschains - reducing r3c8.<1456> by <5>
do_alschains - reducing r9c8.<2456> by <5>
do_alschains - als+[5x5/6] r5c8.<n57> -7- r1c8.<n78> -8- r1c3.<n38> -3- r7c3.<n34> -4- r1567c8.<n14578>
do_alschains - reducing r8c4.<168> by <6>
do_alschains - als+c[6x6/9] r6c4.<n67> -7- b2x479.<n1378> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c679.<n1469>
do_alschains - reducing r6c4.<67> by <7> whip als[3]
do_alschains - als[6x6/9]-whip r6c4.<n67> -7- b2x479.<n1378> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r8c7.<149> by <1>
do_alschains - als[6x5/7] r6c7.<n13> -3- r1c7.<n37> -7- r1c8.<n78> -8- r1c3.<n38> -3- r7c3.<n34> -4- b9x2369.<n14567>
do_alschains - reducing r3c7.<145> by <1>
do_alschains - als[6x5/7] r6c7.<n13> -3- r1c7.<n37> -7- r1c8.<n78> -8- r17c3.<n348> -4- b9x2369.<n14567> -6- r3c2469.<n13568>
do_alschains - reducing r7c6.<1579> by <9>
do_alschains - als[6x6/9] r7c1.<n39> -3- r7c3.<n34> -4- r12567c8.<n124578> -2- r12356c7.<n123457> -4- r8c4679.<n14689> -8- b2x4679.<n13789>
do_alschains - reducing r9c1.<389> by <3>
do_alschains - reducing r9c3.<348> by <3>
do_alschains - als[6x6/9] r7c3.<n34> -4- r12567c8.<n124578> -2- r12356c7.<n123457> -4- r8c4679.<n14689> -8- b2x479.<n1378> -7- r69c4.<n367>
do_alschains - reducing r9c6.<3579> by <9> loop type (1) leg[1]
do_alschains - reducing r2c5.<789> by <7> loop type (2) als[2]
do_alschains - als+c[5x5/7]-loop r8c6.<n19> -9- b2x4679.<n13789> -89- r8c469.<n1689> -9- r2379c6.<n13579> -19- r8c6.<n19>
do_alschains - reducing r8c4.<18> by <1>
do_alschains - reducing r8c9.<16> by <1>
do_alschains - als+c[6x6/9] r8c6.<n19> -9- b2x4679.<n13789> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c67.<n149>
do_alschains - reducing r8c6.<19> by <9> whip als[3]
do_alschains - als+[6x6/9]-whip r8c6.<n19> -9- b2x4679.<n13789> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r3c9.<1568> by <6>
do_alschains - reducing r9c8.<246> by <6>
do_alschains - als+[5x6/7] r8c9.<n16> -1- r8c6.<n19> -9- r679c5.<n4679> -49- r8c4569.<n14689> +9+ b9x23469.<n145679>
do_alschains - reducing r9c9.<567> by <6>
do_alschains - als+[6x5/9] r8c9.<n16> -1- r8c6.<n19> -9- b2x4679.<n13789> -8- r8c4679.<n14689> -4- b3x457.<n1245> -5- r2348c9.<n13568>
do_alschains - reducing r3c8.<146> by <1>
do_alschains - als+[6x6/8] r3c46.<n138> -8- r8c49.<n168> -18- r8c567.<n1489> +8+ r8c469.<n1689> +9+ b9x23469.<n145679> -6- r3c2469.<n13568>
do_alschains - reducing r3c9.<158> by <1>
do_alschains - als+[5x5/8] r3c46.<n138> -8- r8c49.<n168> -18- r8c567.<n1489> +8+ r8c4679.<n14689> -4- b3x457.<n1245>
do_alschains - reducing r2c6.<1379> by <1>
do_alschains - reducing r2c6.<379> by <3>
do_alschains - als+[6x6/9] r3c46.<n138> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r7c135.<n3479> -7- r3789c6.<n13579>
do_alschains - reducing r3c4.<138> by <8> whip als[2]
do_alschains - als[5x6/9]-whip r3c46.<n138> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r9c4.<367> by <7> whip als[3]
do_alschains - als[6x6/9]-whip r69c4.<n367> -7- b2x479.<n1378> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r8c7.<49> by <4> whip als[1]
do_alschains - als[4x6/8]-whip r8c67.<n149> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c67.<n149>
do_alschains - reducing r8c5.<489> by <9>
do_alschains - als+[5x6/8] r8c67.<n149> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r7c135.<n3479> -7- r3789c6.<n13579>
do_alschains - reducing r3c5.<28> by <8>
do_alschains - als+[6x5/8] b2x479.<n1378> -7- r6c4.<n67> -67- r6c5.<n67> -7- r7c135.<n3479> -4- b9x2369.<n14567> -6- r3c2469.<n13568>
do_alschains - reducing r2c4.<1378> by <8> whip als[2]
do_alschains - als[5x6/9]-whip b2x479.<n1378> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r2c6.<79> by <7> whip als[3]
do_alschains - als+[6x6/9]-whip r238c6.<n1379> +7+ b2x479.<n1378> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r7c8.<145> by <4>
do_alschains - als[5x5/7] r7c135.<n3479> -7- r6c5.<n67> -67- r6c4.<n67> -7- b2x479.<n1378> -8- r8c4679.<n14689>
do_alschains - reducing r9c5.<4679> by <7>
do_alschains - als+[6x6/9] r7c135.<n3479> -4- r12567c8.<n124578> -2- r12356c7.<n123457> -4- r8c4679.<n14689> -8- b2x4679.<n13789> +9+ r3789c6.<n13579>
do_alschains - reducing r9c5.<469> by <9>
do_alschains - als+[6x6/8] r8c469.<n1689> -8- b2x479.<n1378> -7- r6c4.<n67> -67- r6c5.<n67> -67- r6c1478.<n13678> -6- r23678c5.<n246789>
do_alschains - reducing r8c5.<48> by <8> whip als[2]
do_alschains - als+[5x6/9]-whip r8c567.<n1489> +8+ r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>
do_alschains - reducing r3c7.<45> by <5>
do_alschains - als[4x6/9] r1256c7.<n12357> -2- r12567c8.<n124578> -4- r8c679.<n1469> -6- r3c2469.<n13568>
do_alschains - reducing r9c7.<2459> by <5>
do_alschains - als+[6x6/8] b9x2369.<n14567> -4- r7c135.<n3479> -7- r3789c6.<n13579> -9- r679c5.<n4679> -49- r8c4569.<n14689> +9+ b9x23469.<n145679>
do_alschains - reducing r9c7.<249> by <4>
do_alschains - als+[6x6/9] r8c4679.<n14689> -8- b2x4679.<n13789> +9+ r3789c6.<n13579> -7- r7c135.<n3479> -4- r12567c8.<n124578> -2- r12356c7.<n123457>
do_alschains - reducing r3c8.<46> by <4>
do_alschains - als[2x6/7] r12356c7.<n123457> -2- r12567c8.<n124578>
do_alschains - reducing r2c5.<89> by <9> whip als[3]
do_alschains - als+[6x6/9]-whip b2x45789.<n123789> +9+ b2x4679.<n13789> -8- r8c4679.<n14689> -4- r12356c7.<n123457> -2- r12567c8.<n124578> -4- r8c4679.<n14689>

do_alschains - ending with 44 updates 36 total solved

do_pinnings - setting r2c4 = d7 hidden single
do_pinnings - setting r2c5 = d8 naked single
do_pinnings - setting r2c6 = d9 naked single
do_pinnings - setting r3c4 = d1 hidden single
do_pinnings - setting r3c5 = d2 naked single
do_pinnings - setting r3c6 = d3 naked single
do_pinnings - setting r3c7 = d4 naked single
do_pinnings - setting r3c8 = d6 naked single
do_pinnings - setting r6c4 = d6 naked single
do_pinnings - setting r6c5 = d7 naked single
do_pinnings - setting r7c5 = d9 hidden single
do_pinnings - setting r8c4 = d8 naked single
do_pinnings - setting r8c5 = d4 naked single
do_pinnings - setting r8c6 = d1 naked single
do_pinnings - setting r8c7 = d9 naked single
do_pinnings - setting r8c9 = d6 naked single
do_pinnings - setting r9c1 = d9 hidden single
do_pinnings - setting r9c3 = d8 hidden single
do_pinnings - setting r9c4 = d3 naked single
do_pinnings - setting r9c5 = d6 naked single
do_pinnings - setting r9c7 = d2 naked single
do_pinnings - setting r9c8 = d4 naked single

do_pinnings - ending with 22 updates 58 total solved

do_pinnings - setting r1c3 = d3 naked single
do_pinnings - setting r1c7 = d7 naked single
do_pinnings - setting r1c8 = d8 naked single
do_pinnings - setting r2c2 = d5 naked single
do_pinnings - setting r2c7 = d1 naked single
do_pinnings - setting r2c8 = d2 naked single
do_pinnings - setting r2c9 = d3 naked single
do_pinnings - setting r3c2 = d8 naked single
do_pinnings - setting r3c9 = d5 naked single
do_pinnings - setting r4c2 = d3 naked single
do_pinnings - setting r4c9 = d8 naked single
do_pinnings - setting r5c7 = d5 naked single
do_pinnings - setting r5c8 = d7 naked single
do_pinnings - setting r6c1 = d8 naked single
do_pinnings - setting r6c7 = d3 naked single
do_pinnings - setting r6c8 = d1 naked single
do_pinnings - setting r7c1 = d3 naked single
do_pinnings - setting r7c3 = d4 naked single
do_pinnings - setting r7c8 = d5 naked single
do_pinnings - setting r7c9 = d1 hidden single
do_pinnings - setting r9c6 = d5 hidden single
do_pinnings - setting r9c9 = d7 naked single

do_pinnings - ending with 22 updates 80 total solved

do_pinnings - setting r7c6 = d7 naked single

do_pinnings - ending with 1 updates 81 total solved

RCB solution        1 for puzzle 1 x.pm

 1 2 3| 4 5 6| 7 8 9
 4 5 6| 7 8 9| 1 2 3
 7 8 9| 1 2 3| 4 6 5
------+------+------
 2 3 7| 5 1 4| 6 9 8
 6 4 1| 9 3 8| 5 7 2
 8 9 5| 6 7 2| 3 1 4
------+------+------
 3 6 4| 2 9 7| 8 5 1
 5 7 2| 8 4 1| 9 3 6
 9 1 8| 3 6 5| 2 4 7

Puzzle call statistics:

  do_pinnings      updates/calls 45/4              11.2500       0.1791 msec       0.0448 msec/call       0.0040 msec/update
  do_restrictions  updates/calls 0/1                0.0000       0.0140 msec       0.0140 msec/call          inf msec/update
  do_subsets       updates/calls 0/1                0.0000       0.0729 msec       0.0729 msec/call          inf msec/update
  do_alschains     updates/calls 44/1              44.0000    3369.7534 msec    3369.7534 msec/call      76.5853 msec/update

Puzzle 1 took 3401.3672 msec for 1 solution(s)

/home/paul/nsudoku/sudoku -bv -Xprsa -A6 -B4 -w -P x.pm
nrczt promote 0) 0  1) 0  2) 0  3) 0  4) 0  5) 0  6) 0    z_links) 0  t_links) 0  g_links) 0
nrczt search
vt chains) 0  vs chains) 0  ve chains) 0  nrc[0] exits) 0  nrczt 0) 0  nrczt 1) 0  nrczt 2) 0  nrczt 3) 0  nrczt 4) 0 
niceloop search
niceloop exits 0) 0/0  1) 0/0  2) 0/0  3) 0/0  4) 0/0  5) 0/0  6) 0/0  7) 0/0  8) 0/0  9) 0/0


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

Postby champagne » Sun Mar 01, 2009 9:38 pm

Hi Paul,

Thanks for comments, it makes your presentation quite clear.
I will on my side add comments to your post.

PIsaacson wrote:The results all show that ALSs are commonly found in most every puzzle.
I think it's just a matter of how far into the solution process one wants/needs to go in order to take advantage of them.


For sure they are there. Generally about 200 ALS. This is somehow a concern, but the best are generally the short ones, so a player can work with a reduced set of ALS.

PIsaacson wrote:In my first attempt at ALS chains, I placed that method after other things such as XY chains, nice loops, 3d-medusa etc.
By the time the ALS engine was invoked, most of the eliminations it might have found had already been covered by the other methods,
so I wasn't very impressed with their "performance".


Same experience, especially after I entered AHS/AC=ALS links and AC choices, but my conclusion has been to erase the code dedicated to ALS links.


PIsaacson wrote:This didn't cause me concern until I started investigating SDCs and their relative frequency.
Some maintained that they were rare, but I found that if I scheduled SDCs/ALSs earlier, they started popping up fairly often.


I have to confess that I never studied SCDs as such. It comes differently. I never tried to see how.

PIsaacson wrote:As for bi-value/location pairs:
I still think the ALS engine should completely subsume XY chains and I'm really close.
Just a few weird edge cases remain that I need to investigate.

If you are not considering group bi values, you are likely right, but as I already said, bi values (including groups) is so simple to handle that I would not give the preference to ALS chains.


PIsaacson wrote:But, I still haven't figured out how to effectively use AHSs in ALS chains.


It comes thru weak links created in the AC/AHS working exactly as a cell. (AC is a short for Almost Cell).
PIsaacson wrote:I'm following your suggestion/recommendation that I always consider them in pairs, but if I defer the AHS processing after the ALS processing side,
it's like I'm going through a tremendous amount of effort (computer time that is) for almost no additional eliminations. More work to do.,,


Nothing to add to above comments

PIsaacson wrote:I'm still reading you web pages on full tagging, so I'm by no means certain of the following:
It looks like your level 1 processing is very powerful - similar to 3d-medusa???
I know that when I execute my 3d-medusa before ALS chains, it really reduces the likelihood of the ALS engine finding anything.
Same thing if I allow nice loops to run first, or my nrczt-chains.
Even XY chains messes things up for me because I've implemented Denis Berthier's hXYzt as well as nrczt chains.


I don't know exactly what you put below the word Medusa 3D. For me, it includes Nice loops and XY chains.
When I started tagging end of 2005, I was very close to Medusa 3. I added in the first quarter of 2006 groups bi values and this makes a true breakthrough.

I end this post with your example. I submitted it to the solver and I got a very short answer.

Code: Select all
12.456..94.6......7.9......2.751469.641938..2.95..2..4.6.2..8..572....3..1....... puzzle 1 x.pm
-> row 1  digit 7 in box 3
-> row 5  digit 7 in box 6
-> column 9  digit 7 in box 9
-> row 8  digit 8 in box 8
SwordFish   digit 8 columns 138 rows 169

first tagging

1     2    3a8A  |4     5      6       |3A7a   7A8a    9     
4     358  6     |1378  2789   1379    |1235   125     1358   
7     358  9     |138   28     13      |12345  12456   13568
--------------------------------------------------------------
2     3a8A 7     |5     1      4       |6      9       3A8a   
6     4    1     |9     3      8       |5a7A   5A7a    2     
3A8a  9    5     |67    67     2       |1A3a   1a8A    4     
--------------------------------------------------------------
39    6    34    |2     479    13579   |8      145     157o   
5     7    2     |168   4689   19      |149    3       16   
38A9  1    348a  |367   4679   3579    |2459   2456    567   

3r6c7.a  3r1c7.A <3>r23c7

tagging refreshed

1   2   38  |4    5    6     |37     78     9     
4   358 6   |1378 2789 1379  |125    125    1358   
7   358 9   |138  28   13    |1245   12456d 1356D8
--------------------------------------------------
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  13579 |8      145    157   
5   7   2   |168  4689 19    |149n   3      1X6x   
389 1   348 |367  4679 3579  |2h459N 2H456D 567   

[]6r9c8.D - 6r8c9.x = 1r8c9.X - 1r8c6 = 9r8c6 - 9r8c7 = 9r9c7.N - 2r9c7.h = 2r9c8.H - 6r9c8.D


game over

I see nothing special in that chain. I did not check, but may-be the first step could be avoided.
champagne
2017 Supporter
 
Posts: 5677
Joined: 02 August 2007
Location: France Brittany

Postby PIsaacson » Mon Mar 02, 2009 2:14 am

Champagne,

The point isn't to solve the puzzle, but rather to show how many ALSs exist. My full solver likewise clears the example with a single hXYzt chain followed only by naked/hidden singles:
Code: Select all
Puzzle: 12.456..94.6......7.9......2.751469.641938..2.95..2..4.6.2..8..572....3..1....... puzzle 1 x.pm

 1         2         38       |4         5         6        |37        78        9
 4         358       6        |1378      2789      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       13579    |8         145       157
 5         7         2        |168       489       19       |149       3         16
 389       1         348      |367       4679      3579     |2459      2456      567

do_xychains - reducing r8c9.<16> by <1>
do_xychains - xyt-whip[10] 6=[r8c9]=1=[r8c6]=9=[r8c7]=4=[r7c8]=5=[r5c8]=7=[r1c8]=8=[r1c3]=3=[r7c3]=4=[r7c5]=7=[r7c9]=1


But that's not very interesting from an ALS perspective, so please keep in mind that these posting are just demonstrations of how many ALSs are present at early stages of the solution.

One thing I forgot to mention is that for all the collection statistics, I'm using "-A4 -B4" which limits the engine to ALSs size 2-4 and chains of length 6 or less. This is really not a very in-depth examination, but using something like "-A9 -B6" is too slow and I reserve in-depth analysis for single puzzles.

BTW, I'm in the middle of coding a full-tagging engine using my 3d-medusa as a starting point. I just added AC weak links and, it made a significant difference just as you stated. I'm dubbing it the FTL engine because it's so much faster at finding eliminations than my recursive tree walking engines such as ALS and nice loops etc. I'm designing level 2 based on the current ALS engine and ALS/AHS pairs. Wish me luck...

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

Postby champagne » Mon Mar 02, 2009 1:17 pm

PIsaacson wrote:Wish me luck...

Cheers,
Paul


No need for any wish, I am sure you will succeed. I could send you my code, but I am not sure it would help, but in case, I can do it.

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

PreviousNext

Return to Advanced solving techniques