The New Sudoku Players' Forum

by **PIsaacson** » Sun Feb 15, 2009 3:00 am

Recently, I decided to re-code my ALS chaining method to simplify the code and to add an improved depth-first tree walk algorithm for finding pontentially very long ALS chains. During this process, I discovered by accident, that I had allowed for "overlapping" ALSs:

Form (1) occurs when an adjacent left-hand (parent) and right-hand (child) ALS share cells.
Form (2) occurs when a chain is formed and non-adjacent members of the chain share cells.

Form (1) is valid as long as the shared cells do not contain any RCD(s).
Form (2) is valid provided the start ALS and the end ALS are not identical (loop). This is still under investigation.

This fortuitous bug opened up ALS chains and provided many more potential eliminations due to these new overlapping possibilities. Using the Royle17 (36628) puzzle set as a standard collection to test against, my new ALS engine reports:

Code: Select all: 34933 normal ALSs, 18391 overlapping ALSs, 1484 cannibalistic ALSs, 2830 overlapping/cannibalistic ALSs, 348 SDCs and 8 cannibalistic SDCs.

In discussion with ronk and hobiwan, I have to qualify the SDC categorizations. I assumed that all SDCs could be derived as dual-link ALS chains, but my code to classify one as an SDC is defective. As a result, anything reported by the engine as an SDC should just be considered a "normal" dual-linked ALS.

The following is from the solution log for Royle17 #40:

Code: Select all: Royle17 #40 after simple eliminations: 8 B27-9 A29 |4 6 3 |79 1 5 A46 B457-6 57-6 |9 1 2 |67 8 3 3 AB69 1 |7 8 5 |69 4 2 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 8 4 |2 5 6 |3 9 1 9 B56 56 |1 3 7 |4 2 8 1 23 23 |8 9 4 |5 7 6 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 5 B79 8 |6 4 1 |2 3 79 2 34-9 39 |5 7 8 |1 6 49 46 1 67 |3 2 9 |8 5 47 do_alschains - graph contains 104 vertices and 1388 edges do_alschains - reducing r2c2.<4567> by <6> dual do_alschains - reducing r2c3.<567> by <6> dual do_alschains - reducing r1c2.<279> by <9> dual do_alschains - reducing r8c2.<349> by <9> dual do_alschains - sdc+c[2x6/6] b1x348.<2469> +24+ r12357c2.<245679>

Not an SDC, but truly a bizzare dual-linked overlapping, cannibalistic dual-linked ALS. I can't explain the candidate eliminations is terms of subset counting, especially the r1c2 <> 9 and r2c2 <> 6, but these types of ALSs are "all over the place" and all the eliminations are valid. Another example:

Code: Select all: Royle17 #11551 after simple eliminations: 2 6 7 |8 5 4 |3 9 1 1 39 8 |39 A67 67 |4 2 5 5 39 4 |1 23-9 239 |6 8 7 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 4 7 2 |5 B38-9 B39 |89 1 6 9 1 3 |B47 B468-7 68-7 |78 5 2 8 5 6 |2 AB79 1 |79 4 3 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 4 1 |6 A89 5 |2 3 89 6 8 5 |39 234-9 239 |1 7 49 3 2 9 |47 1 78 |5 6 48 do_alschains - graph contains 123 vertices and 1520 edges do_alschains - reducing r5c5.<4678> by <7> dual do_alschains - reducing r5c6.<678> by <7> dual do_alschains - reducing r3c5.<239> by <9> dual do_alschains - reducing r4c5.<389> by <9> dual do_alschains - reducing r8c5.<2349> by <9> dual do_alschains - sdc+c[2x6/6] r267c5.<6789> +68+ b5x23458.<346789>

The following solution logs demonstrate the frequency of overlapping ALSs

