## Sudoku Explainer: Bugs, Quirks and Other Remarks...

Programs which generate, solve, and analyze Sudoku puzzles

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

At least one problem with transposed puzzles arises from the fact that many of the SE techniques restrict their range of operation to the only the sector of pattern discovery. It's just the way it was coded, not a bug, but it makes it sensitive to locality, causing it to miss potential eliminations/assignments due to presentation of candidates.

I've previous stated that the correct way to handle this is to always determine the "range" on a digit by digit basis - and'ing the peers of each cell containing that digit within a pattern to fully assess the "range" of operation. As an example, suppose a pattern contains a digit that is confined to a single cell. Then for that digit, the range of operation includes all 20 potential peers within the same row/col/box. Similarly, any 2 cell digit that is confined to a dual-sector line/box intersection has a range of operation extending to the remaining 7 box and 6 line (row or col) or 13 potential peers. This happens frequently.

As a comparison, I ran all 4 above puzzle presentations though my experimental C++ SE replacement and all 4 rated identically at 4.6/2.0/2.0 and presented identical solution paths (which they should!):
Code: Select all
`1..........21..3...3..4..2..4.3.5.....5.2.6.....6...7..2..7..8...3..89..........4 1         56789     46789    |25789     35689     23679    |4578      4569      56789     456789    56789     2        |1         5689      679      |3         4569      56789     56789     3         6789     |5789      4         679      |1578      2         156789    --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 26789     4         16789    |3         189       5        |128       19        1289      3789      1789      5        |4789      2         1479     |6         1349      1389      2389      189       189      |6         189       149      |12458     7         123589    --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 4569      2         1469     |459       7         13469    |15        8         1356      4567      1567      3        |245       156       8        |9         156       12567     56789     156789    16789    |259       13569     12369    |1257      1356      4          1) r6c1 <= 2    direct hidden pair r4c13.<67>  2) r5c1 <= 3 hidden single in b4  3) r6c9 <= 3 hidden single in b6  4) r6c7 <= 5 hidden single in b6  5) r5c8 <= 4 hidden single in b6  6) r1c7 <= 4 hidden single in b3  7) r2c1 <= 4 hidden single in b1  8) r6c6 <= 4 hidden single in b5  9) r7c3 <= 4 hidden single in b7 10) r8c4 <= 4 hidden single in b8 11) r9c8 <= 3 hidden single in b9 12) r7c6 <= 3 hidden single in b8 13) r1c5 <= 3 hidden single in b2 14) r8c9 <= 2 hidden single in r8 15) r4c7 <= 2 hidden single in b6 16) r9c7 <= 7 hidden single in b9 17) r3c7 <= 8 hidden single in c7 18) r7c7 <= 1 full house in c7 19) r3c9 <= 1 hidden single in b3 20) r4c8 <= 1 hidden single in b6 21) r9c1 <= 8    direct hidden pair r4c13.<67> 22) r5c2 <> 7 locked candidates type 1 (pointing) b5/r5 23) r1c9 <> 9 locked candidates type 1 (pointing) b6/c9 24) r2c9 <> 9 locked candidates type 1 (pointing) b6/c9 25) r4c1 <> 9    naked pair r4c59.<89> 26) r4c3 <> 89   naked pair r4c59.<89> 27) r6c3 <> 1    ur[6]-loop type 2 <89> r4c5 r6c5 r6c2 r5c2 r5c9 r4c9  28) r9c3 <= 1 hidden single in c3 29) r8c5 <= 1 hidden single in b8 30) r5c6 <= 1 hidden single in b5 31) r6c2 <= 1 hidden single in b4 32) r5c4 <= 7 hidden single in b5 33) r1c4 <= 8 hidden single in c4 34) r2c2 <= 8 hidden single in b1 35) r1c6 <= 2 hidden single in b2 36) r6c3 <= 8 hidden single in b4 37) r6c5 <= 9 full house in r6 38) r4c5 <= 8 full house in b5 39) r5c2 <= 9 hidden single in b4 40) r5c9 <= 8 full house in r5 41) r4c9 <= 9 full house in b6 42) r7c1 <= 9 hidden single in b7 43) r9c4 <= 2 hidden single in b8 44) r9c6 <= 9 hidden single in b8 45) r3c4 <= 9 hidden single in b2 46) r7c4 <= 5 full house in c4 47) r7c9 <= 6 full house in r7 48) r9c5 <= 6 full house in b8 49) r2c5 <= 5 full house in c5 50) r9c2 <= 5 full house in r9 51) r8c8 <= 5 full house in b9 52) r3c1 <= 5 hidden single in b1 53) r1c3 <= 9 hidden single in b1 54) r1c9 <= 5 hidden single in b3 55) r2c9 <= 7 full house in c9 56) r3c6 <= 7 hidden single in b2 57) r2c6 <= 6 full house in b2 58) r2c8 <= 9 full house in r2 59) r3c3 <= 6 full house in r3 60) r1c2 <= 7 full house in b1 61) r1c8 <= 6 full house in r1 62) r8c2 <= 6 full house in c2 63) r4c3 <= 7 full house in c3 64) r4c1 <= 6 full house in r4 65) r8c1 <= 7 full house in c1179832465482156397536947821647385219395721648218694573924573186763418952851269734 1 4.6 2.0 2.0 0.4327ms1..........34..2...2..5..3..1.3.6.....4.2.7.....5...8..3..6..9...2..78..........4 1         456789    56789    |26789     3789      2389     |4569      4567      56789     56789     56789     3        |4         1789      189      |2         1567      156789    46789     2         6789     |16789     5         189      |1469      3         16789     --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 25789     1         5789     |3         4789      6        |459       245       259       35689     5689      4        |189       2         189      |7         156       13569     23679     679       679      |5         1479      149      |13469     8         12369     --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 4578      3         1578     |128       6         12458    |15        9         1257      4569      4569      2        |19        1349      7        |8         156       1356      56789     56789     156789   |1289      1389      123589   |1356      12567     4          1) r1c6 <= 2    direct hidden pair r13c4.<67>  2) r1c5 <= 3 hidden single in b2  3) r9c6 <= 3 hidden single in b8  4) r7c6 <= 5 hidden single in b8  5) r8c5 <= 4 hidden single in b8  6) r6c6 <= 4 hidden single in b5  7) r7c1 <= 4 hidden single in b7  8) r1c2 <= 4 hidden single in b1  9) r3c7 <= 4 hidden single in b3 10) r4c8 <= 4 hidden single in b6 11) r8c9 <= 3 hidden single in b9 12) r6c7 <= 3 hidden single in b6 13) r5c1 <= 3 hidden single in b4 14) r9c8 <= 2 hidden single in c8 15) r7c4 <= 2 hidden single in b8 16) r7c9 <= 7 hidden single in b9 17) r7c3 <= 8 hidden single in r7 18) r7c7 <= 1 full house in r7 19) r9c3 <= 1 hidden single in b7 20) r8c4 <= 1 hidden single in b8 21) r1c9 <= 8    direct hidden pair r13c4.<67> 22) r2c5 <> 7 locked candidates type 1 (pointing) b5/c5 23) r9c1 <> 9 locked candidates type 1 (pointing) b8/r9 24) r9c2 <> 9 locked candidates type 1 (pointing) b8/r9 25) r1c4 <> 9    naked pair r59c4.<89> 26) r3c4 <> 89   naked pair r59c4.<89> 27) r3c6 <> 1    ur[6]-loop type 2 <89> r5c4 r5c6 r2c6 r2c5 r9c5 r9c4  28) r3c9 <= 1 hidden single in r3 29) r5c8 <= 1 hidden single in b6 30) r6c5 <= 1 hidden single in b5 31) r2c6 <= 1 hidden single in b2 32) r4c5 <= 7 hidden single in b5 33) r4c1 <= 8 hidden single in r4 34) r2c2 <= 8 hidden single in b1 35) r3c6 <= 8 hidden single in b2 36) r5c6 <= 9 full house in c6 37) r5c4 <= 8 full house in b5 38) r2c5 <= 9 hidden single in b2 39) r9c5 <= 8 full house in c5 40) r9c4 <= 9 full house in b8 41) r1c7 <= 9 hidden single in b3 42) r6c1 <= 2 hidden single in b4 43) r4c9 <= 2 hidden single in b6 44) r6c9 <= 9 hidden single in b6 45) r4c3 <= 9 hidden single in b4 46) r4c7 <= 5 full house in r4 47) r5c9 <= 6 full house in b6 48) r5c2 <= 5 full house in r5 49) r9c7 <= 6 full house in c7 50) r2c9 <= 5 full house in c9 51) r8c8 <= 5 full house in b9 52) r1c3 <= 5 hidden single in b1 53) r3c1 <= 9 hidden single in b1 54) r9c1 <= 5 hidden single in b7 55) r9c2 <= 7 full house in r9 56) r6c3 <= 7 hidden single in b4 57) r3c3 <= 6 full house in c3 58) r2c1 <= 7 full house in b1 59) r8c1 <= 6 full house in c1 60) r2c8 <= 6 full house in r2 61) r3c4 <= 7 full house in r3 62) r1c4 <= 6 full house in b2 63) r1c8 <= 7 full house in r1 64) r6c2 <= 6 full house in b4 65) r8c2 <= 9 full house in c2145632978783491265926758431819376542354829716267514389438265197692147853571983624 2 4.6 2.0 2.0 0.3871ms.8..9.3.....4.......7..8.2...4..2.3.........11...3.2..35.....4...2.6.5..6....7... 245       8         156      |12567     9         156      |3         1567      4567      259       12369     13569    |4         1257      1356     |16789     156789    56789     459       13469     7        |1356      15        8        |1469      2         4569      --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 5789      679       4        |156789    1578      2        |6789      3         56789     25789     23679     35689    |56789     4578      4569     |46789     56789     1         1         679       5689     |56789     3         4569     |2         56789     456789    --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 3         5         189      |1289      128       19       |16789     4         26789     4789      1479      2        |1389      6         1349     |5         1789      3789      6         149       189      |123589    12458     7        |189       189       2389       1) r9c9 <= 2    direct hidden pair r7c79.<67>  2) r8c9 <= 3 hidden single in b9  3) r9c4 <= 3 hidden single in b8  4) r2c6 <= 3 hidden single in b2  5) r3c2 <= 3 hidden single in b1  6) r5c3 <= 3 hidden single in b4  7) r9c5 <= 5 hidden single in b8  8) r8c6 <= 4 hidden single in b8  9) r5c5 <= 4 hidden single in b5 10) r6c9 <= 4 hidden single in b6 11) r3c7 <= 4 hidden single in b3 12) r1c1 <= 4 hidden single in b1 13) r9c2 <= 4 hidden single in b7 14) r1c4 <= 2 hidden single in r1 15) r2c5 <= 7 hidden single in b2 16) r7c5 <= 2 hidden single in b8 17) r4c5 <= 8 hidden single in c5 18) r3c5 <= 1 full house in c5 19) r4c4 <= 1 hidden single in b5 20) r7c6 <= 1 hidden single in b8 21) r2c9 <= 8    direct hidden pair r7c79.<67> 22) r8c8 <> 7 locked candidates type 1 (pointing) b7/r8 23) r5c4 <> 9 locked candidates type 1 (pointing) b8/c4 24) r6c4 <> 9 locked candidates type 1 (pointing) b8/c4 25) r7c7 <> 89   naked pair r7c34.<89> 26) r7c9 <> 9    naked pair r7c34.<89> 27) r9c7 <> 1    ur[6]-loop type 2 <89> r7c3 r9c3 r9c8 r8c8 r8c4 r7c4  28) r2c7 <= 1 hidden single in c7 29) r1c3 <= 1 hidden single in b1 30) r8c2 <= 1 hidden single in b7 31) r8c1 <= 7 hidden single in b7 32) r9c8 <= 1 hidden single in b9 33) r5c1 <= 8 hidden single in c1 34) r5c2 <= 2 hidden single in b4 35) r2c1 <= 2 hidden single in b1 36) r6c8 <= 8 hidden single in b6 37) r9c7 <= 8 hidden single in b9 38) r9c3 <= 9 full house in r9 39) r7c3 <= 8 full house in b7 40) r8c4 <= 8 hidden single in b8 41) r8c8 <= 9 full house in r8 42) r7c4 <= 9 full house in b8 43) r3c9 <= 9 hidden single in b3 44) r2c2 <= 9 hidden single in b1 45) r2c3 <= 6 hidden single in b1 46) r3c1 <= 5 full house in b1 47) r4c1 <= 9 full house in c1 48) r2c8 <= 5 full house in r2 49) r3c4 <= 6 full house in r3 50) r1c6 <= 5 full house in b2 51) r6c3 <= 5 full house in c3 52) r5c4 <= 5 hidden single in b5 53) r6c4 <= 7 full house in c4 54) r4c2 <= 7 hidden single in b4 55) r6c2 <= 6 full house in c2 56) r6c6 <= 9 full house in r6 57) r5c6 <= 6 full house in b5 58) r4c9 <= 5 hidden single in b6 59) r4c7 <= 6 full house in r4 60) r5c7 <= 9 hidden single in b6 61) r5c8 <= 7 full house in r5 62) r7c7 <= 7 full house in c7 63) r7c9 <= 6 full house in r7 64) r1c8 <= 6 full house in c8 65) r1c9 <= 7 full house in r1481295367296473158537618429974182635823546971165739284358921746712864593649357812 3 4.6 2.0 2.0 0.3922ms100050700050100006000007000200010040006000000040500003000600190800090005030000800 1         2689      23489    |23489     5         234689   |7         238       2489      3479      5         234789   |1         2348      23489    |2349      238       6         3469      2689      23489    |23489     23468     7        |23459     12358     12489     --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 2         789       35789    |3789      1         3689     |569       4         789       3579      1789      6        |234789    23478     23489    |259       12578     12789     79        4         1789     |5         2678      2689     |269       12678     3         --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 457       27        2457     |6         23478     23458    |1         9         247       8         1267      1247     |2347      9         1234     |2346      2367      5         45679     3         124579   |247       247       1245     |8         267       247        1) r9c6 <= 5    direct hidden pair r7c56.<38>  2) r8c6 <= 1 hidden single in b8  3) r9c3 <= 1 hidden single in b7  4) r5c2 <= 1 hidden single in b4  5) r6c8 <= 1 hidden single in b6  6) r3c9 <= 1 hidden single in b3  7) r9c1 <= 9 hidden single in b7  8) r8c2 <= 6 hidden single in b7  9) r3c1 <= 6 hidden single in b1 10) r1c6 <= 6 hidden single in b2 11) r6c5 <= 6 hidden single in b5 12) r4c7 <= 6 hidden single in b6 13) r9c8 <= 6 hidden single in b9 14) r4c3 <= 5 hidden single in r4 15) r5c1 <= 3 hidden single in b4 16) r7c1 <= 5 hidden single in b7 17) r2c1 <= 4 hidden single in c1 18) r6c1 <= 7 full house in c1 19) r2c3 <= 7 hidden single in b1 20) r7c2 <= 7 hidden single in b7 21) r5c6 <= 4    direct hidden pair r7c56.<38> 22) r1c3 <> 2 locked candidates type 1 (pointing) b7/c3 23) r3c3 <> 2 locked candidates type 1 (pointing) b7/c3 24) r8c4 <> 3 locked candidates type 1 (pointing) b9/r8 25) r7c5 <> 24   naked pair r7c39.<24> 26) r7c6 <> 2    naked pair r7c39.<24> 27) r9c5 <> 7    ur[6]-loop type 2 <24> r7c9 r9c9 r9c4 r8c4 r8c3 r7c3  28) r5c5 <= 7 hidden single in c5 29) r4c9 <= 7 hidden single in b6 30) r8c8 <= 7 hidden single in b9 31) r9c4 <= 7 hidden single in b8 32) r8c7 <= 3 hidden single in b9 33) r3c7 <= 4 hidden single in c7 34) r1c4 <= 4 hidden single in b2 35) r3c8 <= 5 hidden single in b3 36) r5c7 <= 5 hidden single in b6 37) r9c5 <= 4 hidden single in b8 38) r9c9 <= 2 full house in r9 39) r7c9 <= 4 full house in b9 40) r8c3 <= 4 hidden single in b7 41) r7c3 <= 2 full house in b7 42) r8c4 <= 2 full house in r8 43) r6c6 <= 2 hidden single in b5 44) r5c8 <= 2 hidden single in b6 45) r2c7 <= 2 hidden single in b3 46) r6c7 <= 9 full house in c7 47) r6c3 <= 8 full house in r6 48) r4c2 <= 9 full house in b4 49) r5c9 <= 8 full house in b6 50) r5c4 <= 9 full house in r5 51) r1c9 <= 9 full house in c9 52) r3c3 <= 9 hidden single in b1 53) r1c3 <= 3 full house in c3 54) r3c5 <= 2 hidden single in b2 55) r1c2 <= 2 hidden single in b1 56) r1c8 <= 8 full house in r1 57) r3c2 <= 8 full house in b1 58) r3c4 <= 3 full house in r3 59) r2c8 <= 3 full house in b3 60) r4c4 <= 8 full house in c4 61) r4c6 <= 3 full house in r4 62) r2c6 <= 9 hidden single in b2 63) r2c5 <= 8 full house in r2 64) r7c5 <= 3 full house in c5 65) r7c6 <= 8 full house in c6123456789457189236689327451295813647316974528748562913572638194864291375931745862 4 4.6 2.0 2.0 0.3725ms`

