The New Sudoku Players' Forum

by **rjamil** » Tue Nov 19, 2024 6:44 pm

Hi P.O.,

Ok. Now I understand how two-digit POM templates are combined, i.e., by taking non-overlapping templates of each digit out of all valid each digit templates.

However, for two-digit (or multi-digit) POM, one need to keep track of all the valid single-digit POM of both (or all of) the digits.

In case of an empty Sudoku puzzle, each digit POM maximum number of valid template count is 15,552 (i.e., 3 x 5184 for each digit). Playing with such a huge data need linked list, which is not available in C language (or, I don't know) right now. Once, I will be able to record such a huge data, i.e., for three-digit, there are 46,656 templates need to be examined.

Thank you for your guidance and support for taking the time to provide such detailed and constructive feedback.

Searched and found Myth Jellies post here, here, here and here.

R. Jamil

by **rjamil** » Mon Dec 23, 2024 11:46 am

Hi experts,

While I am studing dynamic memory allocation in C language (as compared to linked lists in C++ language) and thinking about how to implement multi-digit POM, got an idea to implement as follows:

I see no significant difference to capture the valid (possible) templates of each digit, in order to display accordingly. The only thing to compute the elimination(s) / placement(s) is / are to count the valid (possible) templates only, and, any cell that contain particular digit, if absent from / present in all valid (possible) templates, may be eliminated / placed accordingly.
My new idea is to just count for each digit (from 1 ... 9) against each digit except itself, i.e., two unique digits {(1, [2 ... 9]), (2, [1, 3 ... 9]), (3, [1, 2, 4 ... 9]), ...};
1. If only one occurance found for each digit, then the template is considered as solution;
2. If more than one occurance found then treat as single-digit POM move;
3. if no valid (possible) template found then the puzzle has either no or multiple solution;
4. If step (b) failed then search for 3-digit combinations, then, 4-digit combinations.

The above scenario is searched 9 x 8 = 72 times for 2 unique digit combinations, 9 x 8 x 7 = 504 for 3, and 9 x 8 x 7 x 6 = 3024 for 4, without tracking any template, and give solution.

R. Jamil

by **Hajime** » Mon Dec 23, 2024 6:23 pm

Why do you need all the those 46656 patterns.
If you follow the rules of https://www.sudokuwiki.org/Pattern_Overlay for the 3 example here.
You can eliminate all candidates 3's with a "-". And all cells with "ab" have 3 as a solution.
1 extra rule: only houses (row,col,box) that are touched are included. Others are out-of-reach.
So in the next example all 4's are candidates

Code: Select all: ...4.4... ......... ......... 4.......4 ......... 4.......4 ......... ......... ...4.4...

You can pick the 4's in row 1, but they influence only row 9.
Row 4 and 6 are untouched, so you can not eliminate the 4's there, not even if the have the mark "-".
Rigth?

by **P.O.** » Mon Dec 23, 2024 6:26 pm

hi R. Jamil
there are certainly several ways to use templates as a resolution technique, personally i use the following method:

with the combinations of 2, to be kept
a template for 1 must figure in all these combinations: (1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) (1 9)
a template for 2 must figure in all these combinations: (1 2) (2 3) (2 4) (2 5) (2 6) (2 7) (2 8) (2 9)
a template for 3 must figure in all these combinations: (1 3) (2 3) (3 4) (3 5) (3 6) (3 7) (3 8) (3 9)
a template for 4 must figure in all these combinations: (1 4) (2 4) (3 4) (4 5) (4 6) (4 7) (4 8) (4 9)
a template for 5 must figure in all these combinations: (1 5) (2 5) (3 5) (4 5) (5 6) (5 7) (5 8) (5 9)
a template for 6 must figure in all these combinations: (1 6) (2 6) (3 6) (4 6) (5 6) (6 7) (6 8) (6 9)
a template for 7 must figure in all these combinations: (1 7) (2 7) (3 7) (4 7) (5 7) (6 7) (7 8) (7 9)
a template for 8 must figure in all these combinations: (1 8) (2 8) (3 8) (4 8) (5 8) (6 8) (7 8) (8 9)
a template for 9 must figure in all these combinations: (1 9) (2 9) (3 9) (4 9) (5 9) (6 9) (7 9) (8 9)

with the combinations of 3, to be kept
a template for 1 must figure in all these combinations:
(1 2 3) (1 2 4) (1 2 5) (1 2 6) (1 2 7) (1 2 8) (1 2 9) (1 3 4) (1 3 5)
(1 3 6) (1 3 7) (1 3 8) (1 3 9) (1 4 5) (1 4 6) (1 4 7) (1 4 8) (1 4 9)
(1 5 6) (1 5 7) (1 5 8) (1 5 9) (1 6 7) (1 6 8) (1 6 9) (1 7 8) (1 7 9)
(1 8 9)
a template for 2 must figure in all these combinations:
(1 2 3) (1 2 4) (1 2 5) (1 2 6) (1 2 7) (1 2 8) (1 2 9) (2 3 4) (2 3 5)
(2 3 6) (2 3 7) (2 3 8) (2 3 9) (2 4 5) (2 4 6) (2 4 7) (2 4 8) (2 4 9)
(2 5 6) (2 5 7) (2 5 8) (2 5 9) (2 6 7) (2 6 8) (2 6 9) (2 7 8) (2 7 9)
(2 8 9)
a template for 3 must figure in all these combinations:
(1 2 3) (1 3 4) (1 3 5) (1 3 6) (1 3 7) (1 3 8) (1 3 9) (2 3 4) (2 3 5)
(2 3 6) (2 3 7) (2 3 8) (2 3 9) (3 4 5) (3 4 6) (3 4 7) (3 4 8) (3 4 9)
(3 5 6) (3 5 7) (3 5 8) (3 5 9) (3 6 7) (3 6 8) (3 6 9) (3 7 8) (3 7 9)
(3 8 9)
etc.

with the combinations of 4, to be kept
a template for 1 must figure in all these combinations:
(1 2 3 4) (1 2 3 5) (1 2 3 6) (1 2 3 7) (1 2 3 8) (1 2 3 9) (1 2 4 5)
(1 2 4 6) (1 2 4 7) (1 2 4 8) (1 2 4 9) (1 2 5 6) (1 2 5 7) (1 2 5 8)
(1 2 5 9) (1 2 6 7) (1 2 6 8) (1 2 6 9) (1 2 7 8) (1 2 7 9) (1 2 8 9)
(1 3 4 5) (1 3 4 6) (1 3 4 7) (1 3 4 8) (1 3 4 9) (1 3 5 6) (1 3 5 7)
(1 3 5 8) (1 3 5 9) (1 3 6 7) (1 3 6 8) (1 3 6 9) (1 3 7 8) (1 3 7 9)
(1 3 8 9) (1 4 5 6) (1 4 5 7) (1 4 5 8) (1 4 5 9) (1 4 6 7) (1 4 6 8)
(1 4 6 9) (1 4 7 8) (1 4 7 9) (1 4 8 9) (1 5 6 7) (1 5 6 8) (1 5 6 9)
(1 5 7 8) (1 5 7 9) (1 5 8 9) (1 6 7 8) (1 6 7 9) (1 6 8 9) (1 7 8 9)
a template for 2 must figure in all these combinations:
(1 2 3 4) (1 2 3 5) (1 2 3 6) (1 2 3 7) (1 2 3 8) (1 2 3 9) (1 2 4 5)
(1 2 4 6) (1 2 4 7) (1 2 4 8) (1 2 4 9) (1 2 5 6) (1 2 5 7) (1 2 5 8)
(1 2 5 9) (1 2 6 7) (1 2 6 8) (1 2 6 9) (1 2 7 8) (1 2 7 9) (1 2 8 9)
(2 3 4 5) (2 3 4 6) (2 3 4 7) (2 3 4 8) (2 3 4 9) (2 3 5 6) (2 3 5 7)
(2 3 5 8) (2 3 5 9) (2 3 6 7) (2 3 6 8) (2 3 6 9) (2 3 7 8) (2 3 7 9)
(2 3 8 9) (2 4 5 6) (2 4 5 7) (2 4 5 8) (2 4 5 9) (2 4 6 7) (2 4 6 8)
(2 4 6 9) (2 4 7 8) (2 4 7 9) (2 4 8 9) (2 5 6 7) (2 5 6 8) (2 5 6 9)
(2 5 7 8) (2 5 7 9) (2 5 8 9) (2 6 7 8) (2 6 7 9) (2 6 8 9) (2 7 8 9)
etc.

etc.

with this method if the puzzle has multiple solutions all its solutions are obtained
if the puzzle has no solution this is noted when there is no more template for certain combinations
for example this puzzle is invalid, with my implementation it passes the combinations of 2 then is found invalid with the combinations of 3

Code: Select all: . 6 . 2 . . . . . . . 3 . 9 . . . . . 4 . 6 . 1 . . . 1 . . . 5 . 2 . . 4 . 7 . 3 . . 1 . 2 . . . 4 . . . 5 . 1 8 7 . . . 3 . . . . . 1 . 8 . . . . . . . 9 . . . .6.2.......3.9.....4.6.1...1...5.2..4.7.3..1.2...4...5.187...3.....1.8.......9... 5789 6 1 2 78 3 4579 45789 4789 578 278 3 458 9 4578 14567 245678 124678 5789 4 259 6 78 1 3579 25789 23789 1 389 69 89 5 678 2 46789 346789 4 5 7 89 3 2 69 1 689 2 389 69 1 4 678 3679 6789 5 569 1 8 7 26 456 4569 3 2469 35679 2379 24569 345 1 456 8 245679 24679 3567 237 2456 3458 268 9 14567 24567 12467 196 candidates. PM VALID. #VT: (2 10 4 15 23 24 78 20 48) Cells: nil nil nil nil nil nil nil nil nil Candidates: nil nil (65 74) (16 17 18) (10 16 17) (35 36 52 53 60 66 69 75) (15) (11 18) nil 5789 6 1 2 78 3 4579 45789 4789 78 27 3 458 9 458 167 2678 1267 5789 4 259 6 78 1 3579 25789 23789 1 389 69 89 5 678 2 4789 34789 4 5 7 89 3 2 69 1 689 2 389 69 1 4 678 379 789 5 569 1 8 7 26 45 4569 3 2469 35679 279 2459 345 1 45 8 245679 24679 3567 27 245 3458 268 9 14567 24567 12467 177 candidates. PM VALID. 2combs #VT: (2 10 4 15 23 20 78 19 46) Cells: nil nil nil nil nil nil nil nil nil Candidates: nil nil nil nil nil (61) nil nil nil 5789 6 1 2 78 3 4579 45789 4789 78 27 3 458 9 458 167 2678 1267 5789 4 259 6 78 1 3579 25789 23789 1 389 69 89 5 678 2 4789 34789 4 5 7 89 3 2 69 1 689 2 389 69 1 4 678 379 789 5 569 1 8 7 26 45 459 3 2469 35679 279 2459 345 1 45 8 245679 24679 3567 27 245 3458 268 9 14567 24567 12467 176 candidates. PM VALID. 3combs Puzzle invalid: .6.2.......3.9.....4.6.1...1...5.2..4.7.3..1.2...4...5.187...3.....1.8.......9... #VT: (2 9 4 12 14 8 76 0 13)

by **rjamil** » Wed Dec 25, 2024 2:04 am

Hi P.O.,

Thanks for providing the expanded version of what I was thinking.

Now, I am rethinking about how to code the multi-digit POM search routine as per pjb described here and here.

R. Jamil

by **P.O.** » Wed Dec 25, 2024 12:40 pm

once what needs to be done has been specified enough to consider a technical implementation, all that remains is to set up the data structures and algorithms and there is also more than one way to proceed, in the link you cite pjb outlined his method, i did the same here and Dobrichev here also posting his code which is in C the language you use

he uses a puzzle to illustrate his method, step B of which corresponds to the computation of the templates for each value at the beginning of the procedure, i quote:
"Step B. Apply the 9 masks over all 46656 templates. Store all disjoint to the mask templates as candidates for the respective digit.
Template distribution 36 28 54 28 14 4 6 14 42 product=301112598528 sum=226"

solving the puzzle i get the same distribution, note that the puzzle is in 2-template and can be solved by considering only the combination (6 7)
Dobrichev's example:

Code: Select all: . . . . . 1 . . 2 . . 3 . 4 . . 5 . . 6 . 7 . . 8 . . . . 6 . . . . 7 . . 4 . . 2 . . . 3 1 . . . . 4 9 . . . . 8 . . 9 5 . . . 7 . 8 . . . 6 . 6 . . . 5 . . . . .....1..2..3.4..5..6.7..8....6....7..4..2...31....49....8..95...7.8...6.6...5.... 45789 589 4579 3569 3689 1 3467 349 2 2789 1289 3 269 4 268 167 5 1679 2459 6 12459 7 39 235 8 1349 149 23589 23589 6 1359 1389 358 124 7 1458 5789 4 579 1569 2 5678 16 18 3 1 2358 257 356 3678 4 9 28 568 234 123 8 12346 1367 9 5 1234 147 23459 7 12459 8 13 23 1234 6 149 6 1239 1249 1234 5 237 12347 123489 14789 209 candidates. #VT: (36 28 54 28 14 4 6 14 42) Cells: nil nil nil nil nil (54) nil nil nil SetVC: ( n6r6c9 n1r5c7 n8r5c8 n2r6c8 n4r4c7 n5r4c9 n8r9c9 ) #VT: (10 14 54 12 7 4 6 4 42) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil (11) nil 45789 589 4579 3569 3689 1 367 349 2 2789 129 3 269 4 268 67 5 179 2459 6 12459 7 39 235 8 1349 149 2389 2389 6 139 1389 38 4 7 5 579 4 579 569 2 567 1 8 3 1 358 57 35 378 4 9 2 6 234 123 8 12346 1367 9 5 134 147 23459 7 12459 8 13 23 23 6 149 6 1239 1249 1234 5 237 237 1349 8 166 candidates. 2combs #VT: (10 14 46 12 7 4 3 3 26) Cells: nil nil nil nil nil nil (50 63 78) nil nil SetVC: ( n7r6c5 n7r7c9 n7r9c6 n5r6c3 n3r6c4 n8r4c6 n8r6c2 n5r8c1 n5r1c2 n8r1c5 n8r2c1 n5r5c4 n5r3c6 n6r7c5 n6r5c6 n7r2c7 n2r2c6 n3r8c6 n2r8c7 n3r9c7 n6r1c7 n1r8c5 n9r1c4 n6r2c4 n3r3c5 n1r4c4 n9r4c5 n3r1c8 ) #VT: (3 4 2 12 1 1 2 1 2) Cells: nil nil nil nil nil nil nil nil (11 37) SetVC: ( n9r2c2 n1r2c9 n9r5c1 n7r5c3 n4r1c3 n2r3c1 n1r3c3 n3r4c1 n2r4c2 n4r7c1 n2r7c4 n1r7c8 n9r8c3 n4r8c9 n1r9c2 n2r9c3 n4r9c4 n9r9c8 n7r1c1 n4r3c8 n9r3c9 n3r7c2 ) 7 5 4 9 8 1 6 3 2 8 9 3 6 4 2 7 5 1 2 6 1 7 3 5 8 4 9 3 2 6 1 9 8 4 7 5 9 4 7 5 2 6 1 8 3 1 8 5 3 7 4 9 2 6 4 3 8 2 6 9 5 1 7 5 7 9 8 1 3 2 6 4 6 1 2 4 5 7 3 9 8 puzzle in 2(1)-Template

by **rjamil** » Wed Dec 25, 2024 4:45 pm

Hi P.O.,

Many thanks for such a detailed and informative analysis with patience.

Actually, what I am thinking is to avoid storing the valid (possible) templates (either in linked list or dynamic memory allocation). All I see is that, the count of single-digit and multi-digit templates are sufficient. I am now thinking to implement the multi-digit POM without keep tracking the templates (just like I did for single-digit POM) as follows:

for each template of digit 1;
if digit 1 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 1;
for each template of digit 2;
if digit 2 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 3;
for each template of digit 3;
if digit 3 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 5;
for each template of digit 4;
if digit 4 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 7;
for each template of digit 5;
if digit 5 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 9;
for each template of digit 6;
if digit 6 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 11;
for each template of digit 7;
if digit 7 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 13;
for each template of digit 8;
if digit 8 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 15;
for each template of digit 9;
if digit 9 is absent in template's nine disjoint cells as clue or solved or candidate then go to step 17;
all nine digits template are considered as solution;
count number of solution;
next template of digit 9;
next template of digit 8;
next template of digit 7;
next template of digit 6;
next template of digit 5;
next template of digit 4;
next template of digit 3;
next template of digit 2;
next template of digit 1;
if (number of solution) is one than puzzle is solved else puzzle has (number of solution) solution(s).

The above flow chart reflects what I understand from pjb implemented in his solver as described here.

R. Jamil

Note: I checked nine loops for generating the 46,656 templates as follows:

Hidden Text: Show

Code: Select all: #include <stdio.h> int main (void) { int w[81] = { // Band, Stack, Row, Box and Column for 81 Cell positions 262657, 262658, 262660, 134480904, 134480912, 134480928, 268699712, 268699776, 268699904, 524801, 524802, 524804, 134743048, 134743056, 134743072, 268961856, 268961920, 268962048, 1049089, 1049090, 1049092, 135267336, 135267344, 135267360, 269486144, 269486208, 269486336, 538972161, 538972162, 538972164, 673193992, 673194000, 673194016, 807419968, 807420032, 807420160, 541069313, 541069314, 541069316, 675291144, 675291152, 675291168, 809517120, 809517184, 809517312, 545263617, 545263618, 545263620, 679485448, 679485456, 679485472, 813711424, 813711488, 813711616, 1090551809,1090551810,1090551812,1224802312,1224802320,1224802336,1359085632,1359085696,1359085824, 1107329025,1107329026,1107329028,1241579528,1241579536,1241579552,1375862848,1375862912,1375863040, 1140883457,1140883458,1140883460,1275133960,1275133968,1275133984,1409417280,1409417344,1409417472}, B[513] = { // Count bitwise Cell values 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9,10}; for (int x = 0, a = 0; a < 9; ++a) for (int b = 9; b < 18; ++b) { if (B[(w[a] | w[b]) & 511] < 2 || B[((w[a] | w[b]) >> 9) & 511] < 2) continue; for (int c = 18; c < 27; ++c) { if (B[(w[a] | w[b] | w[c]) & 511] < 3 || B[((w[a] | w[b] | w[c]) >> 9) & 511] < 3) continue; for (int d = 27; d < 36; ++d) { if (B[(w[a] | w[b] | w[c] | w[d]) & 511] < 4 || B[((w[a] | w[b] | w[c] | w[d]) >> 9) & 511] < 4) continue; for (int e = 36; e < 45; ++e) { if (B[(w[a] | w[b] | w[c] | w[d] | w[e]) & 511] < 5 || B[((w[a] | w[b] | w[c] | w[d] | w[e]) >> 9) & 511] < 5) continue; for (int f = 45; f < 54; ++f) { if (B[(w[a] | w[b] | w[c] | w[d] | w[e] | w[f]) & 511] < 6 || B[((w[a] | w[b] | w[c] | w[d] | w[e] | w[f]) >> 9) & 511] < 6) continue; for (int g = 54; g < 63; ++g) { if (B[(w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g]) & 511] < 7 || B[((w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g]) >> 9) & 511] < 7) continue; for (int h = 63; h < 72; ++h) { if (B[(w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g] | w[h]) & 511] < 8 || B[((w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g] | w[h]) >> 9) & 511] < 8) continue; for (int i = 72; i < 81; ++i) { if (B[(w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g] | w[h] | w[i]) & 511] < 9 || B[((w[a] | w[b] | w[c] | w[d] | w[e] | w[f] | w[g] | w[h] | w[i]) >> 9) & 511] < 9) continue; printf ("%d {%d,%d,%d,%d,%d,%d,%d,%d,%d},\n", ++x, a, b, c, d, e, f, g, h, i); } } } } } } } } }

by **P.O.** » Thu Dec 26, 2024 9:20 am

in your procedure you write: for each template of digit 1, for each template of digit 2 etc. doesn't that indicate that you have all the templates for each value available?

in the second link you give pjb explicitly write:
"Generate all patterns for each number in separate arrays and order them by increasing size."

it is difficult to reconcile this with:
"(...) to avoid storing the valid (possible) templates (...) without keep tracking the templates (...)"

i have a procedure similar to the one you describe, a DFS backtracking algorithm, i use it to count the number of solutions and possibly to recover them but i need to have all the templates for each value

it should also be noted that such a procedure strictly speaking does not provide a resolution path for the puzzle; it does not make the grid evolve progressively towards its solution, allowing a classification of the puzzles into the maximum size of combinations sufficient to solve them and also does not allow us to know which combinations actually solve the puzzles.

by **rjamil** » Thu Dec 26, 2024 3:19 pm

Hi P.O.,

Many thanks for your experience based advice and wise counselling.

Well, I'll use static two-dimensional array containing 46,656 x 9 templates. (The 3 x 5184 x 8, 9 x 60 and 8, i.e., less than ~~one-third~~ 30% of actual POM templates are only for fun and used for single-digit POM when first row's cell is already known.)
I have programmed robust search method to find a specific digit's template on the fly without need to store it anywhere.
I see no need to get each digit's template out of all first; and, then manipulate them separately.

