The New Sudoku Players' Forum

[Mathimagics]

Thanks for those examples, I can see that I still have some work to do ...

[coloin]

Code: Select all

+---+---+---+
|4.5|..6|...|
|.7.|.8.|..4|
|6..|...|.9.|
+---+---+---+
|...|..4|..7|
|..9|...|.8.|
|.6.|5..|...|
+---+---+---+
|...|..7|5..|
|8..|.6.|...|
|...|9..|.12|
+---+---+---+  ED=9.0/7.1/6.7

This puzzzle has 21 clues .... maybe it is worth a look at regarding the possible templates

And a 20C with a similar {123] template ..can be found

Code: Select all

+---+---+---+
|...|..4|...|
|.5.|.6.|.4.|
|7..|8..|9..|
+---+---+---+
|...|...|...|
|8..|..9|..7|
|5..|...|.6.|
+---+---+---+
|...|.4.|8..|
|.6.|7..|...|
|9..|.5.|.12|
+---+---+---+  ED=8.3/6.7/6.7  20C

[P.O.]

great i tried but i didn't find 20 clue puzzles with the same conditions.
the 21 clues is in 3(1)-template and the 20 in 3(2)-template

21 clues:

Hidden Text: Show

Code: Select all

4  .  5  .  .  6  .  .  .
.  7  .  .  8  .  .  .  4
6  .  .  .  .  .  .  9  .
.  .  .  .  .  4  .  .  7
.  .  9  .  .  .  .  8  .
.  6  .  5  .  .  .  .  .
.  .  .  .  .  7  5  .  .
8  .  .  .  6  .  .  .  .
.  .  .  9  .  .  .  1  2

4.5..6....7..8...46......9......4..7..9....8..6.5..........75..8...6.......9...12

4       12389   5       1237    12379   6       12378   237     138             
1239    7       123     123     8       12359   1236    2356    4               
6       1238    1238    12347   123457  1235    12378   9       1358             
1235    12358   1238    12368   1239    4       12369   2356    7               
12357   12345   9       12367   1237    123     12346   8       1356             
1237    6       123478  5       12379   12389   12349   234     139             
1239    12349   12346   12348   1234    7       5       346     3689             
8       123459  12347   1234    6       1235    3479    347     39               
357     345     3467    9       345     358     34678   1       2         

#VT: (524 550 3251 16 5 5 18 5 5)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil (38) nil nil nil nil
 2combs
#VT: (416 441 2477 15 5 4 18 2 4)
Cells: nil nil nil nil nil (75) nil (9 51 58 79) nil
SetVC: ( n8r1c9   n8r6c6   n8r7c4   n6r9c3   n8r9c7   n7r9c1
         n9r2c6   n5r2c8   n6r2c7   n7r6c3   n9r7c1   n9r1c2
         n4r5c2   n5r5c9   n6r7c9   n6r4c8   n6r5c4   n7r5c5
         n4r9c5   n5r3c5   n5r4c1   n4r3c4   n7r3c7   n7r1c4
         n7r8c8 )

#VT: (416 441 2477 2 2 1 1 2 3)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil
 2combs
#VT: (8 18 20 2 2 1 1 2 3)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:(29 50 66) (5) (29) nil nil nil nil nil nil
 2combs
#VT: (7 10 9 2 2 1 1 2 3)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:(43) (52) (50 56 57 70) nil nil nil nil nil nil
 2combs
#VT: (7 8 8 2 2 1 1 2 3)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil (42 66) nil nil nil nil nil nil nil
 2combs
#VT: (5 8 8 2 2 1 1 2 3)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil
 3combs
#VT: (3 3 3 2 2 1 1 2 2)
Cells: nil nil (62) nil nil nil nil nil nil
SetVC: ( n3r7c8   n9r8c9   n2r1c8   n4r6c8   n4r8c7   n3r8c3
         n5r9c2   n3r9c6   n1r5c6   n2r3c6   n5r8c6   n3r3c2
         n4r7c3   n8r4c2   n8r3c3   n1r3c9   n3r6c9   n3r1c7
         n2r5c7   n1r1c5   n3r2c4   n2r4c4   n3r5c1   n9r6c5
         n1r6c7   n2r7c5   n1r8c4   n1r4c3   n3r4c5   n9r4c7
         n2r6c1   n1r7c2   n2r8c2   n1r2c1   n2r2c3 )
4 9 5   7 1 6   3 2 8
1 7 2   3 8 9   6 5 4
6 3 8   4 5 2   7 9 1
5 8 1   2 3 4   9 6 7
3 4 9   6 7 1   2 8 5
2 6 7   5 9 8   1 4 3
9 1 4   8 2 7   5 3 6
8 2 3   1 6 5   4 7 9
7 5 6   9 4 3   8 1 2

(2 2 2 2 2 3)
puzzle in 3(1)-Template


20 clues:

Hidden Text: Show

Code: Select all

.  .  .  .  .  4  .  .  .
.  5  .  .  6  .  .  4  .
7  .  .  8  .  .  9  .  .
.  .  .  .  .  .  .  .  .
8  .  .  .  .  9  .  .  7
5  .  .  .  .  .  .  6  .
.  .  .  .  4  .  8  .  .
.  6  .  7  .  .  .  .  .
9  .  .  .  5  .  .  1  2

.....4....5..6..4.7..8..9...........8....9..75......6.....4.8...6.7.....9...5..12