I'm not familiar enough with Glen's gsf sudoku program to know the options, but I believe it can generate transpositions??? If anyone has a collection with multiples, I would like to have that for additional testing to ensure that my experimental replacement code is not sensitive to transposition scoring. So far, I don't think it is, but I have yet to test the higher level chaining logic.

Cheers,
Paul
PIsaacson

Posts: 249
Joined: 02 July 2008

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

PIsaacson wrote:I'm not familiar enough with Glen's gsf sudoku program to know the options, but I believe it can generate transpositions??? If anyone has a collection with multiples, I would like to have that for additional testing to ensure that my experimental replacement code is not sensitive to transposition scoring. So far, I don't think it is, but I have yet to test the higher level chaining logic.

1) Get a large sampling of puzzles from the Pattern Games.
2) Rate the puzzles using your program.
3) Convert the puzzles to row MinLex order using gsf's program: sudoku.exe -f"%c" in_file > out_file
4) Rate the puzzles in out_file using your program.
5) Compare the ratings from (2) to the ratings from (4).

Regards, Danny

Actually, someone should do this using Sudoku Explainer to get an idea of just how sensitive it is to transposition.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

PIsaacson wrote:At least one problem with transposed puzzles arises from the fact that many of the SE techniques restrict their range of operation to the only the sector of pattern discovery. It's just the way it was coded, not a bug, but it makes it sensitive to locality, causing it to miss potential eliminations/assignments due to presentation of candidates.