R. Jamil

by **rjamil** » Fri Jan 03, 2025 3:49 am

Hi experts,

While I am still thinking to code multi-digit POM, found too much unnecessary combinations searching, say for example, for two-digit, need to search either 9! (or 36) pair of unique digits; or, 72 (or 9 x 8) pair of unique digits, as mentioned in my and P.O. above posts.

Googling this and that; and reading here and there for any efficient way for the same, found Google AI response as follows:

Searched: how to program multi-digit pattern overlay method for sudoku
AI Overview:-
To program the multi-digit Pattern Overlay Method (POM) for Sudoku, you can:

Start with a cell that has two remaining candidates, also known as a bivalue cell
Use the POM analysis for both digits
Analyze the effects of placing either digit in the cell
Ensure that the patterns of both digits do not overlap
Make deductions based on the analysis, which may also affect the starting cell

Here are some other things to keep in mind when using the POM method:

You can write the pattern identifiers in a single grid instead of using a separate grid for each pattern
Cells that contain all pattern identifiers must contain the selected digit
Cells that contain no pattern identifiers cannot contain the selected digit
You can label the patterns with letters, such as "a", "b", and "c"
Cells with "ab" must contain the number
Cells with no "a" or "b" cannot contain the number

The above Google AI suggestion comes from Sudopedia site.