1236     12389    123689   12359    12379    4        123567   23578    13568             
123      5        12389    1239     6        1237     1237     4        138               
7        1234     12346    8        123      1235     9        235      1356             
12346    123479   1234679  123456   12378    1235678  12345    23589    134589           
8        1234     12346    123456   123      9        12345    235      7                 
5        123479   123479   1234     12378    12378    1234     6        13489             
123      1237     12357    12369    4        1236     8        3579     3569             
1234     6        123458   7        12389    1238     345      359      3459             
9        3478     3478     36       5        368      3467     1        2     

#VT: (731 560 3139 15 22 6 12 11 12)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil (34) nil (76) nil nil nil
EraseCC: ( n3r9c4 )

#VT: (731 560 785 15 22 6 12 11 12)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil
 2combs
#VT: (650 523 717 8 22 4 12 8 10)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil (29 30 38 47 48 66) nil (3 9) nil (33) (72)
 2combs
#VT: (571 481 688 8 22 4 12 8 10)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil
 3combs
#VT: (374 343 456 8 18 4 6 8 10)
Cells: nil nil nil nil nil nil (62) nil nil
SetVC: ( n7r7c8 )

#VT: (374 343 456 8 18 4 8 8 10)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:(28) (28) (28) nil nil nil nil nil nil
 2combs
#VT: (374 343 408 8 16 4 8 8 4)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil (4 30)
 2combs
#VT: (374 331 389 8 16 4 8 7 4)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil (9) nil
 3combs
#VT: (247 193 220 8 12 3 6 7 4)
Cells: nil nil nil nil nil (1 27 79) nil nil nil
SetVC: ( n6r1c1   n6r3c9   n4r4c1   n6r9c7   n8r9c6   n8r8c3
         n8r1c2   n5r7c3   n8r4c8   n8r2c9   n9r8c8   n3r7c9
         n3r8c1   n8r6c5   n9r7c4   n9r1c5   n6r7c6   n7r4c5
         n7r2c6   n7r1c7   n9r2c3   n3r2c7   n1r1c9   n3r5c8
         n3r1c3   n3r3c5 )

#VT: (18 193 2 6 4 2 2 1 2)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil
 2combs
#VT: (16 13 2 4 3 2 2 1 2)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil (38 49) nil (52) (34) nil nil nil nil
EraseCC: ( n1r5c2   n2r5c5   n2r7c2   n1r8c5   n2r8c6   n4r3c2
           n6r5c3   n1r7c1   n7r9c2   n4r9c3   n2r2c1   n1r2c4
           n1r3c3   n5r3c6   n2r3c8   n2r4c3   n1r4c7   n7r6c3
           n4r6c4   n2r6c7   n9r6c9   n2r1c4   n5r1c8   n3r4c6
           n5r4c9   n5r5c4   n4r5c7   n3r6c2   n1r6c6   n5r8c7
           n4r8c9   n9r4c2   n6r4c4 )
6 8 3   2 9 4   7 5 1
2 5 9   1 6 7   3 4 8
7 4 1   8 3 5   9 2 6
4 9 2   6 7 3   1 8 5
8 1 6   5 2 9   4 3 7
5 3 7   4 8 1   2 6 9
1 2 5   9 4 6   8 7 3
3 6 8   7 1 2   5 9 4
9 7 4   3 5 8   6 1 2

(2 2 3 2 2 3 2)
puzzle in 3(2)-Template


[rjamil]

Hi P.O. and experts,

I saw your thread along with Myth Jellies this and this threads.

Thinking about how to search the same in fast way. Some questions arise in my mind, i.e.,

- Is it necessary to check all 46656 patterns for a particular digit?
- Is there any pre-requisite that at least one cell contain particular digit as either clue or solved?
- Is it the same template for row wise and column wise POM result? I think that it is impossible for box wise.

I assume the second question will be answered in the affirmative.

I think, for POM searching, if we search first occurrence of digit as either clue or solved cell then, we try to swap that cell location to r1c1. There are only one to four swap needed to move a clue or solved cell to r1c1.

1) If it is not present in Band 1 then swap the required Band with Band 1;
2) If it is not present in Row 1 then swap the required Row with Row 1;
3) If it is not present in Stack 1 then swap the required Stack with Stack 1; and
4) If it is not present in Column 1 then swap the required Column with Column 1.

In this way, the first cell always contain the clue or solved digit. So we need not to check Row 1 and Column 1.
We only need template to check whose row 1 cell location is r1c1, i.e., only 5184 templates (only 1/9 of total 46656 templates).
We need to store the eight locations instead of nine.
The array declaration syntax in C looks like "int POM[5184][8];"
Now to check the templates one by one as follows:

for x = 0 to 5184 // templates
for y = 0 to 7 // row wise templates
for z = (y * 9) + 10 to (y * 9) + 18 // row wise Sudoku Temporary array
if T[z][0] = POM[x][y] then T[z][1] += 1
next z
next y
next x

Where int T[81][2] array contain copy of original cell locations of Sudoku grid and number of templates digit occurred duly swapped as per above mentioned four swap steps.

I hope my algorithm is considered to be very fast, efficient and; if at least one clue or solved cell contain particular digit constraint then complete.

Sorry for my poor English.

R. Jamil

Edit on 20241016: Minor corrections highlighted as red color.

[P.O.]

Hi R. Jamil, you may find this thread interesting here and the link to Ruud thread: Has anyone tried solving these puzzles using templates?

with templates i use the following logic:
in any resolution state
- a candidate for a given value can be eliminated if it does not belong to any of the possible templates for that value
- a candidate for a given value can be set if it belongs to all the possible templates for that value
to implement this logic all templates are necessary
computing all templates is fast and the storage space required is negligible, checking the above conditions is fast too, the algorithms that become slow are those that combine templates of different values ​​in order to find template eliminations