In the case of the uniqueness loop ("UL") above, I don't believe this to be the case. The UL is discovered in a chute (band or stack) and the scope of exclusions is the same chute. It shouldn't matter if a band is transposed to a stack.

Similarly, any 2 cell digit that is confined to a dual-sector line/box intersection has a range of operation extending to the remaining 7 box and 6 line (row or col) or 13 potential peers. This happens frequently.

I don't presently know how Explainer treats, for example, a naked pair in a line/box intersection. However, since we're trying to emulate Explainer's ratings, Explainer should be the guideline.

PIsaacson wrote:As a comparison, I ran all 4 above puzzle presentations though my experimental C++ SE replacement and all 4 rated identically at 4.6/2.0/2.0 and presented identical solution paths (which they should!):
Code: Select all
`1..........21..3...3..4..2..4.3.5.....5.2.6.....6...7..2..7..8...3..89..........4...179832465482156397536947821647385219395721648218694573924573186763418952851269734 1 4.6 2.0 2.0 0.4327ms1..........34..2...2..5..3..1.3.6.....4.2.7.....5...8..3..6..9...2..78..........4...145632978783491265926758431819376542354829716267514389438265197692147853571983624 2 4.6 2.0 2.0 0.3871msand more`

Congratulations, for these puzzles at least, you've out-Explainered Explainer.