Code: Select all: Royle17 #14464 after simple eliminations: 78 1 2 |3 4 9 |6 578 57 4 6 357 |57 1 578 |378 2 9 378 9 357 |2 578 6 |378 14 14 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 1 3 8 |9 6 57 |4 57 2 5 7 4 |1 3 2 |9 6 8 6 2 9 |8 57 4 |57 13 13 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 37 58 37 |4 2 58 |1 9 6 2 458 6 |57 9 1 |578 34578 3457 9 458 1 |6 578 3 |2 4578 457 do_alschains - graph contains 133 vertices and 814 edges do_alschains - reducing r8c9.<3457> by <5> do_alschains - als[3x3/4] r1c9.<57> -7- r23c7.<378> -8- r8c47.<578> do_alschains - reducing r2c3.<357> by <5> do_alschains - reducing r3c5.<578> by <5> do_alschains - als+[3x3/3] r2c4.<57> -7- b8x34.<578> -8- r2c46.<578> do_alschains - reducing r8c8.<34578> by <7> do_alschains - reducing r9c8.<4578> by <7> do_alschains - als+[3x4/4] r4c8.<57> -5- r236c7.<3578> -8- r14c8.<578> do_alschains - reducing r3c3.<357> by <3> do_alschains - als+[4x4/4] r27c3.<357> -5- r2c4.<57> -7- b8x34.<578> -8- r2c346.<3578> do_alschains - ending with 6 updates 49 total solved do_pinnings - setting r3c3 = d5 hidden single do_pinnings - ending with 1 updates 50 total solved 78 1 2 |3 4 9 |6 578 57 4 6 37 |57 1 578 |378 2 9 378 9 5 |2 78 6 |378 14 14 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 1 3 8 |9 6 57 |4 57 2 5 7 4 |1 3 2 |9 6 8 6 2 9 |8 57 4 |57 13 13 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 37 58 37 |4 2 58 |1 9 6 2 458 6 |57 9 1 |578 3458 347 9 458 1 |6 578 3 |2 458 457 do_alschains - graph contains 131 vertices and 1018 edges do_alschains - reducing r3c7.<378> by <7> do_alschains - als+[3x4/4] r3c5.<78> -8- r2c346.<3578> -3- r3c15.<378> do_alschains - reducing r2c7.<378> by <7> do_alschains - als[3x3/3] r6c7.<57> -5- r36c5.<578> -8- r2c46.<578> do_alschains - reducing r8c7.<578> by <7> do_alschains - als[4x5/6] r6c7.<57> -5- r36c5.<578> -7- r9c258.<4578> -5- r3689c9.<13457> do_alschains - reducing r8c2.<458> by <5> do_alschains - als[4x6/6] r7c2.<58> -8- r47c6.<578> -7- r34689c8.<134578> -8- r8c47.<578> do_alschains - reducing r8c9.<347> by <7> do_alschains - als+[3x4/4] r8c4.<57> -5- r2c347.<3578> -8- r8c47.<578> do_alschains - reducing r1c1.<78> by <7> do_alschains - als[4x4/4] r1c89.<578> -8- r236c7.<3578> -5- r36c5.<578> -8- b1x67.<378>