My question is, has anyone tried to search multi-digit POM this way? Is this method efficient if searched for each bivalue cell, then trivalue and then quadvalue?

R. Jamil

Added as on 20250104: OMG!!! Google AI quoted from sudopedia.org site. Where as, sudopedia.enjoysudoku.com (mirror site) and sudopedia.sudocue.net described with an example of multi-digit pattern overlay method.

by **rjamil** » Sat Jan 04, 2025 2:58 pm

Hi expert,

Sorry to bother again.

After reading above mentioned sudopedia mirror and sudocue sites, I have finally concluded to search multi-digit POM as follows:

For each digitA (in 1 ... 9)
For each valid template for digitA (in 46,656 templates)
Search each digitB (in 1 ... 9 except digitA) (in 46,656 templates)
If a valid template for digitB found (search only first occurence of valid template for digitB) then count digitA disjoint cell positions for digitB and go to step 2
If no valid template of digitB found then go to step 3
If a valid template for digitA found then apply single-digit POM elimination / placement for digitA
Go to step 1

Hope my idea to search two-digit POM is easy-to-understand and may be perfect.

However, I am now trying to convert three-dimensional 3 x 5,184 x 8 array along with two-dimensional 9 x 60 array; and two dimensional array 46,656 x 9 in to bitwise 3 x 5,184 along with 9 x 60; and 46,656 along with 9 x 60 arrays respectively.

R. Jamil

by **P.O.** » Sat Jan 04, 2025 6:54 pm

