The New Sudoku Players' Forum

[rjamil]

Hi P.O.,

i find the same eliminations which correspond to those mentioned above in the quote from Myth Jellies but the real power of a template procedure as a solving technique begins with the combinations of templates which consists of testing the compatibility of templates for different values ​​and gradually eliminating all those which do not fit into any of them.
Do you intend to develop your procedure in this way?

Well, yes, of course, for sure, I do, most welcome, why not.

But the problem is that, there are no detail information available for the multi-digit POM. Myth Jellies declare POM as single digit elimination/placement technic. I was trying to start coding only for those technics that have sufficient information to understand (keeping language barrier) as well as to program the same (most preferably pattern based).

I see how powerful POM technic is but lack of interest and information due huge data set as one of the main reason. I finally able to shrink the entire data set, by importing the 46656 x 9 templates in XLSX file in rows 1 to 46656 x column A to I respectively, taken from StrmCkr's post. Then, sort whole data by A to I column in ascending order. Copy each 5184 chunk in to separate sheet and trying to shrink as much as possible, without loosing any data. My final compilation is available here. See, how all 46656 templates are carefully examined and converted in to 9 first row cell positions x 60 rest of the rows disjoint cell positions, without any loss of data.

For your information, I find that, AI does not have enough information and useless to help explain step-by-step and programming too.

Well, as an off topic, I think that, the multi-digit POM is exactly opposite to the multi-digit impossible patterns, for which, i started another topic to discuss here. But, again, lack of information on most powerful technics, like impossible pattern, unavoidable sets, deadly pattern, etc.

R. Jamil

[P.O.]

to compute the templates is fast and they don't need that much memory, i don't organize them, at the initialization of the puzzle i retrieve from them the possible templates for each value, which does not amount to much, less than 8000 i think
for example these must be among those which have the most:

Code: Select all

...4.6.........12.......5..2........5.1..8..........47.7..1...8.6.9.........2....
(12 7 5984 56 74 44 32 68 872)    = 7149
..34...........12........6...4.....7....61.3.8.............7..861..2.......5.....
(5 135 132 30 858 5 113 47 6229)  = 7554
.2...67....6...........1.4..94.............15.........5.1.4.......3..92.........7
(6 119 827 12 36 146 156 6276 57) = 7635
1....6...4...........2..5.......7.4.......9...68.1........4...8..29.....7.......1
(6 82 6698 8 720 102 92 68 60)    = 7836
1...............36..82.......5...4...7....8......13....3.....1.6.......7...845...
(6 660 4 64 77 62 90 4 6256)      = 7223
......7.9.5.1......8...3...23..9........7..1.....4..5......8......5....39.4......
(65 736 8 43 6 6288 54 68 4)      = 7272
..34.6.........2....9...5...4.....93....28....6.......5.......48......6....31....
(574 32 8 8 70 9 6290 68 103)     = 7162


to give an overview of what i do
i have the templates in 9 lists like this:

Code: Select all

 val 1  (1T0 1T1 1T2 1T3 ..... 1Tn)
 val 2  (2T0 2T1 2T2 2T3 ..... 2Tn)
 val 3  (3T0 3T1 3T2 3T3 ..... 3Tn)
 etc.


and i start by forming the 36 size 2 combinations:

Code: Select all

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


2 templates are compatible if their intersection is empty
i thus get a variable number of instances for each combination, the templates are indexed by their rank in their list and i preceded the instances by the combination label:

Code: Select all

 ((1 2) (0 0) (0 1) (1 2) (1 3) ...)
 ((1 3) (0 0) (0 2) (2 2) (2 3) ...)
 ((2 3) (0 0) (0 3) (2 2) (2 3) ...)
etc.