Code: Select all: Royle16 #4858 after simple eliminations: 49 7 1 |49 6 3 |5 2 8 8 3 5 |1 2 479 |6 79 479 2 6 49 |8 5 479 |479 13 13 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 3 2 7 |5 9 8 |1 4 6 459 149 6 |3 147 14 |8 579 2 459 149 8 |2 147 6 |79 3579 35 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 5 2 |6 14 149 |3 8 49 6 49 3 |479 8 2 |479 15 15 1 8 49 |479 3 5 |2 6 479 do_alschains - graph contains 138 vertices and 1010 edges do_alschains - reducing r9c9.<479> by <4> do_alschains - als+[4x3/4] r7c9.<49> -9- r57c6.<149> -4- r2c68.<479> -7- r27c9.<479> do_alschains - reducing r3c6.<479> by <4> do_alschains - als[4x3/4] b2x16.<479> -7- r2c89.<479> -4- r7c9.<49> -9- r57c6.<149> do_alschains - ending with 2 updates 49 total solved 49 7 1 |49 6 3 |5 2 8 8 3 5 |1 2 479 |6 79 479 2 6 49 |8 5 79 |479 13 13 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 3 2 7 |5 9 8 |1 4 6 459 149 6 |3 147 14 |8 579 2 459 149 8 |2 147 6 |79 3579 35 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 5 2 |6 14 149 |3 8 49 6 49 3 |479 8 2 |479 15 15 1 8 49 |479 3 5 |2 6 79 do_alschains - graph contains 143 vertices and 1220 edges do_alschains - reducing r6c2.<149> by <9> do_alschains - als[4x6/6] r8c2.<49> -4- b9x49.<479> -9- r7c59.<149> -1- r6c15789.<134579> do_alschains - reducing r8c4.<479> by <9> do_alschains - als[3x3/3] r8c2.<49> -4- r9c39.<479> -7- r19c4.<479> do_alschains - reducing r5c5.<147> by <1> do_alschains - als[4x3/4] r5c26.<149> -9- r8c2.<49> -4- b9x49.<479> -9- r7c59.<149> do_alschains - ending with 3 updates 49 total solved 49 7 1 |49 6 3 |5 2 8 8 3 5 |1 2 479 |6 79 479 2 6 49 |8 5 79 |479 13 13 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 3 2 7 |5 9 8 |1 4 6 459 149 6 |3 47 14 |8 579 2 459 14 8 |2 147 6 |79 3579 35 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 5 2 |6 14 149 |3 8 49 6 49 3 |47 8 2 |479 15 15 1 8 49 |479 3 5 |2 6 79 do_alschains - graph contains 150 vertices and 1482 edges do_alschains - reducing r2c6.<479> by <7> do_alschains - reducing r3c7.<479> by <7> do_alschains - als+[4x3/3] b2x19.<479> -4- r89c4.<479> -9- r9c3.<49> -4- r3c36.<479> do_alschains - reducing r3c7.<49> by <9> do_alschains - als[4x3/3] r3c36.<479> -4- r9c3.<49> -9- r8c24.<479> -4- r68c7.<479>

For those who wish to experiment with these new ALS chains, I've posted my ALS engine on a hosting site for downloading. It's a command line batch solver, so there's no elegant GUI and the solution log is (as shown above) less than pretty. But it's functional and free, so please let me know if you find an example puzzle that produces invalid eliminations. I've tested against massive collections (top50000, top10000, royle17) and have not hit a single incorrect reduction, but I can't prove why overlap/cannibalism should or should not be legal. I'm hoping that someone out there with advanced math/logic can offer a proof.

by **PIsaacson** » Sun Feb 15, 2009 3:04 am

I uploaded a version of my current code for you if you want to download:

http://pisaacson.fileave.com/Bernhard/makefile.txt
http://pisaacson.fileave.com/Bernhard/sudoku.cpp
http://pisaacson.fileave.com/Bernhard/sudoku.h
http://pisaacson.fileave.com/Bernhard/sudoku.exe

I use the cygwin environment, so if you don't have that installed, you won't be able to recompile. I used to have a Visual Studio setup, but abandoned that years ago when I switched to using the cygwin/gnu g++ compiler.

You can execute against a single puzzle in Pencil Markup mode using the -P switch, or against a collection. I've stripped the code to just basic constraint processing (naked/hidden singles, row/col/box interactions and naked/hidden subsets + basic fish-2/3/4) plus the full ALS engine. SDC filtering is broken, so I just plugged in an old chunk of code, so ignore the SDC tagging of dual linked ALSs.

To execute against a single PM

sudoku -bv -P <filename> > <logfile>

To execute against a collection

sudoku -bv <filename> > <logfile>

eg. sudoku -bv -A9 -B0 /downloads/royle17.txt > solution.log

Options -An where n = 2-9 sets the max ALS size to find
-Bn where b = 0-16 sets the max ALS chain size

-B0 will attempt to locate just ALS-XY sets (chain length 2)
-B1 will locate ALSs chain length < 4
-B2 will locate ALSs chain length < 5

I know, the number seems off, but I needed to differentiate between an ALS pass and an SDC pass. I'm still working on this.

Use output redirection for the massive amount of trace log output that it will generate. Hopefully, the solution log is pretty self-explanatory. It's crude compared to your solver, but I was going for a few massively powerful engines rather than having many techniques. As a result, the ALS engine will attempt to locate ALL possible ALS eliminations within the limits of the -An and -Bn options. I have a "quick" exit strategy that can be enabled with -e and -En in order to stop after the nth bi-value/bi-location reduction to a naked/hidden single. I don't often use this except for really massive collections such as the top50000 which takes hours to process.