hi R. Jamil,
forming the size 2 combinations is the first and the simplest step in the use of template combinations
here's how i do it:
- get all possible templates for each value
this cannot be avoided and it is very easy and quick to do
- make all the compatible instances for the 36 size 2 combinations, two templates being compatible if their intersection is empty
for each template for 1 make the intersection with each template for 2 if the intersection is empty it makes a pair (1 2)
(...)
for each template for 8 make the intersection with each template for 9 if the intersection is empty it makes a pair (8 9)
- eliminate the templates which does not appear in all their combination groups as said here
an example #78 again from the second list here:

Code: Select all: .234..7..4...89.....9...........5.3....2..9.....37.2.55...4.8...67....9...1.2...7 after singles: 168 2 3 4 156 16 7 1568 9 4 15 56 7 8 9 1356 2 136 7 158 9 156 3 2 156 14568 1468 2 7 468 168 9 5 16 3 1468 1368 1358 4568 2 16 1468 9 7 1468 1689 189 468 3 7 1468 2 1468 5 5 39 2 169 4 7 8 16 136 38 6 7 158 15 138 4 9 2 389 4 1 5689 2 368 356 56 7 128 candidates. Templates Initialization: #VT: (32 1 3 4 7 24 1 8 2) Cells: nil nil nil nil nil nil nil (8 20) nil SetVC: ( n8r1c8 n8r3c2 n5r1c5 n6r5c5 n1r8c5 n5r8c4 ) #VT: (6 1 3 4 4 9 1 5 2) Cells: nil nil nil nil nil nil nil nil nil Candidates:(26 27) nil nil nil (16) nil nil (37 46) nil 16 2 3 4 5 16 7 8 9 4 15 56 7 8 9 136 2 136 7 8 9 16 3 2 156 456 46 2 7 468 18 9 5 16 3 1468 13 135 458 2 6 148 9 7 148 169 19 468 3 7 148 2 146 5 5 39 2 69 4 7 8 16 136 38 6 7 5 1 38 4 9 2 389 4 1 689 2 368 356 56 7 90 candidates.

the set of possible templates after initialization:

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

these are the templates with which the combinations are made.
this list indicates the number of instances for each combinations in lexical order:
(6 7 12 14 11 6 17 9 3 4 4 9 1 5 2 12 6 18 3 9 4 9 19 4 7 8 19 4 18 8 9 23 9 5 2 6) = 312
these instances:

Hidden Text: Show