the same result can be obtained without calculating any template:
a template is a set of nine pairwise disconnected cells so if for example n of a given value are already known it is enough to form with the set of remaining candidates cells for that value all the 9-n sets of pairwise disconnected cells and do on these sets the same verification as with the templates, as i did here, i call these sets complementary sets, in a single solution puzzle one of them necessarily complements the values ​​already found

[rjamil]

Hi P.O.,

Many thanks for sharing useful information and links.

However, I am still unclear about why all 46656 templates are necessary to check? Why n = 0 for a particular digit need to be check (consider single digit POM instead of multi digit POM)?

Note: For multi digit POM, I like Andrew Stuart Rule 2 idea.

R. Jamil

[P.O.]

the 46656 templates are not verified they are filtered to retrieve those which are possible for the considered value, only these are verified

Andrew Stuart write:
"Rule 1 considers each number in isolation. When looking for all the possible patterns for X it is possible that X may not appear in any pattern at all. If found, the solver reports and quits."

this indicates that there is a need to be exhaustive, either by examining all possible templates for x or by forming all complementary sets with the candidates cells for x

there are certainly several ways to do this.

[rjamil]

Hi P.O.,

Thanks for replying.

I am concentrating in POM's 46656 templates. There are indeed 5184 minimal templates for a particular digit.

What I understand from SudokuWiki Extreme Strategy Pattern Overlay page, Rule 2 example, he shows two alternative paths from B1 and B9.
What I understand is, if a row is moved that contain minimal particular digit to 1st row by swapping Band and/or Row, then move particular cell by swapping Stack and/or Column to r1c1 position. Then there will be no harm to check only 5184 templates instead of 46656 and get the same result.

Similarly, I am also thinking about that, if a digit is not present as either clue or solved, then move the entire row that contain minimal cell locations containing particular digit to first row (by swapping) and then move each cell to r1c1 that contain particular digit, one by one, search only 5184 templates, and combine the results.

I am playing with all 46656 templates in XLS file, data in 46656 rows and 9 columns. Applying filters on each column will give desired results. The results are same even if I move a clue or solved cell to r1c1 filter on first column to 0 location.

My approach is to speed things up, without loosing any scenario. I already achieved same results as per your OTP solution of Shye's Chronos puzzle, i.e. Total 16 templates for digit 9, none of them contain r5c5.

By moving the r5c5 digit 9 to r1c1, none of the template contain digit 9!!! And, there is no rule for the same scenario found!!!

R. Jamil

[P.O.]

in fact the number 5184 counts for each cell of the grid the number of templates of which the cell is a subset: 5184 for each of them

here the example given by Andrew Stuart for Rule 2, note that the following pm still has r1c7=3 and r5c2=3 unlike Andrew's who has already used Rule 2 on the 3s, if you load the puzzle from the start in his solver and follow the resolution path you will find it

it is not necessary to check all 46656 templates nor 5184 of them it is enough to retrieve the possible templates for values 3 and 7, which amounts to 10 and 6 respectively, to combine them and examine if there are any conflicts between them

2 eliminations for 3 and 2 eliminations for 7 are found when combining the possible templates for these two values: there are 12 such combinations and their conflicts leave 7 templates for 3 and 4 for 7 allowing the eliminations: r1c7 and r5c2 <> 3, r2c8 and r5c8 <> 7

Code: Select all

#VT: (1 31 10 11 57 4 6 8 16)

235     24589   2459    256      7      568     3459    1       3589             
57      6       1       4       89      3       2       5789    5789             
2357    234589  234579  1       289     58      3459    45789   6               
8       1       379     37      5       2       369     679     4               
2357    2359    6       37      1       4       8       2579    23579           
4       235     2357    8       6       9       35      257     1               
9       2345    2345    256     248     7       1       24568   258             
6       245     8       9       24      1       7       3       25               
1       7       245     256     3       568     4569    245689  2589         


Hidden Text: Show

Code: Select all

(3 7): 12 instances

....7...3.....3..77.3.........3...7.3..7.......7...3...3...7.........73..7..3....
....7...3.....3..77.3........73.....3..7...........37..3...7.........73..7..3....
....7...3.....3..773..........3...7.3..7.......7...3....3..7.........73..7..3....
....7...3.....3..773.........73.....3..7...........37...3..7.........73..7..3....
....7...3.....3..73.7.........7..3..7..3.......3....7..3...7.........73..7..3....
....7...3.....3..73.7.........7..3..7..3......3.....7...3..7.........73..7..3....
....7...37....3...3......7....7..3.....3....7.37........3..7.........73..7..3....
....7...3.....3..73.7........37.....7..3...........37..3...7.........73..7..3....
....7...37....3...3......7...37........3....7..7...3...3...7.........73..7..3....
3...7.........3..77.....3....73........7....3..3....7..3...7.........73..7..3....
3...7.........3..77.....3.....3...7....7....3.37........3..7.........73..7..3....
3...7.........3..77.....3....73........7....3.3.....7...3..7.........73..7..3....

........3.....3.....3.........3.....3..............3...3..............3.....3....
........3.....3....3..........3.....3..............3....3.............3.....3....
........3.....3...3..............3.....3.......3.......3..............3.....3....
........3.....3...3..............3.....3......3.........3.............3.....3....
........3.....3...3..........3.........3...........3...3..............3.....3....
3.............3.........3.....3.............3..3.......3..............3.....3....
3.............3.........3.....3.............3.3.........3.............3.....3....