Assuming you have cygwin (or equivalent posix-like binaries)

grep "als\[" <solution.log> | wc - count all standard ALSs
grep "als+\[" <solution.log> | wc - count all overlapping ALSs
grep "alsc\[" <solution.log> | wc - count all cannibalistic ALSs
grep "als+c\[" <solution.log> | wc - count all overlapping cannibalistic ALSs

[edit] SDC filtering is retracted.

If you run "sudoku -bv -A9 -B8" (or some -Bn > 4) be prepared to wait a really really long time for the ALS engine to execute a depth first search to n+2 levels requested with the -B flag. I only do this on individual puzzles and usually start with -B4 and work up as desired.

sudoku -h will list the options, but they are mostly to remind me of current flags/defaults, so don't expect much help from the help.

Cheers,
Paul

[edit] I refreshed the code and executable so that it is now compiled with the mingw -mno-cygwin option and the cygwin1.dll is no longer required. This also converted the output to MS cr/lf, so it can go directly into notepad etc.

by **daj95376** » Sun Feb 15, 2009 5:47 am

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

Code: Select all: Royle17 #40 after simple eliminations: XY-Loop a-b-c-d-e-a +--------------------------------------------------------------+ | 8 27-9 29 | 4 6 3 | 79 1 5 | | e46 457-6 57-6 | 9 1 2 | 67 8 3 | | 3 a69 1 | 7 8 5 | 69 4 2 | |--------------------+--------------------+--------------------| | 7 8 4 | 2 5 6 | 3 9 1 | | 9 56 56 | 1 3 7 | 4 2 8 | | 1 23 23 | 8 9 4 | 5 7 6 | |--------------------+--------------------+--------------------| | 5 b79 8 | 6 4 1 | 2 3 79 | | 2 34-9 39 | 5 7 8 | 1 6 49 | | d46 1 c67 | 3 2 9 | 8 5 47 | +--------------------------------------------------------------+ # 26 eliminations remain

Code: Select all: Royle17 #11551 after simple eliminations: XY-Loop a-b-c-d-e-a +--------------------------------------------------------------+ | 2 6 7 | 8 5 4 | 3 9 1 | | 1 39 8 | 39 67 67 | 4 2 5 | | 5 39 4 | 1 23-9 239 | 6 8 7 | |--------------------+--------------------+--------------------| | 4 7 2 | 5 38-9 39 | 89 1 6 | | 9 1 3 | b47 468-7 68-7 | 78 5 2 | | 8 5 6 | 2 a79 1 | 79 4 3 | |--------------------+--------------------+--------------------| | 7 4 1 | 6 e89 5 | 2 3 89 | | 6 8 5 | 39 234-9 239 | 1 7 49 | | 3 2 9 | c47 1 d78 | 5 6 48 | +--------------------------------------------------------------+ # 34 eliminations remain

by **PIsaacson** » Sun Feb 15, 2009 5:58 am

FYI - for those who have a cygwin environment or want to cross check results...

The solver includes my DLX final resort method. Any puzzle that cannot be solved using just the default options (I call them RCB after my original row/col/box simple constraint processing) will be completed using Knuth's dancing links (DLX). Any unsolved puzzle will be flagged as DLX and the statistics will indicate that do_dlx was invoked. It can be invoked by "sudoku -bv -X <puzzles>" to bypass all other methods (you only have do_pinnings/do_restrictions/do_subsets/do_alschains). I use the following shell script to cross check collections using this technique:

Code: Select all: echo Timing RCB $* time sudoku $* > /temp/log1 echo Timing DLX $* for i in $* do if [ -f $i ] then x="$x -X" fi x="$x $i" done time sudoku $x > /temp/log2 echo Comparing output log1 log2 grep "^ [1-9] [1-9] [1-9]\| [1-9] [1-9] [1-9]\| [1-9] [1-9] [1-9]" /temp/log1 > /temp/log1.sol grep "^ [1-9] [1-9] [1-9]\| [1-9] [1-9] [1-9]\| [1-9] [1-9] [1-9]" /temp/log2 > /temp/log2.sol diff -w /temp/log1.sol /temp/log2.sol > /temp/log3 egrep -v '(solution|---|[0-9]*[cd][0-9]*)' /temp/log3 echo Ensuring that RCB solved all $* puzzles egrep DLX /temp/log1 > /dev/null && echo !!! Some puzzles were not solved by RCB !!!