Code: Select all: (1 2): 6 .2...1....1.....2......21..2..1........2....11.....2....2....1.....1...2..1.2.... .2...1....1.....2......21..2..1.....1..2...........21...2.....1....1...2..1.2.... 12..............21...1.2...2.....1.....2.1....1....2....2....1.....1...2..1.2.... 12..............21...1.2...2.....1...1.2..........12....2....1.....1...2..1.2.... 12.............12....1.2...2.......1...2.1....1....2....2....1.....1...2..1.2.... 12.............12....1.2...2.......1.1.2..........12....2....1.....1...2..1.2.... (1 3): 7 ..3..1....1......3....3.1.....1...3.3.......11..3......3.....1.....13.....1...3.. ..3..1....1....3......3.1.....1...3..3......11..3............13....13...3.1...... ..3..1....1....3......3.1.....1...3..3......11..3............133...1......1..3... 1.3............3.1...13..........13..3...1....1.3............13....13...3.1...... 1.3............3.1...13..........13..3...1....1.3............133...1......1..3... 1.3............1.3...13...........313....1....1.3......3.....1.....13.....1...3.. 1.3............1.3...13...........3131..........3.1....3.....1.....13.....1...3.. (1 4): 12 ...4.1...41.............1.4..41..........4..11......4.....4..1.....1.4...41...... ...4.1...41.............14....1....4.....4..11.4..........4..1.....1.4...41...... ...4.1...41.............14....1....4..4.....11....4.......4..1.....1.4...41...... ...4.1...41.............14....1....41....4.....4....1.....4...1....1.4...41...... ...4.1...41.............14....1....41.4...........4.1.....4...1....1.4...41...... ...4.1...41.............14...41.....1.......4.....4.1.....4...1....1.4...41...... 1..4.....4.......1...1...4.......1.4..4..1....1...4.......4..1.....1.4...41...... 1..4.....4.......1...1...4...4...1.......1..4.1...4.......4..1.....1.4...41...... 1..4.....4.......1...1....4..4...1...1...4........1.4.....4..1.....1.4...41...... 1..4.....4.......1...1...4.......1.4.1...4.....4..1.......4..1.....1.4...41...... 1..4.....4.....1.....1...4...4.....1.....1..4.1...4.......4..1.....1.4...41...... 1..4.....4.....1.....1....4..4.....1.1...4........1.4.....4..1.....1.4...41...... (1 5): 14 ....51....15............15....1.5....5......11.......55......1....51......1...5.. ....51....15............15....1.5...15..............155.......1...51......1...5.. 1...5......5.....1...1...5......51...5...1....1......55......1....51......1...5.. 1...5......5.....1...1..5.......51...5...1....1......55......1....51......1....5. 1...5.....5......1...1...5......51....5..1....1......55......1....51......1...5.. 1...5.....5......1...1..5.......51....5..1....1......55......1....51......1....5. 1...5.....5......1...1...5......51...15...........1..55......1....51......1...5.. 1...5.....5......1...1..5.......51...15...........1..55......1....51......1....5. 1...5......5...1.....1...5......5..1.5...1....1......55......1....51......1...5.. 1...5......5...1.....1..5.......5..1.5...1....1......55......1....51......1....5. 1...5.....5....1.....1...5......5..1..5..1....1......55......1....51......1...5.. 1...5.....5....1.....1..5.......5..1..5..1....1......55......1....51......1....5. 1...5.....5....1.....1...5......5..1.15...........1..55......1....51......1...5.. 1...5.....5....1.....1..5.......5..1.15...........1..55......1....51......1....5. (1 6): 11 6....1....1....6.....6..1....61.........6...11......6........16.6..1......1..6... 6....1....1......6...6..1.....1..6..1...6......6....1........61.6..1......1..6... 6....1....1....6.....6..1.....1....61...6......6....1........61.6..1......1..6... 1....6.....6.....1...1...6.......1.6....61...61..........6...1..6..1......1...6.. 1....6.....6.....1...1..6........1.6....61...61..........6...1..6..1......1....6. 1....6.....6.....1...1...6.......1.6.1..6....6....1......6...1..6..1......1...6.. 1....6.....6.....1...1..6........1.6.1..6....6....1......6...1..6..1......1....6. 1....6.....6...1.....1....6......6.1....61...61..........6...1..6..1......1....6. 1....6.....6...1.....1...6.......6.1....61...61..............16.6..1......16..... 1....6.....6...1.....1....6......6.1.1..6....6....1......6...1..6..1......1....6. 1....6.....6...1.....1...6.......6.1.1..6....6....1..........16.6..1......16..... (1 7): 6 .....17...1.7.....7.....1...7.1............711...7.........7.1...7.1......1.....7 .....17...1.7.....7.....1...7.1.....1......7.....7..1......7..1..7.1......1.....7 1.....7.....7....17..1......7....1.......1.7..1..7.........7.1...7.1......1.....7 1.....7.....7....17..1......7....1...1.....7.....71........7.1...7.1......1.....7 1.....7.....7..1..7..1......7......1.....1.7..1..7.........7.1...7.1......1.....7 1.....7.....7..1..7..1......7......1.1.....7.....71........7.1...7.1......1.....7 (1 8): 17 .....1.8..1..8.....8....1.....1....8.....8..11.8............81.8...1......18..... .....1.8..1..8.....8....1.....1....8..8.....11....8.........81.8...1......18..... .....1.8..1..8.....8....1.....1....81....8.....8....1.......8.18...1......18..... .....1.8..1..8.....8....1.....1....81.8...........8.1.......8.18...1......18..... .....1.8..1..8.....8....1....81.....1.......8.....8.1.......8.18...1......18..... 1......8.....8...1.8.1...........1.8..8..1....1...8.........81.8...1......18..... 1......8.....8...1.8.1........8..1.......1..8.18............81.....18...8.1...... 1......8.....8...1.8.1........8..1.......1..8.18............81.8...1......1..8... 1......8.....8...1.8.1.......8...1.......1..8.1...8.........81.8...1......18..... 1......8.....8...1.8.1...........1.8.1...8.....8..1.........81.8...1......18..... 1......8.....8...1.8.1........8..1...1......8..8..1.........81.....18...8.1...... 1......8.....8...1.8.1........8..1...1......8..8..1.........81.8...1......1..8... 1......8.....8.1...8.1........8....1.....1..8.18............81.....18...8.1...... 1......8.....8.1...8.1........8....1.....1..8.18............81.8...1......1..8... 1......8.....8.1...8.1.......8.....1.....1..8.1...8.........81.8...1......18..... 1......8.....8.1...8.1........8....1.1......8..8..1.........81.....18...8.1...... 1......8.....8.1...8.1........8....1.1......8..8..1.........81.8...1......1..8... (1 9): 9 .....1..9.1...9.....9...1.....19..........9.119..........9...1.....1..9.9.1...... .....1..9.1...9.....9...1.....19....1.....9...9.....1....9....1....1..9.9.1...... .....1..9.1...9.....9...1.....19....1.....9..9......1..9......1....1..9...19..... 1.......9.....9..1..91.........9.1.......19..91........9.....1.....1..9...19..... 1.......9.....9..1..91.........9.1...1....9...9...1......9...1.....1..9.9.1...... 1.......9.....9..1..91.........9.1...1....9..9....1....9.....1.....1..9...19..... 1.......9.....91....91.........9...1.....19..91........9.....1.....1..9...19..... 1.......9.....91....91.........9...1.1....9...9...1......9...1.....1..9.9.1...... 1.......9.....91....91.........9...1.1....9..9....1....9.....1.....1..9...19..... (2 3): 3 .23.............23....32...2......3.3..2........3..2...32...........3..2....2.3.. .23............32.....32...2......3..3.2........3..2....2.....3.....3..23...2.... .23............32.....32...2......3..3.2........3..2....2.....33.......2....23... (2 4): 4 .2.4.....4......2......2..42.4.........2.4.........24...2.4..........4.2.4..2.... .2.4.....4......2......2.4.2.......4...2.4.....4...2....2.4..........4.2.4..2.... .2.4.....4......2......2.4.2.......4..42..........42....2.4..........4.2.4..2.... .2.4.....4......2......2.4.2.4.........2....4.....42....2.4..........4.2.4..2.... (2 5): 4 .2..5......5....2......2.5.2....5....5.2...........2.55.2.........5....2....2.5.. .2..5......5....2......25..2....5....5.2...........2.55.2.........5....2....2..5. .2..5.....5.....2......2.5.2....5.....52...........2.55.2.........5....2....2.5.. .2..5.....5.....2......25..2....5.....52...........2.55.2.........5....2....2..5. (2 6): 9 .2...6.....6....2......2..62.....6.....26....6.....2....2....6..6......2...62.... .2...6.....6....2......2..62.....6.....26....6.....2....26......6......2....2..6. .2...6.....6....2......2.6.2.......6...26....6.....2....26......6......2....2.6.. .2...6.....6....2......2.6.2.....6.....26....6.....2....2.....6.6......2...62.... .2...6.....6....2......26..2.......6...26....6.....2....2....6..6......2...62.... .2...6.....6....2......26..2.......6...26....6.....2....26......6......2....2..6. 62..............26...6.2...2.....6.....26......6...2....2....6..6......2....26... 62.............62....6.2...2.......6...26......6...2....2....6..6......2....26... 62.............62....6.2...2.6.........26..........26...2.....6.6......2....26... (2 7): 1 .2....7.....7...2.7....2...27..........2...7.....7.2....2..7.....7.....2....2...7 (2 8): 5 .2.....8.....8..2..8...2...2.......8...2.8.....8...2....2...8..8.......2...82.... .2.....8.....8..2..8...2...2.......8..82..........82....2...8..8.......2...82.... .2.....8.....8..2..8...2...2..8........2....8..8...2....2...8.......8..28...2.... .2.....8.....8..2..8...2...2..8........2....8..8...2....2...8..8.......2....28... .2.....8.....8..2..8...2...2.8.........2....8.....82....2...8..8.......2...82.... (2 9): 2 .2......9.....9.2...9..2...2...9.......2..9...9....2....29............929...2.... .2......9.....9.2...9..2...2...9.......2..9..9.....2...92.............92...92.... (3 4): 12 ..34.....4.......3....3...4..4....3.3....4......3...4..3..4.........34...4....3.. ..34.....4.......3....3..4........343....4.....43......3..4.........34...4....3.. ..34.....4.......3....3..4........343.4.........3.4....3..4.........34...4....3.. ..34.....4.......3....3..4...4....3.3.......4...3.4....3..4.........34...4....3.. ..34.....4.....3......3...4..4....3..3...4......3...4.....4...3.....34..34....... ..34.....4.....3......3..4........34.3...4.....43.........4...3.....34..34....... ..34.....4.....3......3..4........34.34.........3.4.......4...3.....34..34....... ..34.....4.....3......3..4...4....3..3......4...3.4.......4...3.....34..34....... ..34.....4.....3......3...4..4....3..3...4......3...4.....4...33.....4...4...3... ..34.....4.....3......3..4........34.3...4.....43.........4...33.....4...4...3... ..34.....4.....3......3..4........34.34.........3.4.......4...33.....4...4...3... ..34.....4.....3......3..4...4....3..3......4...3.4.......4...33.....4...4...3... (3 5): 6 ..3.5......5.....3....3.5.......5.3.35..........3....553..........5.3.........35. ..3.5.....5......3....3.5.......5.3.3.5.........3....553..........5.3.........35. ..3.5.....5....3......3..5......5.3..35.........3....55.......3...5.3...3.....5.. ..3.5.....5....3......3.5.......5.3..35.........3....55.......3...5.3...3......5. ..3.5.....5....3......3..5......5.3..35.........3....55.......33..5..........35.. ..3.5.....5....3......3.5.......5.3..35.........3....55.......33..5..........3.5. (3 6): 18 ..3..6.....6.....3....3...6......63.3...6....6..3......3.....6..6...3......6..3.. ..3..6.....6.....3....3...6......63.3...6....6..3......3.6......6...3.........36. ..3..6.....6.....3....3..6.......63.3...6....6..3......3......6.6...3......6..3.. ..3..6.....6.....3....3.6.........363...6....6..3......3.....6..6...3......6..3.. ..3..6.....6.....3....3.6.........363...6....6..3......3.6......6...3.........36. 6.3............6.3...63...........363...6......63......3.....6..6...3........63.. 6.3............6.3...63......6....3.3...6.......3...6..3......6.6...3........63.. ..3..6.....6...3......3...6......63..3..6....6..3............63.6...3...3..6..... ..3..6.....6...3......3...6......63..3..6....6..3........6....3.6...3...3......6. ..3..6.....6...3......3..6........36.3..6....6..3........6....3.6...3...3.....6.. ..3..6.....6...3......3.6.........36.3..6....6..3............63.6...3...3..6..... ..3..6.....6...3......3.6.........36.3..6....6..3........6....3.6...3...3......6. 6.3............3.6...63..........63..3..6......63............63.6...3...3....6... ..3..6.....6...3......3...6......63..3..6....6..3............6336..........6.3... ..3..6.....6...3......3...6......63..3..6....6..3........6....336............3.6. ..3..6.....6...3......3..6........36.3..6....6..3........6....336............36.. ..3..6.....6...3......3.6.........36.3..6....6..3............6336..........6.3... ..3..6.....6...3......3.6.........36.3..6....6..3........6....336............3.6.

Hidden Text: Show