....7............7..7.........7.....7...............7......7.........7...7.......
....7............77...............7....7.......7...........7.........7...7.......
....7............77..........7.........7............7......7.........7...7.......
....7....7...............7....7.............7..7...........7.........7...7.......

#VT: (1 31 7 11 57 4 4 8 16)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil (7 38) nil nil nil (17 44) nil nil

235     24589   2459    256     7       568     459     1       3589             
57      6       1       4       89      3       2       589     5789             
2357    234589  234579  1       289     58      3459    45789   6               
8       1       379     37      5       2       369     679     4               
2357    259     6       37      1       4       8       259     23579           
4       235     2357    8       6       9       35      257     1               
9       2345    2345    256     248     7       1       24568   258             
6       245     8       9       24      1       7       3       25               
1       7       245     256     3       568     4569    245689  2589   


you should take a look at Puzzle 234, it has the same particularity as Chronos of being solved at initialization with templates, it is Rule 1 in Andrew's terminology: 24 candidates are eliminated: one 2, two 6s and twenty-one 9s.

i don't really understand what the grid morphing maneuvers bring in terms of speed, it seems more like a burden to me, especially if you check the 5184 templates repeatedly, that adds up to a pretty big number in the end and morphing the grid will not change its characteristics in terms of templates, of course you get the same result no matter what morph you use

but i'm not sure i understand correctly what you're doing, your last sentence "And, there is no rule for the same scenario found!!!" is obscure to me.

[rjamil]

Hi P.O.,

I have read the Ruud's Has anyone tried solving these puzzles using templates? It is exactly the same concept as what I am thinking about POM.

I don't understand how Philip Beeby implemented POM in his solver. Is he generates the templates for a particular state of the puzzle or uses predefined templates?

In this post:

"Between them r3c7 and r8c8 include all patterns of 2, so patterns of 7 which include both cells can be deleted. As a result, no pattern of 7 includes r6c9 so 7 can be deleted from r6c9"

Isn't simply to place the digit 2 in r3c7 and r8c8?

Tested https://www.philsfolly.net.au/Sudoku/index.htm by importing Chronos and, after Start and Zap, by pressing POMs gives same hint.

Added: I am adding my findings of your OTP solutions of following puzzles:

1) 17 clue puzzles:

Code: Select all

After Locked candidate Type 1 (Pointing): 3 @ r4c12 => -3 @ r4c789;
 +-------------------------+------------------------+-----------------------+
 | 456789   245689  245678 | 356789   26789  235789 | 3689    34679  1      |
 | 1456789  45689   145678 | 1356789  6789   135789 | 3689    2      346789 |
 | 16789    2689    3      | 16789    26789  4      | 689     679    5      |
 +-------------------------+------------------------+-----------------------+
 | 34589    34589   458    | 145789   24789  6      | 1259    1579   279    |
 | 5689     7       568    | 1589     3      12589  | 4       1569   269    |
 | 2        1       456    | 4579     479    579    | 3569    8      3679   |
 +-------------------------+------------------------+-----------------------+
 | 345678   234568  245678 | 346789   1      3789   | 235689  34569  234689 |
 | 134678   3468    14678  | 2        5      3789   | 13689   13469  34689  |
 | 134568   234568  9      | 3468     468    38     | 7       13456  23468  |
 +-------------------------+------------------------+-----------------------+
POM: Digit 1 not in 6 Templates => -1 @ r4c4 r5c8
POM: Digit 2 not in 5 Templates => -2 @ r1c6 r4c5 r5c9
POM: Digit 2 in all 5 Templates => 2 @ r5c6
stte

2) 17August24:

Code: Select all

After basics;
 +-------------------+-----------------------+------------------------+
 | 3789  2389  25789 | 1279   4       6      | 12579   12359   12379  |
 | 1     36    2479  | 279    2579    2579   | 2479    8       36     |
 | 679   2469  24579 | 1279   3       8      | 124579  124569  124679 |
 +-------------------+-----------------------+------------------------+
 | 2     3489  14789 | 3479   179     13479  | 6       149     5      |
 | 369   5     149   | 8      1269    12349  | 12479   1249    12479  |
 | 679   469   1479  | 24679  125679  124579 | 3       1249    8      |
 +-------------------+-----------------------+------------------------+
 | 5     1     3     | 24679  26789   2479   | 2489    2469    2469   |
 | 89    289   289   | 5      16      134    | 14      7       1346   |
 | 4     7     6     | 239    1289    1239   | 12589   12359   1239   |
 +-------------------+-----------------------+------------------------+
POM: Digit 3 not in 5 Templates => -3 @ r1c1 r4c2 r5c6
POM: Digit 3 in all 5 Templates => 3 @ r5c1
POM: Digit 6 not in 1 Template => -6 @ r2c9 r3c1 r3c2 r3c9 r6c5 r6c4 r6c2 r7c5 r7c8 r7c9 r8c5
POM: Digit 6 in all 1 Template => 6 @ r2c2 r3c8 r5c5 r6c1 r7c4 r8c9
POM: Digit 7 not in 40 Templates => -7 @ r1c3 r2c3 r3c3
stte

3) 17September24:

Code: Select all

After basics;
 +-------------------+-----------------------+-----------------------+
 | 1359  2359  12569 | 1258   4       7      | 12568   1235   12368  |
 | 8     37    1245  | 125    1256    1256   | 1245    9      37     |
 | 157   2457  12456 | 1258   3       9      | 124568  12457  124678 |
 +-------------------+-----------------------+-----------------------+
 | 2     349   1489  | 134    168     13468  | 7       146    5      |
 | 1357  6     145   | 9      1257    12345  | 1248    124    1248   |
 | 157   457   1458  | 12457  125678  124568 | 3       1246   9      |
 +-------------------+-----------------------+-----------------------+
 | 6     1     3     | 2457   25789   2458   | 2459    2457   247    |
 | 59    259   259   | 6      17      134    | 14      8      1347   |
 | 4     8     7     | 1235   1259    1235   | 12569   1235   1236   |
 +-------------------+-----------------------+-----------------------+