daj95376 wrote:Actually, someone should do this using Sudoku Explainer to get an idea of just how sensitive it is to transposition.

For the UR and UL ratings ER=4.5 through ER=5.1, I've tested 99 isomorphs to all of the puzzles available in the Patterns Game. ER=4.6 and ER=5.0 are the only two that have anomalies. I'm examining the 5.0 cases now.

Using gsf's sudoku.exe program ...

sudoku -J99 file.dat
and
sudoku -J-99 file.dat

... generate 99 isomorphs for each of the puzzles in file.dat. The extra '-' in the 2nd inhibits changing the clue values. Obviously, the '99' can be some different number.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

I managed to find and correct the bug in the source code for finding unique loops in SE

In short, there is a recursive method for finding loops, when trying to find a loop and getting to the situation where the loop cannot continue, there is backtracking to the previous loop prefix; however when returning to that prefix, some information is not reset and therefore sometimes the prefix is continued with invalid state

The invalid state can result in some cases that the prefix will not continue to another loop which would have existed if the prefix state was valid

I also managed to provide a fix to the problem locally, and my version finds the transformed unique loop of the isomorphism bug example

Is there a way to provide the bug solution to the creator of SE? what are the ways for publishing a fixed version while maintaining the original license, and where should such a fix be placed?
lksudoku

Posts: 90
Joined: 06 October 2010

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

I maintain the version used by the patterns game
send me the patch and I can merge it in
actually, it would be best if you made the patch on the version used in the patterns game

I won't post an update immediately
I would first run it on all game entries to see how many puzzles hit the bug
lksudoku wrote:Is there a way to provide the bug solution to the creator of SE? what are the ways for publishing a fixed version while maintaining the original license, and where should such a fix be placed?
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

I've never played with isomorphs or minlex formats in the past, so testing with them is making me concerned that I don't understand something basic here: Are all properly coded techniques supposed to be able to withstand isomorph'ed puzzles and produce identical length chains/patterns??? It looks like everything up to aligned pairs is fairly tolerant of presentation, but after that, even simple XY chains don't seem to be able to produce identical results. Frequently identical and when different, usually similar, but sometimes disturbingly different.

So, should all scored puzzles be rated on their minlex format just to ensure uniformity? I'm starting to think that during my pre-processing code in which I validate whether or not the puzzle has a single unique solution, I should also reduce it to minlex form?

Anyway, thanks for the command line options to gsf's sudoku program for generating these sorts of test cases.

Cheers,
Paul
PIsaacson

Posts: 249
Joined: 02 July 2008

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

PIsaacson wrote:Are all properly coded techniques supposed to be able to withstand isomorph'ed puzzles and produce identical length chains/patterns??? It looks like everything up to aligned pairs is fairly tolerant of presentation, but after that, even simple XY chains don't seem to be able to produce identical results. Frequently identical and when different, usually similar, but sometimes disturbingly different.

No, I believe that's a realizable goal for a batch-solver, but an impossible goal for a step-solver. However, testing with multiple isomorphs can still be useful for a step-solver, as shown by the bug discovered above.