Save this as bm.sh and you can pass whatever options as in:

Code: Select all: bm -bv -A9 -B2 /downloads/royle17.txt

The output automatically goes into /temp/log1 for the ALS pass and /temp/log2 for the DLX pass. The solution logs are filtered for just solutions into /temp/log1.sol and /temp/log2.sol and then diff'ed into /temp/log3 for validation. The egrep -v command will display various parts of the solutions that don't match. This indicates an error, so if you see lines like "123 | 456 | 789" you've found a puzzle that has caused a false elimination from the ALS engine. Please let me know. I'm still looking for this. I use the bash shell, so make sure you're not using csh or a non-korn based shell, or better yet, add the #!/bin/bash 1st line shell script option. Pre-create a /temp directory if it doesn't already exist.

Good hunting!
Paul

by **PIsaacson** » Sun Feb 15, 2009 6:15 am

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. My XY-chaining method is based on Denis Bethier's hxyzt theory, so it doesn't find loops. I want my ALS engine to produce XY chains since they are, in fact, ALS chains, but it currently doesn't do this. More work...

by **DonM** » Sun Feb 15, 2009 6:22 am

Paul, you might find this thread of particular interest. While I've had it in my files for some time, for some reason it doesn't come up with a Google search, but some sleuthing in the Player's archives indicated that it's still very much there. It is almost the definitive discussion on overlapping ALSs (courtesy of Myth Jellies):

http://forum.enjoysudoku.com/viewtopic.php?t=4863

by **ronk** » Sun Feb 15, 2009 6:30 am

PIsaacson wrote:I assumed that all SDCs could be derived as dual-link ALS chains, but my code to classify one as an SDC is defective. As a result, anything reported by the engine as an SDC should just be considered a "normal" dual-linked ALS.

The following is from the solution log for Royle17 #40:
Code: Select all
Royle17 #40 after simple eliminations: 8 B27-9 A29 |4 6 3 |79 1 5 A46 B457-6 57-6 |9 1 2 |67 8 3 3 AB69 1 |7 8 5 |69 4 2 ------ ------ ------+------ ------ ------+------ ------ --- 7 8 4 |2 5 6 |3 9 1 9 B56 56 |1 3 7 |4 2 8 1 23 23 |8 9 4 |5 7 6 ------ ------ ------+------ ------ ------+------ ------ --- 5 B79 8 |6 4 1 |2 3 79 2 34-9 39 |5 7 8 |1 6 49 46 1 67 |3 2 9 |8 5 47

Not an SDC, but truly a bizzare dual-linked overlapping, cannibalistic dual-linked ALS.

You were looking for SDCs and seem to have found some hidden SDCs as well. In this case, candidates <57> in b1 and candidates <234> in c2 are covered by cells r1268c2 and r2c3. The hidden "core" set is <2457> in r12c2, the hidden box set is <57> in r2c3, and the hidden row/col set is <234> in r68c2.

royle17 #40 hidden SDC

PIsaacson wrote:Another example:
Code: Select all
Royle17 #11551 after simple eliminations: 2 6 7 |8 5 4 |3 9 1 1 39 8 |39 A67 67 |4 2 5 5 39 4 |1 23-9 239 |6 8 7 ------ ------ ------+------ ------ ------+------ ------ --- 4 7 2 |5 B38-9 B39 |89 1 6 9 1 3 |B47 B468-7 68-7 |78 5 2 8 5 6 |2 AB79 1 |79 4 3 ------ ------ ------+------ ------ ------+------ ------ --- 7 4 1 |6 A89 5 |2 3 89 6 8 5 |39 234-9 239 |1 7 49 3 2 9 |47 1 78 |5 6 48

In this case, candidates <68> in b5 and candidates <234> in c5 are covered by cells r3458c5 and r5c6. The hidden "core" set is <3468> in r45c5, the hidden box set is <68> in r5c6, and the hidden row/col set is <234> in r38c5.

royle17 #11551 hidden SDC