Code: Select all: (3 7): 3 ..3...7.....7....37...3.....7.....3.3......7....37.....3...7.....7..3.........3.7 ..3...7.....7..3..7...3.....7.....3..3.....7....37.........7..3..7..3...3.......7 ..3...7.....7..3..7...3.....7.....3..3.....7....37.........7..33.7...........3..7 (3 8): 9 ..3....8.....8...3.8..3...........383....8.....83......3....8..8....3......8..3.. ..3....8.....8...3.8..3...........383.8.........3.8....3....8..8....3......8..3.. ..3....8.....8...3.8..3.......8...3.3.......8..83......3....8..8....3........83.. ..3....8.....8...3.8..3......8....3.3.......8...3.8....3....8..8....3......8..3.. ..3....8.....8.3...8..3...........38.3...8.....83...........8.38....3...3..8..... ..3....8.....8.3...8..3...........38.38.........3.8.........8.38....3...3..8..... ..3....8.....8.3...8..3.......8...3..3......8..83...........8.38....3...3....8... ..3....8.....8.3...8..3......8....3..3......8...3.8.........8.38....3...3..8..... ..3....8.....8.3...8..3.......8...3..3......8..83...........8.33....8...8....3... (3 9): 4 ..3.....9.....9..3..9.3........9..3.3.....9...9.3......3.9..........3.9.9.....3.. ..3.....9.....93....9.3........9..3..3....9..9..3......9......3.....3.9.3..9..... ..3.....9.....93....9.3........9..3..3....9...9.3........9....33......9.9....3... ..3.....9.....93....9.3........9..3..3....9..9..3......9......33......9....9.3... (4 5): 9 ...45....4.5.............54..4..5....5...4..........455...4.......5..4...4....5.. ...45....4.5............5.4..4..5....5...4..........455...4.......5..4...4.....5. ...45....45..............54..4..5.....5..4..........455...4.......5..4...4....5.. ...45....45.............5.4..4..5.....5..4..........455...4.......5..4...4.....5. ...45....4.5............54......5..4.5...4.....4.....55...4.......5..4...4.....5. ...45....45.............54......5..4..5..4.....4.....55...4.......5..4...4.....5. ...45....4.5............54......5..4.54...........4..55...4.......5..4...4.....5. ...45....4.5............54...4..5....5......4.....4..55...4.......5..4...4.....5. ...45....45.............54...4..5.....5.....4.....4..55...4.......5..4...4.....5. (4 6): 19 ...4.6...4.6.............64..4.....6....64...6......4....64.....6....4...4....6.. ...4.6...4.6.............64..4...6......64...6......4.....4...6.6....4...4.6..... ...4.6...4.6............6.4..4.....6....64...6......4.....4..6..6....4...4.6..... ...4.6...4.6............6.4..4.....6....64...6......4....64.....6....4...4.....6. 6..4.....4.......6...6....4..4...6......64.....6....4.....4..6..6....4...4...6... 6..4.....4.....6.....6....4..4.....6....64.....6....4.....4..6..6....4...4...6... ...4.6...4.6.............46......6.4....64...6.4..........4..6..6....4...4.6..... ...4.6...4.6.............46......6.4....64...6.4.........64.....6....4...4.....6. 6..4.....4.....6.....6...4...6.....4....64.....4....6.....4...6.6....4...4...6... ...4.6...4.6.............46......6.4..4.6....6....4.......4..6..6....4...4.6..... ...4.6...4.6.............46......6.4..4.6....6....4......64.....6....4...4.....6. 6..4.....4.......6...6...4.......6.4..4.6......6..4.......4..6..6....4...4...6... 6..4.....4.....6.....6...4...6.....4..4.6.........4.6.....4...6.6....4...4...6... ...4.6...4.6.............46..4...6......6...46....4.......4..6..6....4...4.6..... ...4.6...4.6.............46..4...6......6...46....4......64.....6....4...4.....6. ...4.6...4.6............64...4.....6....6...46....4.......4..6..6....4...4.6..... ...4.6...4.6............64...4.....6....6...46....4......64.....6....4...4.....6. 6..4.....4.......6...6...4...4...6......6...4..6..4.......4..6..6....4...4...6... 6..4.....4.....6.....6...4...4.....6....6...4..6..4.......4..6..6....4...4...6... (4 7): 4 ...4..7..4..7.....7.......4.74...........4.7.....7..4.....47.....7...4...4......7 ...4..7..4..7.....7......4..7......4.....4.7...4.7........47.....7...4...4......7 ...4..7..4..7.....7......4..7......4..4....7.....74.......47.....7...4...4......7 ...4..7..4..7.....7......4..74.............74....74.......47.....7...4...4......7 (4 8): 7 ...4...8.4...8.....8......4..4.....8..8..4........8.4.....4.8..8.....4...4.8..... ...4...8.4...8.....8......4..48..........4..8..8....4.....4.8.......84..84....... ...4...8.4...8.....8......4..48..........4..8..8....4.....4.8..8.....4...4...8... ...4...8.4...8.....8.....4...8.....4.....4..8..4..8.......4.8..8.....4...4.8..... ...4...8.4...8.....8.....4....8....4..4.....8..8..4.......4.8.......84..84....... ...4...8.4...8.....8.....4....8....4..4.....8..8..4.......4.8..8.....4...4...8... ...4...8.4...8.....8.....4...4.....8.....8..4..8..4.......4.8..8.....4...4.8..... (4 9): 8 ...4....94....9.....9.....4..4.9.........49...9.....4....94..........49.94....... ...4....94....9.....9.....4..4.9.........49..9......4..9..4..........49..4.9..... ...4....94....9.....9....4.....9...4.....49...94.........94..........49.94....... ...4....94....9.....9....4.....9...4.....49..9.4.......9..4..........49..4.9..... ...4....94....9.....9....4.....9...4..4...9...9...4......94..........49.94....... ...4....94....9.....9....4.....9...4..4...9..9....4....9..4..........49..4.9..... ...4....94....9.....9....4...4.9..........9.4.9...4......94..........49.94....... ...4....94....9.....9....4...4.9..........9.49....4....9..4..........49..4.9..... (5 6): 19 6...5......5.....6...6...5......56...5..6......6.....55......6..6.5..........65.. 6...5......5...6.....6...5......5..6.5..6......6.....55......6..6.5..........65.. 6...5......5...6.....6...5...6..5....5..6...........655.......6.6.5..........65.. 6...5......5.....6...6..5.......56...5..6......6.....55......6..6.5..........6.5. 6...5......5...6.....6..5.......5..6.5..6......6.....55......6..6.5..........6.5. 6...5......5...6.....6..5....6..5....5..6...........655.......6.6.5..........6.5. ....56....56.............56.....56....5.6....6.......55......6..6.5........6..5.. ....56....56.............56.....56....5.6....6.......55..6......6.5...........56. ....56....56............65......5..6..5.6....6.......55......6..6.5........6..5.. ....56....56............65......5..6..5.6....6.......55..6......6.5...........56. 6...5.....5......6...6...5......56....5.6......6.....55......6..6.5..........65.. 6...5.....5....6.....6...5......5..6..5.6......6.....55......6..6.5..........65.. 6...5.....5....6.....6...5...6..5.....5.6...........655.......6.6.5..........65.. ....56....56............5.6.....56....5.6....6.......55......6..6.5........6...5. ....56....56............56......5..6..5.6....6.......55..6......6.5...........65. ....56....56............56......56....5.6....6.......55.......6.6.5........6...5. 6...5.....5......6...6..5.......56....5.6......6.....55......6..6.5..........6.5. 6...5.....5....6.....6..5.......5..6..5.6......6.....55......6..6.5..........6.5. 6...5.....5....6.....6..5....6..5.....5.6...........655.......6.6.5..........6.5. (5 7): 4 ....5.7....57.....7......5..7...5....5.....7.....7...55....7.....75...........5.7 ....5.7....57.....7.....5...7...5....5.....7.....7...55....7.....75............57 ....5.7...5.7.....7......5..7...5.....5....7.....7...55....7.....75...........5.7 ....5.7...5.7.....7.....5...7...5.....5....7.....7...55....7.....75............57 (5 8): 18 ....5..8...5.8.....8.....5......5..8.5...8.....8.....55.....8..8..5........8..5.. ....5..8...5.8.....8.....5......5..8.58...........8..55.....8..8..5........8..5.. ....5..8...5.8.....8.....5....8.5....5......8..8.....55.....8.....5.8...8.....5.. ....5..8...5.8.....8.....5....8.5....5......8..8.....55.....8..8..5..........85.. ....5..8...5.8.....8.....5...8..5....5......8.....8..55.....8..8..5........8..5.. ....5..8...5.8.....8....5.......5..8.5...8.....8.....55.....8..8..5........8...5. ....5..8...5.8.....8....5.......5..8.58...........8..55.....8..8..5........8...5. ....5..8...5.8.....8....5.....8.5....5......8..8.....55.....8.....5.8...8......5. ....5..8...5.8.....8....5.....8.5....5......8..8.....55.....8..8..5..........8.5. ....5..8...5.8.....8....5....8..5....5......8.....8..55.....8..8..5........8...5. ....5..8..5..8.....8.....5......5..8..5..8.....8.....55.....8..8..5........8..5.. ....5..8..5..8.....8.....5....8.5.....5.....8..8.....55.....8.....5.8...8.....5.. ....5..8..5..8.....8.....5....8.5.....5.....8..8.....55.....8..8..5..........85.. ....5..8..5..8.....8.....5...8..5.....5.....8.....8..55.....8..8..5........8..5.. ....5..8..5..8.....8....5.......5..8..5..8.....8.....55.....8..8..5........8...5. ....5..8..5..8.....8....5.....8.5.....5.....8..8.....55.....8.....5.8...8......5. ....5..8..5..8.....8....5.....8.5.....5.....8..8.....55.....8..8..5..........8.5. ....5..8..5..8.....8....5....8..5.....5.....8.....8..55.....8..8..5........8...5. (5 9): 8 ....5...9..5..9.....9....5.....95....5....9...9......55..9........5...9.9.....5.. ....5...9..5..9.....9....5.....95....5....9..9.......559..........5...9....9..5.. ....5...9..5..9.....9...5......95....5....9...9......55..9........5...9.9......5. ....5...9..5..9.....9...5......95....5....9..9.......559..........5...9....9...5. ....5...9.5...9.....9....5.....95.....5...9...9......55..9........5...9.9.....5.. ....5...9.5...9.....9....5.....95.....5...9..9.......559..........5...9....9..5.. ....5...9.5...9.....9...5......95.....5...9...9......55..9........5...9.9......5. ....5...9.5...9.....9...5......95.....5...9..9.......559..........5...9....9...5. (6 7): 9 .....67....67.....7.......6.7....6......6..7.6...7.........7.6..67.........6....7 .....67....67.....7.......6.7....6......6..7.6...7.......6.7....67.............67 .....67....67.....7......6..7......6....6..7.6...7.......6.7....67............6.7 .....67....67.....7......6..7....6......6..7.6...7.........7..6.67.........6....7 .....67....67.....7.....6...7......6....6..7.6...7.........7.6..67.........6....7 .....67....67.....7.....6...7......6....6..7.6...7.......6.7....67.............67 6.....7.....7....67..6......7....6......6..7...6.7.........7.6..67...........6..7 6.....7.....7..6..7..6......7......6....6..7...6.7.........7.6..67...........6..7 6.....7.....7..6..7..6......76..........6..7.....7..6......7..6.67...........6..7 (6 8): 23 .....6.8...6.8.....8......6...8..6......6...86.8............86..6...8...8..6..... .....6.8...6.8.....8......6...8..6......6...86.8............86.86..........6.8... .....6.8...6.8.....8......6......6.8....68...6.8.........6..8..86..........8...6. .....6.8...6.8.....8......6......6.8..8.6....6....8......6..8..86..........8...6. .....6.8...6.8.....8......6...8..6......6...86.8.........6..8...6...8...8......6. .....6.8...6.8.....8......6...8..6......6...86.8.........6..8..86............8.6. .....6.8...6.8.....8......6..8...6......6...86....8......6..8..86..........8...6. .....6.8...6.8.....8.....6....8....6....6...86.8.........6..8...6...8...8.....6.. .....6.8...6.8.....8.....6....8....6....6...86.8.........6..8..86............86.. .....6.8...6.8.....8.....6...8.....6....6...86....8......6..8..86..........8..6.. .....6.8...6.8.....8.....6....8..6......6...86.8............8.6.6...8...8..6..... .....6.8...6.8.....8.....6....8..6......6...86.8............8.686..........6.8... .....6.8...6.8.....8....6.....8....6....6...86.8............86..6...8...8..6..... .....6.8...6.8.....8....6.....8....6....6...86.8............86.86..........6.8... .....6.8...6.8.....8....6.....8....6....6...86.8.........6..8...6...8...8......6. .....6.8...6.8.....8....6.....8....6....6...86.8.........6..8..86............8.6. .....6.8...6.8.....8....6....8.....6....6...86....8......6..8..86..........8...6. 6......8.....8...6.8.6...........6.8..8.6......6..8.........86.86..........8.6... 6......8.....8...6.8.6.......8...6......6...8..6..8.........86.86..........8.6... 6......8.....8.6...8.6.......8.....6....6...8..6..8.........86.86..........8.6... 6......8.....8.6...8.6.......6.....8....68.....8....6.......8.686..........8.6... 6......8.....8.6...8.6.......6.....8..8.6.........8.6.......8.686..........8.6... 6......8.....8.6...8.6.......68.........6...8..8....6.......8.6.6...8...8....6... (6 9): 9 .....6..9..6..9.....9.....6....9.6......6.9..69..........9...6..6.....9.9..6..... .....6..9..6..9.....9....6.....9.6......6.9..69..........9....6.6.....9.9..6..... .....6..9..6..9.....9...6......9...6....6.9..69..........9...6..6.....9.9..6..... 6.......9.....9..6..96.........9.6......6.9...96.........9...6..6.....9.9....6... 6.......9.....9..6..96.........9.6......6.9..9.6.......9.....6..6.....9....9.6... 6.......9.....96....96.........9...6....6.9...96.........9...6..6.....9.9....6... 6.......9.....96....96.........9...6....6.9..9.6.......9.....6..6.....9....9.6... 6.......9.....96....96.......6.9........6.9...9.....6....9....6.6.....9.9....6... 6.......9.....96....96.......6.9........6.9..9......6..9......6.6.....9....9.6... (7 8): 5 ......78....78....78........7......8.....8.7...8.7.........78..8.7.........8....7 ......78....78....78........7......8..8....7.....78........78..8.7.........8....7 ......78....78....78........7.8............78..8.7.........78....7..8...8.......7 ......78....78....78........7.8............78..8.7.........78..8.7...........8..7 ......78....78....78........78.............78....78........78..8.7.........8....7 (7 9): 2 ......7.9...7.9...7.9.......7..9..........97..9..7.......9.7.....7....9.9.......7 ......7.9...7.9...7.9.......7..9..........97.9...7.....9...7.....7....9....9....7 (8 9): 6 .......89....89....89..........9...8.....89...98.........9..8..8......9.9..8..... .......89....89....89..........9...8..8...9...9...8......9..8..8......9.9..8..... .......89....89....89.........89..........9.89.8.......9....8.......8.9.8..9..... .......89....89....89.........89..........9.8.98.........9..8..8......9.9....8... .......89....89....89.........89..........9.89.8.......9....8..8......9....9.8... .......89....89....89........8.9..........9.8.9...8......9..8..8......9.9..8.....