PIsaacson wrote:So, should all scored puzzles be rated on their minlex format just to ensure uniformity? I'm starting to think that during my pre-processing code in which I validate whether or not the puzzle has a single unique solution, I should also reduce it to minlex form?

Rating a canonical form was suggested by daj95376 earlier in the thread, and I've made the same suggestion for the Patterns Game in the past. I would like to see that as the command-line option though ... with the default being the rating of the puzzle as presented.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

ronk wrote:
PIsaacson wrote:Are all properly coded techniques supposed to be able to withstand isomorph'ed puzzles and produce identical length chains/patterns??? It looks like everything up to aligned pairs is fairly tolerant of presentation, but after that, even simple XY chains don't seem to be able to produce identical results. Frequently identical and when different, usually similar, but sometimes disturbingly different.

No, I believe that's a realizable goal for a batch-solver, but an impossible goal for a step-solver. However, testing with multiple isomorphs can still be useful for a step-solver, as shown by the bug discovered above.

I agree that blue is not to be expected when only one XY-Chain is performed at a time. However, all isomorphs should have a rating of XY-Chain or else all XY-Chain eliminations should occur before all isomorphs proceeds to a higher rating.

In general, it would be nice if all isomorphs produced identical canonical grids when proceeding from one rating level to a higher rating level. However and for example, depending on how UR logic is applied, this can't be guaranteed to happen.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

daj95376 wrote:In general, it would be nice if all isomorphs produced identical canonical grids when proceeding from one rating level to a higher rating level. However and for example, depending on how UR logic is applied, this can't be guaranteed to happen.

Hmm, aren't isomorphs identified by showing that their canonicalizations are identical?

Following slightly different solution paths, Sudoku Explainer ("SE") arrives at the same pencilmarks for this puzzle and its transpose ... after adjusting for the transposition, of course. There are two overlapping Type 4 Uniqueness Rectangles ("UR"). SE first finds one of the URs in the original puzzle ... and finds the other UR in the transpose. Each UR destroys the other, so both are not found.

As a result, there is a follow-on xy-wing in the original and a follow-on xy-loop in the transpose, for ER ratings 5.0 and 6.8, respectively.

Code: Select all
`original: . 1 . | . . 2 | . . . 3 4 . | . . . | . . . . . 2 | . 5 7 | . . .-------+-------+------- . . . | 3 . . | 1 . 7 . . 9 | . . . | 4 . . 1 . 5 | . . 8 | . . .-------+-------+------- . . . | 6 9 . | 3 . . . . . | . . . | . 6 2 . . . | 7 . . | . 9 .  # ED=5.0/1.2/1.2 56 Hidden Single3 Direct Hidden Pair6 Pointing1 Claiming1 Naked Pair2 Hidden Pair1 XY-Wing1 XYZ-Wing1 Unique Rectangle type 11 Unique Rectangle type 41 Naked QuadHardest technique: Naked QuadDifficulty: 5.0 5     1     6     | 48    3     2     | 78    478   9 3     4     7     | 9     18    6     | 2     18    5 89    89    2     | 14    5     7     | 6     14    3-------------------+-------------------+---------------- 248   28    48    | 3     6     9     | 1     5     7 6     3     9     | 5     7     1     | 4     2     8 1     7     5     | 2     4     8     | 9     3     6-------------------+-------------------+---------------- 27    25   *18-4  | 6     9     45    | 3     78   *14 79    59    34    | 18    18    34    | 57    6     2 48    6    *138-4 | 7     2     345   | 58    9    *14`

Code: Select all
`transpose: . 3 . | . . 1 | . . . 1 4 . | . . . | . . . . . 2 | . 9 5 | . . .-------+-------+------- . . . | 3 . . | 6 . 7 . . 5 | . . . | 9 . . 2 . 7 | . . 8 | . . .-------+-------+------- . . . | 1 4 . | 3 . . . . . | . . . | . 6 9 . . . | 7 . . | . 2 .   # ED=6.8/1.2/1.255 Hidden Single1 Direct Pointing3 Direct Hidden Pair7 Pointing1 Claiming1 Naked Pair2 Hidden Pair1 XY-Wing1 XYZ-Wing1 Unique Rectangle type 11 Unique Rectangle type 41 Naked Quad1 Bidirectional Y-CycleHardest technique: Bidirectional Y-CycleDifficulty: 6.8 5     3     89    | 248   6     1     | 27    79    48 1     4     89    | 28    3     7     | 25    59    6 6     7     2     | 48    9     5     | 148  *34   *138-4-------------------+-------------------+------------------ 48    9     14    | 3     5     2     | 6     18    7 3     18    5     | 6     7     4     | 9     18    2 2     6     7     | 9     1     8     | 45   *34   *35-4-------------------+-------------------+------------------ 78    2     6     | 1     4     9     | 3     57    58 478   18    14    | 5     2     3     | 78    6     9 9     5     3     | 7     8     6     | 14    2     14`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

ronk wrote:
PIsaacson wrote:Are all properly coded techniques supposed to be able to withstand isomorph'ed puzzles and produce identical length chains/patterns??? It looks like everything up to aligned pairs is fairly tolerant of presentation, but after that, even simple XY chains don't seem to be able to produce identical results. Frequently identical and when different, usually similar, but sometimes disturbingly different.

No, I believe that's a realizable goal for a batch-solver, but an impossible goal for a step-solver.

I agree, in a batch solver, it is likely that rating should remain fixed for all isomorphs

For a step-solver, having the same rating for different isomorphs requires the following property:
Given a candidate value C of puzzle P which can be removed with techniques up to rate R, for a puzzle P'<P which is a subset of P with smaller number of cadidates we can remove candidate C with techniques up to rate R'<=R

the UR and UL techniques do not hold that property for all cases as seen in the example above

