ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

ALS chains with overlap/cannibalism

Postby 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.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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.
Last edited by PIsaacson on Mon Feb 16, 2009 1:06 pm, edited 2 times in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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
daj95376
2014 Supporter
 
Posts: 2397
Joined: 15 May 2006

Postby 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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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...
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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
DonM
2013 Supporter
 
Posts: 399
Joined: 13 January 2008

Re: ALS chains with overlap/cannibalism

Postby 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.

Image
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.

Image
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]
Last edited by ronk on Mon Feb 16, 2009 3:36 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Postby 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...
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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

ImageImageImage

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??
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby 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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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...
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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>
Last edited by PIsaacson on Mon Feb 16, 2009 10:00 pm, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby 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
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby 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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Next

Return to Advanced solving techniques