The New Sudoku Players' Forum

by **Mathimagics** » Wed Dec 14, 2022 9:11 am

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

by **coloin** » Sun Dec 24, 2023 3:28 am

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

by **P.O.** » Sun Dec 24, 2023 6:40 pm

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

by **rjamil** » Sun Oct 13, 2024 1:19 pm

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.

by **P.O.** » Sun Oct 13, 2024 5:20 pm

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

by **rjamil** » Mon Oct 14, 2024 1:33 am

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

by **P.O.** » Mon Oct 14, 2024 4:01 am

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.

by **rjamil** » Mon Oct 14, 2024 10:08 am

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

by **P.O.** » Mon Oct 14, 2024 5:28 pm

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.

by **rjamil** » Tue Oct 15, 2024 9:44 pm

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

by **P.O.** » Wed Oct 16, 2024 5:22 pm

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.

by **rjamil** » Thu Oct 17, 2024 2:54 am

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

by **Hajime** » Thu Oct 17, 2024 11:41 am

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.

by **rjamil** » Thu Oct 17, 2024 4:45 pm

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

by **P.O.** » Thu Oct 17, 2024 5:21 pm

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.

The New Sudoku Players' Forum

Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method

Re: Pattern Overlay Method