Anyway, I do not suggest trusting current SE version for finding all UL and UR as it contains a bug, it would be better to search for examples with the fixed version
Last edited by lksudoku on Thu Oct 14, 2010 12:00 am, edited 1 time in total.
lksudoku

Posts: 90
Joined: 06 October 2010

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

lksudoku wrote:For a step-solver, having the same rating for different isomorphs requires the following property:
Given a candidate value C of puzzle P which can be removed with techniques up to rate R, for a puzzle P'<P which is a subset of P with smaller number of cadidates we can remove candidate C with techniques up to rate R'<=R

the UR and UL techniques do not hold that property for all cases

The set of "uniqueness techniques" might hold that property if the equivalent of UR1.1 for the UR Type 1 were implemented. A search for "UR1.1" on this site should provide food for thought here.

lksudoku wrote:Anyway, I do not suggest trusting current SE version for finding all UL and UR as it contains a bug, it would be better to search for examples with the fixed version

I've got Sudoku Explainer working within the Eclipse IDE, so would you please post the fix so I can incorporate it for my testing Hopefully by then I'll have figured out how to recreate the SudokuExplainer.jar file.

[edit: fixed quote tag]
Last edited by ronk on Thu Oct 14, 2010 12:41 am, edited 1 time in total.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

ronk wrote:
daj95376 wrote:In general, it would be nice if all isomorphs produced identical canonical grids when proceeding from one rating level to a higher rating level. However and for example, depending on how UR logic is applied, this can't be guaranteed to happen.

Hmm, aren't isomorphs identified by showing that their canonicalizations are identical?

Following slightly different solution paths, Sudoku Explainer ("SE") arrives at the same pencilmarks for this puzzle and its transpose ... after adjusting for the transposition, of course.

I was trying to say the same thing. Maybe I should have said:

A puzzle can be transposed based on the canonicalization of its solution. The same can be done for a partially solved grid. In general, it would be nice if the canonicalized transpose of all partially-solved isomorph grids were identical before proceeding to a higher rating level.

Thanks for supplying a specific example for my UR comment. It does support canonicalizing a puzzle before rating it.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

daj95376 wrote:It does support canonicalizing a puzzle before rating it.

Or performing batch solving, where all common rated techniques are applied simultaneously before trying a different technique, this mode is also likely to be faster
lksudoku

Posts: 90
Joined: 06 October 2010

### Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