I would like to see several more of your "sdc+c[ ... ]" chains to see if hidden SDCs appear there as well.

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.

[edit: 1) added hidden SDC images; 2) shrink pencilmarks]

by **PIsaacson** » Sun Feb 15, 2009 7:52 am

DonM wrote:Paul, you might find this thread of particular interest. While I've had it in my files for some time, for some reason it doesn't come up with a Google search, but some sleuthing in the Player's archives indicated that it's still very much there. It is almost the definitive discussion on overlapping ALSs (courtesy of Myth Jellies):

http://forum.enjoysudoku.com/viewtopic.php?t=4863

Don,

Thanks a million for this pearl. A great read and I pay homage to Myth Jellies' logic. He opened up ALS chaining back in '06 and it's taken me this long to catch up with such past discoveries. I deliberately prune adjacent ALSs whose cells are proper subsets, but he has examples that indicate even this is permissible. Back to the drawing board for ALS chaining. Hopefully we can define a set of rules that catches ALL possible ALS chains - at least for computer programs. This stuff is way beyond my manual ability...

by **PIsaacson** » Sun Feb 15, 2009 12:06 pm

I hate to contradict Myth Jellies' overlapping rules, but I modified my ALS engine to allow adjacent ALSs to have overlapping cells with RCD(s) candidates, and this induced many invalid eliminations. I must have missed something in the fine print or some condition/qualifier. I have been cross-checking the exemplar PMs listed in the CoALS thread, but without much success. Can anyone else out there with ALS chaining confirm whether or not RCDs can be present in shared cells? If so, under what conditions? I don't understand the CoALS proof, but SDCs boggle my mind as well, so take that into consideration.

by **Allan Barker** » Sun Feb 15, 2009 2:21 pm

PIsaacson wrote:
Code: Select all
Royle17 #11551 after simple eliminations: 2 6 7 |8 5 4 |3 9 1 1 39 8 |39 A67 67 |4 2 5 5 39 4 |1 23-9 239 |6 8 7 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 4 7 2 |5 B38-9 B39 |89 1 6 9 1 3 |B47 B468-7 68-7 |78 5 2 8 5 6 |2 AB79 1 |79 4 3 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 7 4 1 |6 A89 5 |2 3 89 6 8 5 |39 234-9 239 |1 7 49 3 2 9 |47 1 78 |5 6 48 do_alschains - graph contains 123 vertices and 1520 edges do_alschains - reducing r5c5.<4678> by <7> dual do_alschains - reducing r5c6.<678> by <7> dual do_alschains - reducing r3c5.<239> by <9> dual do_alschains - reducing r4c5.<389> by <9> dual do_alschains - reducing r8c5.<2349> by <9> dual do_alschains - sdc+c[2x6/6] r267c5.<6789> +68+ b5x23458.<346789>

Hi, PIssacson,

I'm not sure how helpful it will be but I took a look at the base/cover set logic for your overlapping, cannibalistic dual-linked ALS. (ALS collision?? )

The 7 cells (base sets) from the 2 ALS cannot be covered by 7 cover sets and can't form a true SDQ, as I understand them. They can be covered by 8 cover sets so, as a general rule, any candidate that sees 2 cover sets can be eliminated. However, in this case, the 2 ALS are interconnected in a way that completely solves all 7 cells. (Diagram 1, 7 base/8 cover set full solution). Much of this solution is cannibalistic.

There is also a 5 base, 6 cover set combined (A)ALS that eliminates the 9s from column 5. Elimination of 9r34c5 would then set off a cannibalistic chain reaction that leads to the full solution. (diagram 2)

What I thought was interesting is how diagram 2 eliminates the 8s and 9s because neither can be contained in 2 cover sets. In this case, (from triplet and rank rules) 7r6c5 forms a triplet that lowers the rank of cover sets 89c5 to 0 and eliminates the 8s and 9s. (Black shaded in diagram 3).

It would be interesting to see how this relates to more conventional ALS logic. However, I'm not so sure how helpful this is from a programming point of view.

1. Diagram 1, 7 base/8 cover set full solution.
2. Diagram 2, 5 base/6 cover set elimination
2. Diagram 3, 3D view of 5 base/6 cover set elimination, rank 0 shaded black