POM: Digit 3 not in 5 Templates => -3 @ r1c1 r4c2 r5c6
POM: Digit 3 in all 5 Templates => 3 @ r5c1
POM: Digit 7 not in 1 Template => -7 @ r2c9 r3c1 r3c2 r3c9 r6c5 r6c4 r6c2 r7c5 r7c8 r7c9 r8c5
POM: Digit 7 in all 1 Template => 7 @ r2c2 r3c8 r5c5 r6c1 r7c4 r8c9
stte

R. Jamil

[P.O.]

Hi R. Jamil, for the 3 puzzles you mention when i initialized them with the template procedure i found that they were solved immediately and these are the results i posted

Hidden Text: Show

Code: Select all

........1.......2...3..4..5.....6....7..3.4..21.....8.....1.......25......9...7..
#VT: (6 5 94 92 138 527 89 856 511)
Cells: nil (42) nil nil nil nil nil nil nil
SetVC: ( n2r5c6   n1r2c6   n1r8c3   n1r3c1   n1r9c8   n1r4c7
         n2r7c7   n2r4c9   n5r7c8   n5r6c7   n1r5c4   n2r9c2
         n2r1c3   n3r6c9   n5r9c1   n5r1c6   n5r4c4   n6r6c3
         n7r2c9   n7r4c8   n8r4c5   n4r4c3   n2r3c5   n4r1c8
         n5r5c3   n5r2c2   n7r7c3   n7r3c4   n7r1c1   n8r5c1
         n8r2c3   n3r8c8   n4r2c1   n7r8c6   n7r6c5   n8r3c7
         n8r1c4   n9r4c1   n3r4c2   n9r6c6   n6r8c1   n9r8c7
         n4r6c4   n3r7c1   n8r7c6   n3r9c6   n4r7c2   n6r7c9
         n8r8c2   n4r8c9   n6r9c4   n4r9c5   n8r9c9   n9r5c9
         n9r7c4   n3r2c4   n6r2c7   n9r3c8   n6r5c8   n3r1c7
         n9r2c5   n6r3c2   n9r1c2   n6r1c5 )
7 9 2   8 6 5   3 4 1
4 5 8   3 9 1   6 2 7
1 6 3   7 2 4   8 9 5
9 3 4   5 8 6   1 7 2
8 7 5   1 3 2   4 6 9
2 1 6   4 7 9   5 8 3
3 4 7   9 1 8   2 5 6
6 8 1   2 5 7   9 3 4
5 2 9   6 4 3   7 1 8
Solved.

....46...1......8.....3....2.....6.5.5.8...........3...13.........5...7.4.6......
#VT: (144 576 5 128 8 6 104 8 3232)
Cells: nil nil (37) nil nil nil nil nil nil
SetVC: ( n3r5c1   n6r5c5   n6r8c9   n6r7c4   n3r8c6   n4r7c6
         n4r8c7   n6r3c8   n6r2c2   n7r7c5   n8r7c7   n1r8c5
         n3r4c4   n3r2c9   n3r1c2   n4r6c4   n4r3c9   n4r2c3
         n6r6c1   n8r9c5   n9r4c5   n9r6c2   n2r3c2   n8r8c2
         n4r4c2   n1r4c8   n2r6c8   n9r7c8   n2r7c9   n9r8c1
         n2r8c3   n1r9c9   n5r1c8   n7r3c1   n7r4c6   n4r5c8
         n5r6c5   n1r6c6   n5r9c7   n3r9c8   n8r1c1   n9r1c3
         n7r1c9   n2r2c5   n9r2c7   n5r3c3   n1r3c7   n8r4c3
         n2r5c6   n7r5c7   n9r5c9   n7r6c3   n9r9c6   n1r1c4
         n2r1c7   n7r2c4   n5r2c6   n9r3c4   n1r5c3   n2r9c4 )
8 3 9   1 4 6   2 5 7
1 6 4   7 2 5   9 8 3
7 2 5   9 3 8   1 6 4
2 4 8   3 9 7   6 1 5
3 5 1   8 6 2   7 4 9
6 9 7   4 5 1   3 2 8
5 1 3   6 7 4   8 9 2
9 8 2   5 1 3   4 7 6
4 7 6   2 8 9   5 3 1
Solved.

....47...8......9.....3....2.....7.5.6.9...........3...13.........6...8.4.7......
#VT: (792 576 5 128 576 16 6 16 8)
Cells: nil nil (37) nil nil nil nil nil nil
SetVC: ( n3r5c1   n7r5c5   n7r8c9   n7r7c4   n3r8c6   n4r7c6
         n4r8c7   n7r3c8   n7r2c2   n8r7c5   n9r7c7   n2r7c9
         n5r7c8   n1r8c5   n3r4c4   n3r2c9   n3r1c2   n4r6c4
         n4r3c9   n4r2c3   n7r6c1   n9r9c5   n6r4c5   n5r6c2
         n2r6c5   n5r2c5   n2r3c2   n9r8c2   n4r4c2   n1r4c8
         n8r5c9   n6r6c8   n5r8c1   n2r8c3   n3r9c8   n2r1c8
         n1r3c1   n8r3c4   n8r4c6   n1r5c3   n5r5c6   n2r5c7
         n4r5c8   n8r6c3   n1r6c6   n2r9c6   n9r1c1   n1r1c4
         n6r1c9   n2r2c4   n6r2c6   n1r2c7   n5r3c7   n9r4c3
         n5r9c4   n6r9c7   n1r9c9   n5r1c3   n8r1c7   n6r3c3 )