I'm still in the process of debugging the last couple of dynamic forcing chains, but these lower level tests are good for seeing whether or not a transposed puzzle should score identically - using Ron's two puzzles listed above here's my full log output:
Code: Select all
`010002000340000000002057000000300107009000400105008000000690300000000062000700090 puzzle 1 starting 56789     1         678      |489       3468      2        |56789     34578     345689    3         4         678      |189       168       169      |256789    12578     15689     689       689       2        |1489      5         7        |689       1348      134689    --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 2468      268       468      |3         246       4569     |1         258       7         2678      23678     9        |125       1267      156      |4         2358      3568      1         2367      5        |249       2467      8        |269       23        369       --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 24578     2578      1478     |6         9         145      |3         14578     1458      45789     35789     13478    |1458      1348      1345     |578       6         2         24568     23568     13468    |7         12348     1345     |58        9         1458       1)  1.2 r1c1 <= 5 hidden single in b1  2)  1.2 r1c5 <= 3 hidden single in b2  3)  1.2 r9c5 <= 2 hidden single in b8  4)  1.5 r4c6 <= 9 hidden single in r4  5)  1.5 r4c8 <= 5 hidden single in r4  6)  1.7 r6c5 <= 4 direct pointing b2/r1  7)  1.2 r5c5 <= 7 hidden single in b5  8)  1.2 r6c2 <= 7 hidden single in b4  9)  1.2 r5c2 <= 3 hidden single in b4 10)  2.0 r6c4 <= 2    direct hidden pair r5c46.<15> 11)  1.2 r5c8 <= 2 hidden single in b6 12)  1.2 r2c7 <= 2 hidden single in b3 13)  1.2 r2c9 <= 5 hidden single in b3 14)  1.2 r5c9 <= 8 hidden single in b6 15)  1.5 r2c4 <= 9 hidden single in r2 16)  2.0 r2c6 <= 6    direct hidden pair r5c46.<15> 17)  1.2 r4c5 <= 6 hidden single in b5 18)  1.2 r5c1 <= 6 hidden single in b4 19)  2.0 r3c9 <= 3    direct hidden pair r6c79.<69> 20)  1.2 r6c8 <= 3 hidden single in b6 21)  2.6 r7c3 <> 7 locked candidates type 1 (pointing) b1/c3 22)  2.6 r8c3 <> 7 locked candidates type 1 (pointing) b1/c3 23)  2.6 r3c7 <> 9 locked candidates type 1 (pointing) b1/r3 24)  2.6 r8c4 <> 4 locked candidates type 1 (pointing) b2/c4 25)  2.6 r7c8 <> 1 locked candidates type 1 (pointing) b3/c8 26)  2.6 r8c1 <> 8 locked candidates type 1 (pointing) b8/r8 27)  2.6 r8c2 <> 8 locked candidates type 1 (pointing) b8/r8 28)  2.6 r8c3 <> 8 locked candidates type 1 (pointing) b8/r8 29)  2.6 r8c7 <> 8 locked candidates type 1 (pointing) b8/r8 30)  3.0 r1c9 <> 4    naked pair r79c9.<14> 31)  2.6 r7c8 <> 4 locked candidates type 1 (pointing) b3/c8 32)  3.4 r3c4 <> 8    hidden pair r3c48.<14> 33)  3.4 r3c8 <> 8    hidden pair r3c48.<14> 34)  4.4 r7c1 <> 4 xyz-wing at r7c3.<148> 1) r7c9.<14> 2) r9c1.<48> 35)  4.5 r1c7 <> 69   unique rectangle type 1 6/9 r1c79 r6c79 36)  1.2 r1c9 <= 9 hidden single in b3 37)  1.2 r3c7 <= 6 hidden single in b3 38)  1.2 r1c3 <= 6 hidden single in b1 39)  1.2 r2c3 <= 7 hidden single in b1 40)  1.2 r6c9 <= 6 hidden single in b6 41)  1.0 r6c7 <= 9 full house in r6 42)  1.2 r9c2 <= 6 hidden single in b7 43)  5.0 r7c1 <> 8    naked quad b7x3679.<1348> 44)  5.0 r7c2 <> 8    naked quad b7x3679.<1348> 45)  5.0 r8c1 <> 4    naked quad b7x3679.<1348> 46)  3.4 r8c3 <> 1    hidden pair r8c36.<34> 47)  2.8 r7c6 <> 1 locked candidates type 2 (claiming) b8/r8 48)  2.8 r9c6 <> 1 locked candidates type 2 (claiming) b8/r8 49)  2.0 r5c6 <= 1    direct hidden pair r8c36.<34> 50)  1.0 r5c4 <= 5 full house in r5 51)  3.4 r8c6 <> 5    hidden pair r8c36.<34> 52)  4.5 r7c3 <> 4   unique rectangle type 4 1/4 r7c39 r9c39 53)  4.5 r9c3 <> 4   unique rectangle type 4 1/4 r7c39 r9c39 54)  4.2 r9c9 <> 4 xy-wing at r7c3.<18> 1) r7c9.<14> 2) r9c1.<48> 55)  1.2 r7c9 <= 4 hidden single in b9 56)  1.0 r9c9 <= 1 full house in c9 57)  1.2 r7c3 <= 1 hidden single in b7 58)  1.5 r7c8 <= 8 hidden single in r7 59)  1.2 r1c7 <= 8 hidden single in b3 60)  1.2 r2c5 <= 8 hidden single in b2 61)  1.0 r2c8 <= 1 full house in r2 62)  1.0 r8c5 <= 1 full house in c5 63)  1.2 r3c4 <= 1 hidden single in b2 64)  1.0 r1c4 <= 4 full house in b2 65)  1.0 r1c8 <= 7 full house in r1 66)  1.0 r3c8 <= 4 full house in b3 67)  1.0 r8c4 <= 8 full house in c4 68)  1.2 r8c7 <= 7 hidden single in b9 69)  1.0 r9c7 <= 5 full house in c7 70)  1.2 r7c1 <= 7 hidden single in b7 71)  1.2 r7c2 <= 2 hidden single in b7 72)  1.0 r7c6 <= 5 full house in r7 73)  1.2 r4c1 <= 2 hidden single in b4 74)  1.2 r4c3 <= 4 hidden single in b4 75)  1.0 r4c2 <= 8 full house in r4 76)  1.2 r3c1 <= 8 hidden single in b1 77)  1.0 r3c2 <= 9 full house in b1 78)  1.0 r8c2 <= 5 full house in c2 79)  1.2 r9c1 <= 4 hidden single in b7 80)  1.0 r8c1 <= 9 full house in c1 81)  1.2 r9c3 <= 8 hidden single in b7 82)  1.0 r8c3 <= 3 full house in c3 83)  1.0 r8c6 <= 4 full house in r8 84)  1.0 r9c6 <= 3 full house in c6.1...2...34.........2.57......3..1.7..9...4..1.5..8......69.3.........62...7...9. 1 5.0 1.2 1.2 1.5822ms030001000140000000002095000000300607005000900207008000000140300000000069000700020 puzzle 2 starting 56789     3         689      |2468      2678      1        |24578     45789     24568     1         4         689      |268       23678     2367     |2578      35789     23568     678       678       2        |468       9         5        |1478      13478     13468     --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 489       189       1489     |3         125       249      |6         1458      7         3468      168       5        |246       1267      2467     |9         1348      12348     2         169       7        |4569      156       8        |145       1345      1345      --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 56789     256789    689      |1         4         269      |3         578       58        34578     12578     1348     |258       2358      23       |14578     6         9         345689    15689     134689   |7         3568      369      |1458      2         1458       1)  1.2 r1c1 <= 5 hidden single in b1  2)  1.2 r5c1 <= 3 hidden single in b4  3)  1.2 r5c9 <= 2 hidden single in b6  4)  1.5 r6c4 <= 9 hidden single in c4  5)  1.5 r8c4 <= 5 hidden single in c4  6)  1.7 r5c6 <= 4 direct pointing b4/r4  7)  1.2 r5c5 <= 7 hidden single in b5  8)  1.2 r2c6 <= 7 hidden single in b2  9)  1.2 r2c5 <= 3 hidden single in b2 10)  2.0 r6c2 <= 6    direct hidden pair r5c28.<18> 11)  1.2 r5c4 <= 6 hidden single in b5 12)  1.2 r1c5 <= 6 hidden single in b2 13)  2.0 r8c5 <= 2    direct hidden pair r46c5.<15> 14)  1.2 r4c6 <= 2 hidden single in b5 15)  1.2 r7c2 <= 2 hidden single in b7 16)  1.2 r9c2 <= 5 hidden single in b7 17)  1.2 r9c5 <= 8 hidden single in b8 18)  1.5 r4c2 <= 9 hidden single in c2 19)  2.0 r8c6 <= 3    direct hidden pair r79c6.<69> 20)  1.2 r9c3 <= 3 hidden single in b7 21)  2.6 r3c7 <> 7 locked candidates type 1 (pointing) b1/r3 22)  2.6 r3c8 <> 7 locked candidates type 1 (pointing) b1/r3 23)  2.6 r7c3 <> 9 locked candidates type 1 (pointing) b1/c3 24)  2.6 r4c8 <> 4 locked candidates type 1 (pointing) b4/r4 25)  2.6 r1c8 <> 8 locked candidates type 1 (pointing) b6/c8 26)  2.6 r2c8 <> 8 locked candidates type 1 (pointing) b6/c8 27)  2.6 r3c8 <> 8 locked candidates type 1 (pointing) b6/c8 28)  2.6 r7c8 <> 8 locked candidates type 1 (pointing) b6/c8 29)  2.6 r8c7 <> 1 locked candidates type 1 (pointing) b7/r8 30)  3.0 r8c7 <> 4    naked pair r9c79.<14> 31)  2.6 r9c1 <> 4 locked candidates type 1 (pointing) b9/r9 32)  3.4 r4c3 <> 8    hidden pair r48c3.<14> 33)  3.4 r8c3 <> 8    hidden pair r48c3.<14> 34)  4.4 r1c7 <> 4 xyz-wing at r3c7.<148> 1) r1c9.<48> 2) r9c7.<14> 35)  4.5 r7c1 <> 69   unique rectangle type 1 6/9 r7c16 r9c16 36)  1.2 r9c1 <= 9 hidden single in b7 37)  1.2 r7c3 <= 6 hidden single in b7 38)  1.2 r3c1 <= 6 hidden single in b1 39)  1.2 r3c2 <= 7 hidden single in b1 40)  1.2 r2c9 <= 6 hidden single in b3 41)  1.2 r9c6 <= 6 hidden single in b8 42)  1.0 r7c6 <= 9 full house in c6 43)  5.0 r1c7 <> 8    naked quad b3x3789.<1348> 44)  5.0 r1c8 <> 4    naked quad b3x3789.<1348> 45)  3.4 r3c8 <> 1    hidden pair r36c8.<34> 46)  2.8 r6c7 <> 1 locked candidates type 2 (claiming) b6/c8 47)  2.8 r6c9 <> 1 locked candidates type 2 (claiming) b6/c8 48)  2.0 r6c5 <= 1    direct hidden pair r36c8.<34> 49)  1.0 r4c5 <= 5 full house in c5 50)  3.4 r6c8 <> 5    hidden pair r36c8.<34> 51)  4.5 r3c7 <> 4   unique rectangle type 4 1/4 r3c79 r9c79 52)  4.5 r3c9 <> 4   unique rectangle type 4 1/4 r3c79 r9c79 53)  4.2 r3c9 <> 1 xy-wing at r1c9.<48> 1) r3c7.<18> 2) r9c9.<14> 54)  1.2 r3c7 <= 1 hidden single in b3 55)  1.2 r9c9 <= 1 hidden single in b9 56)  1.0 r9c7 <= 4 full house in r9 57)  2.0 r7c9 <= 5    direct hidden pair r6c89.<34> 58)  1.2 r6c7 <= 5 hidden single in b6 59)  1.2 r2c8 <= 5 hidden single in b3 60)  1.2 r1c8 <= 9 hidden single in b3 61)  1.2 r2c3 <= 9 hidden single in b1 62)  1.0 r1c3 <= 8 full house in b1 63)  1.2 r1c7 <= 7 hidden single in b3 64)  1.2 r2c7 <= 2 hidden single in b3 65)  1.0 r2c4 <= 8 full house in r2 66)  1.0 r8c7 <= 8 full house in c7 67)  1.0 r7c8 <= 7 full house in b9 68)  1.0 r7c1 <= 8 full house in r7 69)  1.2 r1c4 <= 2 hidden single in b2 70)  1.0 r1c9 <= 4 full house in r1 71)  1.0 r3c4 <= 4 full house in b2 72)  1.2 r3c9 <= 8 hidden single in b3 73)  1.0 r3c8 <= 3 full house in r3 74)  1.0 r6c9 <= 3 full house in c9 75)  1.0 r6c8 <= 4 full house in r6 76)  1.2 r5c2 <= 8 hidden single in b4 77)  1.0 r8c2 <= 1 full house in c2 78)  1.0 r5c8 <= 1 full house in r5 79)  1.0 r4c8 <= 8 full house in b6 80)  1.2 r4c3 <= 1 hidden single in b4 81)  1.0 r8c3 <= 4 full house in c3 82)  1.0 r4c1 <= 4 full house in r4 83)  1.0 r8c1 <= 7 full house in c1.3...1...14.........2.95......3..6.7..5...9..2.7..8......14.3.........69...7...2. 2 5.0 1.2 1.2 1.1845ms`