then i analyze the combinations, for example a template for value 1 is eliminated if it does not appear in each combinations: ((1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) (1 9)

from there i only use the indexes to form the following combinations, for example a size 3 combination as (1 2 3) is made up of 3 combinations of size 2: (1 2) (1 3) (2 3) and it is from the indexes of these combinations that i form the instances of (1 2 3)

then a combination of size 4 (1 2 3 4) is made up of 4 combinations of size 3 (1 2 3) (1 2 4) (1 3 4) (2 3 4) that i use to obtain the instances of (1 2 3 4)

etc.

[rjamil]

Hi P.O.,

In order to understand your logic, let me run your seven example puzzles with my RJSudoku.c program and a quick comparison of maximum number of valid templates is sharing below:

Code: Select all

...4.6.........12.......5..2........5.1..8..........47.7..1...8.6.9.........2....
PO: (12 7 5984 56 74* 44 32 68 872)    = 7149
RJ: (12 7 0 56 34* 44 0 0 0)

..34...........12........6...4.....7....61.3.8.............7..861..2.......5.....
PO: (5 135 132 30 858 5 113 47 6229)  = 7554
RJ: (5 0 0 30 0 5 0 0 0) stte

.2...67....6...........1.4..94.............15.........5.1.4.......3..92.........7
PO: (6 119 827 12 36 146 156 6276 57) = 7635
RJ: (6 119 0 0 36 0 0 0 57)

1....6...4...........2..5.......7.4.......9...68.1........4...8..29.....7.......1
PO: (6 82 6698 8 720 102 92 68 60)    = 7836
RJ: (6 82 0 8 0 0 92 0 60)

1...............36..82.......5...4...7....8......13....3.....1.6.......7...845...
PO: (6 660 4 64 77 62* 90* 4 6256)      = 7223
RJ: (6 0 4 0 0 14* 58* 4 0)

......7.9.5.1......8...3...23..9........7..1.....4..5......8......5....39.4......
PO: (65 736 8 43 6 6288 54 68* 4)      = 7272
RJ: (65 0 8 43 6 0 0 20* 4)

..34.6.........2....9...5...4.....93....28....6.......5.......48......6....31....
PO: (574 32 8 8 70 9* 6290 68* 103*)     = 7162
RJ: (0 32 8 8 0 3* 0 28* 13*) stte

Please note that, checking a digit beyond 5184 templates? Break your two dimensional array 46,656 x 9 templates into three dimensional 9 x 5,184 x 8 templates and then search each first row cell position to it's corresponding 5184 x 8 array.

R. Jamil

[P.O.]

here is how i retrieve the templates for each value taking as an example the first puzzle
...4.6.........12.......5..2........5.1..8..........47.7..1...8.6.9.........2....
i initialize the puzzle with Singles
...4.6.........12.......5..2.7......5.1..8..........47.7..1...8.6.9.........2....
i retrieve the cells of each value
(16 39 59) (17 28 77) NIL (4 53) (25 37) (6 65) (30 54 56) (42 63) (67)
for each value these are subsets of templates
i retrieve these templates
64 64 46656 576 576 576 144 576 5184
and for each value i remove the templates which have cells from the other values
(12 7 5984 56 74 44 32 68 872)

[rjamil]

Hi P.O.,

Did you not mentioned the MNVT values of each digit? Are you counting the number of templates utilized for checking each digit?

My program uses fully sorted order of 46,656 templates in highly compressed form. Let me show you how the worst case is searched:

Code: Select all

+-------+-------+-------+   +-------+-------+-------+
| X . . | . . . | . . . |   | . . . | . . . | . . X |
| . . . | X . . | . . . |   | . . . | . . X | . . . |
| . . . | . . . | X . . |   | . . X | . . . | . . . |
+-------+-------+-------+   +-------+-------+-------+
| . X . | . . . | . . . |   | . . . | . . . | . X . |
| . . . | . X . | . . . |   | . . . | . X . | . . . |
| . . . | . . . | . X . |   | . X . | . . . | . . . |
+-------+-------+-------+   +-------+-------+-------+
| . . X | . . . | . . . |   | . . . | . . . | X . . |
| . . . | . . X | . . . |   | . . . | X . . | . . . |
| . . . | . . . | . . X |   | X . . | . . . | . . . |
+-------+-------+-------+   +-------+-------+-------+

1) for each digit (1 to 9)
2) for each cell position in first row (0 to 8)
3) if first row cell position does not contain digit in either clue or solved or unsolved then go to step 2
4) for each template in first row cell position chunk (total 5184)
5) for i = 0 to 8 (2nd to 9th row disjoint cell position)
6) if i'th row disjoint cell location does not contain particular digit then go to 8
7) next for (row or go to step 5)
8) if i > 8 then increment count for all rows disjoint cell locations contain particular digit found else skip T[i] template
9) next for (template or go to step 4)
10) eliminate digit from disjoint cell location whose count is zero tmplate
11) place digit in disjoint cell location whose count is all templates
12) next for (digit or go to step 1)

Now keeping above steps in mind, for best and worst case, routine will always check all 9 digit x 9 times check in first row x (6 times skip for 2nd row disjoint cell check + 3 times for 3rd + 6 times for 4th + 4 times for 5th + 2 times for 6th + 3 times for 7th + 2 times for 8th and 9th = total 26 templates searched)

R. Jamil

[rjamil]

Ok.

I did search POM in blank Sudoku grid and here I am sharing my results showing MNVT count:

After T&E: 1r1c1, 2r1c2, 3r1c3, 4r1c4, 5r1c5 and 6r1c6:

Code: Select all