Diagram 1: 17 Nodes, Raw Rank = 1 (linksets - sets)
7 Sets = {5N4 24567N5 4N6}
8 Links = {6789c5 3479b5}
13 Eliminations, 7 Assignments -->
r3468c5<>9, r5c456<>7, r47c5<>8, r5c5<>46, r2c5<>7, r4c6<>3
r2c5=6, r4c5=3, r4c6=9, r5c4=4, r5c5=8, r6c5=7, r7c5=9

Diagram 2&3 12 Nodes, Raw Rank = 1 (linksets - sets)
5 Sets = {5N4 2567N5}
6 Links = {4r5 6789c5 7b5}
4 Eliminations, 0 Assignments --> r348c5<>9, r4c5<>8

PS, I assume that your cygwin environment is based on mingw??

by **PIsaacson** » Sun Feb 15, 2009 3:24 pm

Allan,

I have GOT to spend more time studying your subset cover/link set logic stuff. I've browsed your home page and drooled over the 3d images. Now I have to ask: Do you use a known/available 3d graphing package for those diagrams? If so, what??? I don't understand it, but man is that 3rd jpeg cool looking!

I use cygwin/mingw, but I haven't compiled with the -mno-cygwin option since I downloaded gcc-4.3.3. I just tested using the old g++ 3.4.4 compiler released with the standard cygwin installation and it works fine with a few source/header corrections. If you want a version that doesn't depend on the cygwin1.dll, let me know and I'll update the download files with the corrected #ifdef cygwin in the *.h and *.cpp files along with a new makefile. That's about as equivalent to pure mingw32 as I can get.

My turn...

Does your base/cover set logic provide some insight as to whether or not all such overlap is legal, or does it need to be investigated case-by-case? Of specific concern now is whether or not RCDs can belong in the overlapping cells of adjacent ALSs. Your excellent work on the RCD adjacency restrictions gives me hope that you can definitively state what's what here as well.

Cheers,
Paul

by **PIsaacson** » Mon Feb 16, 2009 10:45 am

Some more examples of dual-linked overlapping cannibalistic ALSs

Code: Select all: ruud_top10000 #2916 ..9.7.....826..1..1....2.8.........854...7.........5......6......83....7..3.18.69 puzzle 2916 /downloads/ruud_top10000.txt After elementary constraint processing 346 356 9 |8 7 1 |36 2345 23456 347 8 2 |6 3459 3459 |1 79 345 1 3567 45 |459 3459 2 |79 8 3456 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 239 239 167 |12459 23459 34569 |679 12479 8 5 4 16 |129 8 7 |369 1239 1236 8 239 167 |1249 2349 3469 |5 12479 1246 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 2479 12579 45 |24579 6 459 |8 135 135 2469 12569 8 |3 2459 459 |24 15 7 247 257 3 |2457 1 8 |24 6 9 do_alschains - graph contains 229 vertices and 888 edges do_alschains - reducing r1c8.<2345> by <3> dual do_alschains - reducing r1c9.<23456> by <3> dual do_alschains - reducing r2c1.<347> by <4> dual do_alschains - reducing r3c2.<3567> by <5> dual do_alschains - reducing r1c9.<2456> by <6> dual do_alschains - als[2x4/4] r1c7.<36> -36- b1x129.<3456> 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>

Code: Select all: ruud_top10000 #8192 6.....5....5.7....1....9.765..34.8.............2.57..143.9....8....2.4....9.....3 puzzle 8192 /downloads/ruud_top10000.txt After elementary constraint processing 6 2789 378 |1248 138 1248 |5 123489 249 2389 28 5 |12468 7 12468 |1239 12348 24 1 248 348 |5 38 9 |23 7 6 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 5 1679 167 |3 4 126 |8 269 279 378 14678 134678 |1268 9 1268 |2367 23456 2457 389 468 2 |68 5 7 |369 346 1 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 4 3 167 |9 16 15 |1267 1256 8 78 15678 1678 |178 2 3 |4 1569 579 278 125678 9 |1478 168 1458 |167 156 3 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>

