Sudoku Players' Forum (clone)

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

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

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:

20 clues:

Hi P.O. and experts,

I saw your thread along with Myth Jelliesthis 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.

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

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 StuartRule 2 idea.

R. Jamil

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.

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

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         


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.

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:

pjb wrote:"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

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

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.

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

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.

Hi Hajime,

Hajime wrote: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

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)

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.