9 3 5   1 4 7   8 2 6
8 7 4   2 5 6   1 9 3
1 2 6   8 3 9   5 7 4
2 4 9   3 6 8   7 1 5
3 6 1   9 7 5   2 4 8
7 5 8   4 2 1   3 6 9
6 1 3   7 8 4   9 5 2
5 9 2   6 1 3   4 8 7
4 8 7   5 9 2   6 3 1
Solved.


i also have the same conception as Ruud about templates and his description of their use as a resolution technique matches my implementation, the only difference being that i don't mix it with other techniques

i obviously agree with the observations he makes:
"There are 46656 different configurations for any value in the grid.
With 1 position given, 5184 configurations are left.
With 2 positions given in 1 chute, 864 configurations are left.
etc."
but i would use different vocabulary to talk about them. Since a sudoku grid can be modeled as a graph it may be convenient to use some concepts from this theory to talk about some of its aspects. The 81 cells of the sudoku are the vertices of the graph and two vertices are adjacent if they are connected by an edge, this notion of adjacency between two sudoku cells is easily defined if the cells are referenced by an RowColBox coordinate system like this:

Code: Select all

((1 1 1) (1 2 1) (1 3 1) (1 4 2) (1 5 2) (1 6 2) (1 7 3) (1 8 3) (1 9 3)
 (2 1 1) (2 2 1) (2 3 1) (2 4 2) (2 5 2) (2 6 2) (2 7 3) (2 8 3) (2 9 3)
 (3 1 1) (3 2 1) (3 3 1) (3 4 2) (3 5 2) (3 6 2) (3 7 3) (3 8 3) (3 9 3)
 (4 1 4) (4 2 4) (4 3 4) (4 4 5) (4 5 5) (4 6 5) (4 7 6) (4 8 6) (4 9 6)
 (5 1 4) (5 2 4) (5 3 4) (5 4 5) (5 5 5) (5 6 5) (5 7 6) (5 8 6) (5 9 6)
 (6 1 4) (6 2 4) (6 3 4) (6 4 5) (6 5 5) (6 6 5) (6 7 6) (6 8 6) (6 9 6)
 (7 1 7) (7 2 7) (7 3 7) (7 4 8) (7 5 8) (7 6 8) (7 7 9) (7 8 9) (7 9 9)
 (8 1 7) (8 2 7) (8 3 7) (8 4 8) (8 5 8) (8 6 8) (8 7 9) (8 8 9) (8 9 9)
 (9 1 7) (9 2 7) (9 3 7) (9 4 8) (9 5 8) (9 6 8) (9 7 9) (9 8 9) (9 9 9))


two cells are adjacent or connected if at least one of their RCB coordinates is equal, otherwise they are non-adjacent or disconnected
Two concepts are useful for describing sets of cells:
- Cliques: sets of pairwise connected cells
- independent sets: sets of pairwise disconnected cells

if by abuse of language the 81 cells taken individually are considered as independent sets of size 1 then in a 9×9 Sudoku grid there are:

Code: Select all

  #ind.Sets / size
       81      1
     2430      2
    34506      3
   247860      4
   901044      5
  1586304      6
  1259712      7
   419904      8
    46656      9 


for a total of 4,498,497

and templates can be defined as independent sets of size 9 which is the maximum size, all other independent sets as subsets of templates, and here is their distribution:

Code: Select all

