The New Sudoku Players' Forum

[PIsaacson]

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 c1
179832465482156397536947821647385219395721648218694573924573186763418952851269734 1 4.6 2.0 2.0 0.4327ms

1..........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 c2
145632978783491265926758431819376542354829716267514389438265197692147853571983624 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 r1
481295367296473158537618429974182635823546971165739284358921746712864593649357812 3 4.6 2.0 2.0 0.3922ms

100050700050100006000007000200010040006000000040500003000600190800090005030000800

 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 c6
123456789457189236689327451295813647316974528748562913572638194864291375931745862 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

[daj95376]

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.

[ronk]

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.

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.4327ms

1..........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.3871ms

and more

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

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.

[lksudoku]

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?

[gsf]

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
see the first page in the patterns game thread for download info

I won't post an update immediately
I would first run it on all game entries to see how many puzzles hit the bug

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?

[PIsaacson]

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

[ronk]

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.

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.

[daj95376]

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.

[ronk]

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 Single
3 Direct Hidden Pair
6 Pointing
1 Claiming
1 Naked Pair
2 Hidden Pair
1 XY-Wing
1 XYZ-Wing
1 Unique Rectangle type 1
1 Unique Rectangle type 4
1 Naked Quad
Hardest technique: Naked Quad
Difficulty: 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.2

55 Hidden Single
1 Direct Pointing
3 Direct Hidden Pair
7 Pointing
1 Claiming
1 Naked Pair
2 Hidden Pair
1 XY-Wing
1 XYZ-Wing
1 Unique Rectangle type 1
1 Unique Rectangle type 4
1 Naked Quad
1 Bidirectional Y-Cycle
Hardest technique: Bidirectional Y-Cycle
Difficulty: 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

[lksudoku]

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

[ronk]

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.

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]

[daj95376]

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.

[lksudoku]

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

[PIsaacson]

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.5822ms

030001000140000000002095000000300607005000900207008000000140300000000069000700020 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

[Pat]

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

it's canon() in sudoku.c