Both puzzles scored 5.0 1.2 1.2 and produced nearly identical presentation of methods/techniques. I have tested using the -Jnnn option to generate multiple transformations, but it appears that I cannot guarantee identical scores without placing puzzles into a known minlex format. Some techniques, such as aligned pairs/triples, are highly sensitive to transformations that take a set of cells that are confined to a single chute (it was the only way I could get APE/ATE to find productive reductions), and then subsequently scatter them such that they are no longer confined to a single chute. URs seem less sensitive since the 4 corners still exist regardless of transformations. ULs also seem to be fairly stable, but I don't have a sufficient numbers of test cases to be confident of that statement.

Is there a list of techniques that are known to be either consistently stable or else not expected to be stable with regards to transformations?

Question for Glen (if you're following this topic): I've tried to use the subcanon.c code since it seemed fairly self-contained and it was easy enough to bind together with my other C++ code, but it doesn't generate minlex transformations that match the -f"%c" option. I looked at the sudoku.c code and it looks like there is a "canon" function embedded in that source that provides minlex transforms as well. Is that the code I should be using if I want to exactly match the -f"%c"??? If so, then I'll have to see if I can slice/dice just that function...

Cheers,
Paul
PIsaacson

Posts: 249
Joined: 02 July 2008

PIsaacson wrote:Question for Glen:

I've tried to use the subcanon.c code since it seemed fairly self-contained and it was easy enough to bind together with my other C++ code, but it doesn't generate minlex transformations that match the -f"%c" option.

I looked at the sudoku.c code and it looks like there is a "canon" function embedded in that source that provides minlex transforms as well. Is that the code I should be using if I want to exactly match the -f"%c"???

yes

Pat

Posts: 3700
Joined: 18 July 2005

PreviousNext