POM: Digit 7 in r1c789 r2c123456789 r3c123456789 r4c123456789 r5c123456789 r6c123456789 r7c123456789 r8c123456789 r9c123456789
Digit 7 not in 15552 Templates => -7 @ r2c7 r2c8 r2c9 r3c7 r3c8 r3c9
POM: Digit 8 in r1c789 r2c123456789 r3c123456789 r4c123456789 r5c123456789 r6c123456789 r7c123456789 r8c123456789 r9c123456789
Digit 8 not in 15552 Templates => -8 @ r2c7 r2c8 r2c9 r3c7 r3c8 r3c9
POM: Digit 9 in r1c789 r2c123456789 r3c123456789 r4c123456789 r5c123456789 r6c123456789 r7c123456789 r8c123456789 r9c123456789
Digit 9 not in 15552 Templates => -9 @ r2c7 r2c8 r2c9 r3c7 r3c8 r3c9

Then T&E: 7r1c7, 8r1c8
NS: 9r1c9
T&E: 4r2c1, 5r2c2 and 6r2c3

Code: Select all

POM: Digit 7 in r1c7 r2c456 r3c123456 r4c12345689 r5c12345689 r6c12345689 r7c12345689 r8c12345689 r9c12345689
Digit 7 not in 2592 Templates => -7 @ r3c4 r3c5 r3c6
POM: Digit 8 in r1c8 r2c456 r3c123456 r4c12345679 r5c12345679 r6c12345679 r7c12345679 r8c12345679 r9c12345679
Digit 8 not in 2592 Templates => -8 @ r3c4 r3c5 r3c6
POM: Digit 9 in r1c9 r2c456 r3c123456 r4c12345678 r5c12345678 r6c12345678 r7c12345678 r8c12345678 r9c12345678
Digit 9 not in 2592 Templates => -9 @ r3c4 r3c5 r3c6

R. Jamil

[P.O.]

i have the same results as you

Code: Select all

123456...........................................................................
#VT: (5184 5184 5184 5184 5184 5184 15552 15552 15552) MNVT = 15552
Cells: nil nil nil nil nil nil nil nil nil
Candidates: nil nil nil nil nil nil (16 17 18 25 26 27) (16 17 18 25 26 27) (16 17 18 25 26 27)
1          2          3          4          5          6          789        789        789                 
456789     456789     456789     123789     123789     123789     123456     123456     123456             
456789     456789     456789     123789     123789     123789     123456     123456     123456             
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
23456789   13456789   12456789   12356789   12346789   12345789   123456789  123456789  123456789           
567 candidates.


123456789456.....................................................................
#VT: (5184 5184 5184 864 864 864 2592 2592 2592) MNVT = 5184
Cells: nil nil nil nil nil nil nil nil nil
Candidates: nil nil nil nil nil nil (22 23 24) (22 23 24) (22 23 24)

1         2         3         4         5         6         7         8         9                 
4         5         6         123789    123789    123789    123       123       123               
789       789       789       123       123       123       123456    123456    123456             
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
2356789   1346789   1245789   12356789  12346789  12345789  12345689  12345679  12345678           
477 candidates.


consider these puzzles and the template count calculated by Dobrichev, these are for each value the number of valid templates at the beginning even before Singles is applied, with Singles the count is slightly different for Platinum Blonde and Fata Morgana,

the MNVT, an acronym coined by Mathimagics, designates for each puzzle the highest value, for example the MNVT of Easter Monster is 148, that of Golden Nugget is 108 etc.

these are the templates i'm talking about and that i retrieve at the beginning of the template procedure after Singles in the way i indicated in the previous post

can we start from there, can you get the same number of templates at the beginning of the procedure

[rjamil]

Hi P.O.,

My program is far inferior to solve those well known the hardest puzzles.

Sorry for unable to solve the puzzles with singleton, POM and T&E searching moves enabled. (Please note that, I can't remove singleton moves because it is highly integrated with T&E move. However, rest of the moves are independently coded and may be stop searching any or all of them.)

However, if MNVT means maximum number of VALID templates, then VT means VALID templates. Right?
Similarly, you showed some count against digit not contain elimination/placement for which I don't.

I showed my program valid templates count for which it does not match with few of your provided seven puzzles.

R. Jamil

[P.O.]

However, if MNVT means maximum number of VALID templates, then VT means VALID templates. Right?
Similarly, you showed some count against digit not contain elimination/placement for which I don't.
I showed my program valid templates count for which it does not match with few of your provided seven puzzles.

yes VT means valid templates, but more precisely the templates that are possible, like candidates that are possible, for each value
and for these puzzles the template count has been done before Singles

these puzzles are just an example of what needs to be calculated at the beginning of a template procedure: for each value the set of possible templates, this is the first thing to do in order to be able to make the template combinations

[rjamil]

Hi P.O.,

these puzzles are just an example of what needs to be calculated at the beginning of a template procedure: for each value the set of possible templates, this is the first thing to do in order to be able to make the template combinations

After thinking, I assume that, my program is able to search POM correctly (as I can't show VT for neither elimination nor placement POM move atm). So, assuming MNVT count is correct for single-digit POM move (without any filter use), how to check multi-digit POM?

R. Jamil