The New Sudoku Players' Forum

by **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.

by **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.

by **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?

by **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.

by **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.

by **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.

by **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.

by **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.

by **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

by **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.

by **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

by **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

by **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.

by **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

by **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

The New Sudoku Players' Forum

ALS chains with overlap/cannibalism