it is the analysis of these instances which leads to the elimination of templates
for example a template for 1 or for 2 which is not in one of the 6 instances of (1 2) is eliminated
and this analyzes is done with all the instances of the combinations
for this puzzle, this reduces the number of templates for each value from (6 1 3 4 4 9 1 5 2) to (4 1 3 4 3 4 1 5 2)
and this is enough to solve it

Code: Select all: 2combs #VT: (4 1 3 4 3 4 1 5 2) Cells: (62) nil nil nil nil nil nil nil nil SetVC: ( n1r7c8 ) #VT: (5 1 3 4 4 5 1 5 2) Cells: nil nil nil nil nil nil nil nil nil Candidates:(37) nil nil nil nil (18 48) nil nil nil EraseCC: ( n3r5c1 n8r8c1 n3r8c6 n9r9c1 n3r7c2 n6r7c9 n5r9c8 n4r3c9 n9r7c4 n3r9c7 n6r3c8 n4r6c8 n1r2c7 n3r2c9 n1r3c4 n5r3c7 n8r4c4 n6r4c7 n1r4c9 n8r5c9 n8r6c3 n1r6c6 n6r9c4 n8r9c6 n6r1c6 n5r2c2 n6r2c3 n4r4c3 n1r5c2 n5r5c3 n4r5c6 n6r6c1 n9r6c2 n1r1c1 ) 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 3 2 5 6 4 2 7 4 8 9 5 6 3 1 3 1 5 2 6 4 9 7 8 6 9 8 3 7 1 2 4 5 5 3 2 9 4 7 8 1 6 8 6 7 5 1 3 4 9 2 9 4 1 6 2 8 3 5 7 puzzle in 2(1)-Template