Elementary constraint processing (term borrowed from Denis Bethier's "The Hidden Logic of Sudoku") consists in my solver of:

1) do_pinnings - naked/hidden singles
2) do_restrictions - row/column/box interactions
3) do_subsets - naked/hidden locked sets size 2-4 plus simple fish size 2-4 (x-wing/swordfish/jellyfish)

This corresponds precisely with Hobiwan's outstanding HoDoKu "Full House ... Jellyfish" steps and the equivalent in Ruud's SudoCue "Full House ... Jellyfish" solving techniques. HoDoKu includes a Sue de Coq step as well as an ALS XY-chains step. SudoCue also has an SDC technique but the ALS chaining seems to be limited. I'm not familiar with other available solvers in terms of their ALS/SDC capabilities, so please let me know of others that provide ALS chaining. I can use all the cross-checking I can get...

by **PIsaacson** » Mon Feb 16, 2009 3:17 pm

Another example of dual-linked overlapping cannibalistic ALSs from the top50000 collection

[edit] Removed Top50000 # 16933 - duplicate of Top10000 #8192 (thanks Ron!)

Code: Select all: Top50000 #35644 after elementary constraint processing ..6....84.....45.......8..1.5..923....36.59....217..6.2..4.......87.....31....7.. puzzle 35664 /downloads/top50000/top50000.sdm 59 39 6 |359 1 7 |2 8 4 1789 23789 179 |239 6 4 |5 379 39 4579 23479 579 |2359 25 8 |6 379 1 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 6 5 14 |8 9 2 |3 14 7 178 78 3 |6 4 5 |9 12 28 489 489 2 |1 7 3 |48 6 5 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 2 679 579 |4 358 169 |18 359 3689 459 469 8 |7 235 169 |14 2359 2369 3 1 459 |25 258 69 |7 2459 2689 do_alschains - graph contains 216 vertices and 1702 edges 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> do_alschains - reducing r1c4.<359> by <3> dual do_alschains - reducing r2c2.<238> by <3> dual do_alschains - reducing r3c2.<234> by <3> dual do_alschains - als+[2x7/7] r168c1.<4589> +48+ b1x124679.<1345789>

by **Allan Barker** » Mon Feb 16, 2009 3:47 pm

Hi Paul,

PIsaacson wrote:Do you use a known/available 3d graphing package for those diagrams? If so, what???

No,

I am using a set of custom 3D/2D drawing routines that I adapt to different applications as needed. Although they are not in library form, they are fairly simple

. I could probably build a standalone example for 3D primitives pixel. line, plate, etc to show how it is done. Everything is written into a memory buffer that is then pasted on screen or can be put in a file.

PIsaacson wrote:Does your base/cover set logic provide some insight as to whether or not all such overlap is legal, or does it need to be investigated case-by-case? Of specific concern now is whether or not RCDs can belong in the overlapping cells of adjacent ALSs. Your excellent work on the RCD adjacency restrictions gives me hope that you can definitively state what's what here as well.

I looked at Myth's elagant coALS rule and his three examples. Although I am not very expert at such thinks, it does look like there is a consistent picture in terms of base/cover sets. However, I'm not so clear on how to relate the RCDs. I tried to make a couple of examples but in the end the logic no longer qualified as a coALS. Your question may be a bit broader than this anyway.

Do you have an example or two of RCDs in the overlap cells? I suppose it is also possible to have two overlap ALS that share an RCD that is not in the overlap. (?)

Update, as I post this is, I see your latest examples. Maybe you could point out a few that might prove fruitful to look at?

Allan

by **PIsaacson** » Tue Feb 17, 2009 3:18 am

Allan,

I have two types of overlap:

1) Shared cells between adjacent ALSs in a chain.
2) Shared cells between two intersecting non-adjacent ALSs in a chain.

I have not been able to successfully build chains of type (1) with RCDs in the shared cells. I sent a PM to Myth Jellies asking for clarification of the CoALS rules - specifically the 3rd rule involving "the link out from the non overlap digits...".

I have not bothered to check whether or not type (2) ever involve RCD contributing cells, but I will add that check, re-test some large collections and post the statistics/examples.

Paul

The New Sudoku Players' Forum

ALS chains with overlap/cannibalism

ALS chains with overlap/cannibalism

Re: ALS chains with overlap/cannibalism