size / (#TP #iS)
   1     (5184 81)
   2     (864 972) (576 1458)
   3     (288 972) (144 11664) (96 17496) (64 4374)
   4     (48 34992) (36 11664) (24 69984) (16 131220)
   5     (16 26244) (12 139968) (8 209952) (4 524880)
   6     (6 46656) (4 419904) (2 839808) (1 279936)
   7     (2 419904) (1 839808)
   8     (1 419904)
   9     (1 46656)


for example:
for independent sets of size 2 there are 972 of them which are subsets of 864 templates and 1458 of 576
for independent sets of size 3 there are 972 of them which are subsets of 288 templates and 11664 of 144, 17496 of 96, 4374 of 64
etc.
and the difference in distribution for each size depends as Ruud observed on the arrangement of the cells on the grid.

a puzzle can be define as a partition of n cells into k independent sets, some partitions give invalid puzzles i.e. zero solutions, others puzzles with one solution and others puzzles with several solutions and a template procedure easily distinguishes between these three categories as Ruud points out.

taking as an example the puzzle given by StrmCkr in the post you quote, here is three partitioning of its 41 cells with the partition (9 6 6 6 6 5 2 1)

Code: Select all

0.00.000..0.0....0000.00.0.00.0.00.000..000..0.00.....0..0.0.0000..0.0...0....0.0   pattern
6.23.915..3.2....6954.61.3.86.5.43.241..235..5.31.....3..4.2.1514..3.6...2....4.3   0 sol
6.23.915..3.2....6954.16.3.26.5.43.141..235..5.31.....3..4.2.1584..3.6...2....4.3   1 sol   StrmCkr
6.23.915..3.2....6954.61.3.28.5.43.141..235..5.36.....3..4.2.1514..3.6...2....4.3   7 sols


Phil explains his method a little here

regarding this quote from Phil:
"Between them r3c7 and r8c8 include all patterns of 2, so patterns of 7 which include both cells can be deleted. As a result, no pattern of 7 includes r6c9 so 7 can be deleted from r6c9"
if we are to understand that there are only 2 possible templates for 2, i have to disagree with Phil, there are 3 and the one that is part of the solution does not contain r3c7 and therefore doing r3c7=2 would be an error, in fact r3c7=7 is in the solution

Code: Select all

(3 13 27 28 41 52 60 71 74)      (3 13 25 28 41 54 60 71 74)      (3 13 25 28 41 53 60 72 74)
     • . 2 • . • • • .                • . 2 • . • • • .                • . 2 • . • • • .
     . • . 2 . . . . •                . • . 2 . . . . •                . • . 2 . . . . •
     • • • . • • - • X                • • • . • • X • -                • • • . • • X • -
     2 • . • . • • . •                2 • . • . • • . •                2 • . • . • • . •
     • • . . 2 • • . .                • • . . 2 • • . .                • • . . 2 • • . .
     • . • • . . X - -                • . • • . . - - X                • . • • . . - X -
     • . . • . 2 . • •                • . . • . 2 . • •                • . . • . 2 . • •
     • • . . • . • X -                • • . . • . • X -                • • . . • . • - X
     . 2 . . . . • . •                . 2 . . . . • . •                . 2 . . . . • . •


but as you rightly say if all the possible templates for a value have cells in common these cells can be set to this value, it is the logic of the resolution by templates, an extremely simple logic but which requires, in order not to make mistakes, to be exhaustive in their enumeration.

[rjamil]

Hi P.O.,

I do have a 32 bit value of RCB for each cell positions stored along with each cell 20 buddies/peers as described here.

I see lot of redundant/unnecessary checking and proposed skips/steps, if all 46656 combinations of POM stored, in order to speed things up, as follows:

For 1st row, search starts from 0 to 46656 step 5184; (total 9 checks)
For 2nd row, search starts from 1st row to (1st row + 1) * 5184 step 864; (total 6 checks)
For 3rd row, search starts from 2nd row to (2nd row + 1) * 864 step 288; (total 3 checks)
and so on.

R. Jamil

[Hajime]

Is the PO method also suitable for a SudokuX with diagonals?
You can not exchange stacks/bands that easily and also not columns/rows within stacks/bands.

[rjamil]

Hi Hajime,

You can not exchange stacks/bands that easily and also not columns/rows within stacks/bands.

Well, I already did it and achieved positive results but not sure if it is optimized or not.

R. Jamil

[P.O.]

Hi R.Jamil,
i also keep in memory in addition to all the templates some tables like for each cell the cells to which it is connected as well as to which it is not connected etc. which helps to speed things up a little, but i suppose that this is a common practice.

the first thing i do when solving with templates, after loading the puzzle into its data structure and applying Singles which is the only technique i use with templates in order to evolve the grid concurrently with the elimination of templates, is to retrieve for each value the set of possible templates, for this i break down the puzzle into its different parts, its independent sets to use the vocabulary of the previous post, with each Single found these parts grow and if the puzzle is not solved the process starts again with this calculation

let's take as example this puzzle:

Code: Select all

8..2...3.4367..5.......1.......1.....2.9.......7.......4.5.....1....8492.....3..6 
(24 32 64) (4 38 72) (8 11 78) (10 56 70) (16 58) (12 81) (13 48) (1 69) (40 71)   parts from 1 to 9


here is the number of templates for each part: (96 64 96 144 576 576 576 576 576) the first four shows three of the four cell arrangements of size 3 in stacks and bands on the grid
for each part the set of other parts constitutes its context and from its templates as an independent set must be subtracted all those which include at least one of the cells of the context, so all that remains are the possible templates for each part: (4 2 10 10 19 14 24 4 27)

Hidden Text: Show

Code: Select all

1: ((3 18 24 32 44 47 61 64 76) (3 18 24 32 43 47 62 64 76) (2 18 24 32 39 53 61 64 76)
   (2 18 24 32 39 52 62 64 76))
 
2: ((4 17 21 34 38 50 60 72 73) (4 17 19 34 38 50 60 72 75))
 
3: ((8 11 23 31 45 46 61 66 78) (8 11 23 31 43 46 63 66 78) (8 11 23 36 37 49 61 66 78)
   (8 11 23 31 37 54 61 66 78)  (8 11 23 31 37 52 63 66 78) (8 11 23 28 45 49 61 66 78)
   (8 11 23 28 43 49 63 66 78)  (8 11 22 36 41 46 61 66 78) (8 11 22 28 41 54 61 66 78)
   (8 11 22 28 41 52 63 66 78))
 
4: ((9 10 22 35 39 51 56 70 77) (9 10 22 33 39 53 56 70 77) (9 10 22 30 44 51 56 70 77)
   (9 10 22 30 42 53 56 70 77)  (6 10 27 35 39 49 56 70 77) (6 10 27 31 39 53 56 70 77)
   (6 10 27 30 44 49 56 70 77)  (6 10 26 36 39 49 56 70 77) (6 10 26 31 39 54 56 70 77)
   (6 10 26 30 45 49 56 70 77))
 
5: ((6 16 21 36 41 46 58 65 80) (6 16 21 28 41 54 58 65 80) (5 16 21 36 42 46 58 65 80)
   (5 16 21 33 45 46 58 65 80)  (5 16 21 36 37 51 58 65 80) (5 16 21 33 37 54 58 65 80)
   (5 16 21 28 45 51 58 65 80)  (5 16 21 28 42 54 58 65 80) (6 16 19 30 41 54 58 65 80)
   (5 16 19 36 39 51 58 65 80)  (5 16 19 33 39 54 58 65 80) (5 16 19 30 45 51 58 65 80)
   (5 16 19 30 42 54 58 65 80)  (3 16 23 36 42 46 58 65 80) (3 16 23 33 45 46 58 65 80)
   (3 16 23 36 37 51 58 65 80)  (3 16 23 33 37 54 58 65 80) (3 16 23 28 45 51 58 65 80)
   (3 16 23 28 42 54 58 65 80))
 
6: ((7 12 23 35 42 47 55 67 81) (7 12 23 33 44 47 55 67 81) (7 12 23 29 44 51 55 67 81)
   (7 12 23 29 42 53 55 67 81)  (6 12 26 29 41 52 55 67 81) (6 12 25 35 41 47 55 67 81)
   (6 12 25 29 41 53 55 67 81)  (5 12 26 33 43 47 55 67 81) (5 12 26 29 43 51 55 67 81)
   (5 12 26 29 42 52 55 67 81)  (5 12 25 35 42 47 55 67 81) (5 12 25 33 44 47 55 67 81)
   (5 12 25 29 44 51 55 67 81)  (5 12 25 29 42 53 55 67 81))
 
7: ((9 13 20 35 42 48 61 68 73) (9 13 20 33 44 48 61 68 73) (9 13 20 33 43 48 62 68 73)
   (7 13 20 36 42 48 62 68 73)  (7 13 20 35 42 48 63 68 73) (7 13 20 33 45 48 62 68 73)
   (7 13 20 33 44 48 63 68 73)  (9 13 19 35 42 48 61 68 74) (9 13 19 33 44 48 61 68 74)
   (9 13 19 33 43 48 62 68 74)  (7 13 19 36 42 48 62 68 74) (7 13 19 35 42 48 63 68 74)
   (7 13 19 33 45 48 62 68 74)  (7 13 19 33 44 48 63 68 74) (2 13 27 35 42 48 61 68 73)
   (2 13 27 33 44 48 61 68 73)  (2 13 27 33 43 48 62 68 73) (2 13 26 36 42 48 61 68 73)
   (2 13 26 33 45 48 61 68 73)  (2 13 26 33 43 48 63 68 73) (2 13 25 36 42 48 62 68 73)
   (2 13 25 35 42 48 63 68 73)  (2 13 25 33 45 48 62 68 73) (2 13 25 33 44 48 63 68 73))
 
8: ((1 14 27 31 44 47 57 69 79) (1 14 27 29 44 49 57 69 79) (1 14 26 31 45 47 57 69 79)
   (1 14 26 29 45 49 57 69 79))
 
9: ((9 15 21 29 40 52 59 71 73) (9 15 21 28 40 52 59 71 74) (7 15 21 36 40 47 59 71 73)
   (7 15 21 36 40 46 59 71 74)  (7 15 21 29 40 54 59 71 73) (7 15 21 28 40 54 59 71 74)
   (9 15 20 30 40 52 59 71 73)  (9 15 20 28 40 52 59 71 75) (7 15 20 36 40 46 59 71 75)
   (7 15 20 30 40 54 59 71 73)  (7 15 20 28 40 54 59 71 75) (9 15 19 30 40 52 59 71 74)
   (9 15 19 29 40 52 59 71 75)  (7 15 19 36 40 47 59 71 75) (7 15 19 30 40 54 59 71 74)
   (7 15 19 29 40 54 59 71 75)  (3 15 27 29 40 52 59 71 73) (3 15 27 28 40 52 59 71 74)
   (3 15 25 36 40 47 59 71 73)  (3 15 25 36 40 46 59 71 74) (3 15 25 29 40 54 59 71 73)
   (3 15 25 28 40 54 59 71 74)  (2 15 27 30 40 52 59 71 73) (2 15 27 28 40 52 59 71 75)
   (2 15 25 36 40 46 59 71 75)  (2 15 25 30 40 54 59 71 73) (2 15 25 28 40 54 59 71 75))


This is the filtering phase of the procedure which is repeated iteratively on reduced sets of templates each time some of them are eliminated and which converges towards the solution(s) of the puzzle
this obtained i apply the logic of the resolution by templates which is double:
- first i check for each set of templates if they have cells in common, if so i put in these cells the value associated with this set of templates and i apply Singles, if the puzzle is solved i stop, if there were some Singles but the puzzle is not solved the process iterates from the parts calculation
- otherwise i retrieve for each value all of their candidate cells:

Code: Select all

1: (2 3 39 43 44 47 52 53 61 62)
2: (19 21 73 75)
3: (22 23 28 31 36 37 41 43 45 46 49 52 54 61 63)
4: (6 9 22 26 27 30 31 33 35 36 39 42 44 45 49 51 53 54)
5: (3 5 6 19 21 23 28 30 33 36 37 39 41 42 45 46 51 54)
6: (5 6 7 23 25 26 29 33 35 41 42 43 44 47 51 52 53)
7: (2 7 9 19 20 25 26 27 33 35 36 42 43 44 45 61 62 63 73 74)
8: (26 27 29 31 35 36 44 45 47 49 53 54)
9: (2 3 7 9 19 20 21 25 27 28 29 30 36 46 47 52 54 73 74 75)


and i check if some of them are absent from all of its possible templates, for this puzzle it is the case for the 8 for which none of the cells 35 36 53 54 are found in its four possible templates, in which case i eliminate this value from these cells and i apply Singles, if the grid is solved i stop, otherwise if there were singles the process iterates from the parts calculation

otherwise i enter the process of eliminating templates by combining templates of different values and checking their compatibility, which is more complicated.