by **rjamil** » Sat Jan 04, 2025 8:25 pm

Hi P.O.,

Many thanks for your valuable guidance and patience.

Let me elaborate my point of view step-by-step with your reply as follows:

P.O. wrote:- get all possible templates for each value
this cannot be avoided and it is very easy and quick to do

Well, this is the point that I am planning to avoid completely. I'll search digitA template one-by-one and search digitB template. If at least one digitB template found then count digitA 9 disjoint cell positions only.

- make all the compatible instances for the 36 size 2 combinations, two templates being compatible if their intersection is empty
for each template for 1 make the intersection with each template for 2 if the intersection is empty it makes a pair (1 2)

Well, I'll suggest to check each digitA valid template against first digitB valid template is enough to satisfy that digitA template is valid. Also, I'll check all 9 digitAs' against 8 other digitBs (i.e., 9 x 8 = 72 two-digit combinations) keeping digitA searched for all instances of valid template and digitB for just one instance. If no instance of digitB found then that digitA template is considered as invalid (as I already mentioned about it earlier without conclusion here quoted:

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!!!

).

- eliminate the templates which does not appear in all their combination groups

Counting of each valid digitA 9 cell position will then make it possible to perform single-digit POM placement and elimination for digitA.

Consider the example puzzle:

Code: Select all: .------------------------.------------------------.------------------------. | 2 13 4 | 378 137 178 | 5 69 69 | | 7 5 38 | 6 9 4 | 238 28 1 | | 6 9 138 | 35 2 15 | 348 48 7 | :------------------------ ------------------------ ------------------------: | 8 12467 126 | 9 1457 156 | 27 2567 3 | | 49 2467 5 | 3478 347 678 | 1 26789 269 | | 3 167 169 | 578 157 2 | 789 56789 4 | :------------------------ ------------------------ ------------------------: | 5 34 239 | 27 6 79 | 49 1 8 | | 49 246 269 | 1 8 3 | 2479 479 5 | | 1 8 7 | 24 45 59 | 6 3 29 | '------------------------'------------------------'------------------------' .------------------------.------------------------.------------------------. | . . . | . . . | . . . | | . . . | . . . | abc de . | | . . . | . . . | A BCDEF . | :------------------------ ------------------------ ------------------------: | . adBC b | . ADEF . | e . c | | ADE ceF . | B C . | . ab d | | . . . | . . . | . . . | :------------------------ ------------------------ ------------------------: | . AD d | abce . . | BCEF . . | | BCF bE ace | . . . | dD A . | | . . . | dACDEF B . | . . abce | '------------------------'------------------------'------------------------'

Here digitA is 2 (total 5 possible templates a-e), and digitB is 4 (total 6 possible templates A-F).

In my point of view, by checking digit 2's template d against digit 4, no valid template found and hence digit 2's template d is invalid result total 4 valid templates (abce) each disjoint cell position count calculated as per following grid:

Code: Select all: .------------------------.------------------------.------------------------. | . . . | . . . | . . . | | . . . | . . . | abc *e . | | . . . | . . . | A BCDEF . | :------------------------ ------------------------ ------------------------: | . a*BC b | . ADEF . | e . c | | ADE ceF . | B C . | . ab * | | . . . | . . . | . . . | :------------------------ ------------------------ ------------------------: | . AD * | abce . . | BCEF . . | | BCF bE ace | . . . | *D A . | | . . . | *ACDEF B . | . . abce | '------------------------'------------------------'------------------------'

Applying digit 2 POM will result as mentioned in the site as:

Cells r7c4 and r9c9 participate in all of the remaining patterns for candidate 2 (abce). Thus, we know that those two cells must be a 2.
Cells r5c9, r7c3, r8c7, and r9c4 no longer occur in any pattern for candidate 2. We can therefore eliminate 2 as a possible candidate for these cells.

R. Jamil

by **P.O.** » Sun Jan 05, 2025 11:11 am

starting from this resolution state and doing only the combinations of size 2 i arrive at the same assertions and eliminations concerning the value 2:

Code: Select all: 2 13 4 378 137 178 5 69 69 7 5 38 6 9 4 238 28 1 6 9 138 35 2 15 348 48 7 8 12467 126 9 1457 156 27 2567 3 49 2467 5 3478 347 678 1 26789 269 3 167 169 578 157 2 789 56789 4 5 34 239 27 6 79 49 1 8 49 246 269 1 8 3 2479 479 5 1 8 7 24 45 59 6 3 29 133 candidates. #VT: (5 5 5 6 4 9 31 10 6) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil nil nil 2combs #VT: (5 4 5 5 4 9 21 10 5) Cells: nil (58 81) nil nil nil nil nil nil nil SetVC: ( n2r7c4 n4r9c4 n5r9c5 n9r9c6 n2r9c9 n7r7c6 ) #VT: (5 4 5 5 2 9 17 10 5) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil nil nil nil nil nil nil 2 13 4 378 137 18 5 69 69 7 5 38 6 9 4 238 28 1 6 9 138 35 2 15 348 48 7 8 12467 126 9 147 156 27 2567 3 49 2467 5 378 347 68 1 26789 69 3 167 169 578 17 2 789 56789 4 5 34 39 2 6 7 49 1 8 49 246 269 1 8 3 479 479 5 1 8 7 4 5 9 6 3 2 113 candidates. 2combs #VT: (5 4 5 4 2 6 17 10 4) Cells: nil nil nil nil nil nil nil nil nil Candidates:nil nil nil (65) nil (44) nil nil (66) 2 13 4 378 137 18 5 69 69 7 5 38 6 9 4 238 28 1 6 9 138 35 2 15 348 48 7 8 12467 126 9 147 156 27 2567 3 49 2467 5 378 347 68 1 2789 69 3 167 169 578 17 2 789 56789 4 5 34 39 2 6 7 49 1 8 49 26 26 1 8 3 479 479 5 1 8 7 4 5 9 6 3 2 110 candidates.

it should be noted that the reasoning of the author of the example you cite is based on knowledge of all possible templates for 2 and 4
but there are of course several ways to obtain the same result, implement the method you are thinking of and let's see its applications with examples.

by **rjamil** » Sun Jan 05, 2025 12:24 pm

Hi P.O.,

P.O. wrote:it should be noted that the reasoning of the author of the example you cite is based on knowledge of all possible templates for 2 and 4
but there are of course several ways to obtain the same result, implement the method you are thinking of and let's see its applications with examples.

I appreciate the way you supported me and now allowing me to implement the multi-digit POM search routine my way.

I have an idea in mind as how to do it intellengently, without loosing robust and exhaustive criteria.

However, I have successfully converted the three-dimensional P[3][5184][8] array in to two-dimensional P[3][5184] array by replacing the 8 template cells with one 32-bit integer value. Now, I am in the process of converting the two-dimensional R[9][60] array in to three-dimensional R[9][8][8] array, in order to avoid some additional calculations inserted due highly compressed one 32-bit integer value containing 3 bit of 8 template cells each, at the cost of additional 9 x 4 elements as wastage.

Hope, the full and final outcome will be the most highly compressed form of the POM static data, stored in to P[3][5184], R[9][8][8] and T[2][8] arrays.

Comparing the original POM[46656][9] == total 419,904 elements with (P[3][5184] = 15,552) + (R[9][8][8] = 576) + (T[2][8] = 16) == total 16,144 elements only, i.e., less than 3.85% data.

R. Jamil

Added: Wish to inform that, I have achieved the most highly compressed form of the POM static data successfully. My GitHub repositories for RJSudoku.c and RJSukaku.c are updated accordingly.

I have found the post of Dobrichev in which he suggested the same concept first, for which I have inspired from, as step D under [Hidden Text]. (I admit that my idea is not new.)

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