The New Sudoku Players' Forum

[P.O.]

Is it then check single-digit POM elimination/placement move first?
I think, there is no elimination/placement possible for double-digit POM move as all subset combinations contain only valid (possible) templates against each other.

each time templates are eliminated, i check whether there is placement or elimination of candidates
combinations are made from possible templates, but some of them do not fit into the combinations and are therefore eliminated and as the combinations are checked for validity this results in new template eliminations

Hidden Text: Show

Code: Select all

2.4...5..75.694..169..2...78..9....3..5...1..3....2..45...6..18...183..5187...63.

initialization:
(5 10 5 6 6 9 34 12 6)      #VT before checking
(5  5 5 5 6 9 24 12 5)      #VT after checking

#VT: (5 5 5 5 6 9 24 12 5)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL (57 61 71) NIL (58 65) NIL NIL (61) NIL NIL        eliminations found

2      13     4      378    137    178    5      689    69             
7      5      38     6      9      4      238    28     1               
6      9      138    358    2      158    348    48     7               
8      12467  126    9      1457   1567   27     2567   3               
49     2467   5      3478   347    678    1      26789  269             
3      167    169    578    157    2      789    56789  4               
5      234    39     27     6      79     49     1      8               
49     26     269    1      8      3      2479   479    5               
1      8      7      245    45     59     6      3      29             
137 candidates. 34 values.

 2combs done
 (18 11 14 15 21 43 23 14 12 11 11 11 45 18 12 9 19 31 39 17 11 13 24 34 28 11 22 43 23 12 71 46 10 94 43 34)
 number of instances of the 36 size 2 combinations in lexical order (1 2) (1 3) etc.
 they are checked for validity and reduce the number of templates from (5 5 5 5 6 9 24 12 5) to (5 4 5 5 4 8 16 8 4) which are then checked for validity
 
(5 4 5 5 4 8 16 8 4)      #VT before checking
(5 4 5 5 4 6 14 8 3)      #VT after checking

#VT: (5 4 5 5 4 6 14 8 3)
Cells: NIL (58 81) NIL NIL NIL NIL (60) NIL (78)              placements found
SetVC: ( n2r7c4   n7r7c6   n9r9c6   n2r9c9 )

#VT: (5 4 5 5 4 6 14 8 3)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL (44) NIL (8 22 24) (44 66)    eliminations found

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      1457   156    27     2567   3               
49     2467   5      3478   347    68     1      278    69             
3      167    169    578    157    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      45     45     9      6      3      2               
116 candidates. 38 values.

 2combs done
 36 new sets of size 2 combinations
(16 11 12 8 7 26 13 9 8 10 9 9 31 10 11 8 11 17 20 11 9 8 14 24 17 8 12 25 11 7 45 24 8 32 25 14)
they are checked for validity and reduce the number of templates from (5 4 5 5 4 6 14 8 3) to (3 4 5 5 3 5 13 6 3) which are then checked for validity

(3 4 5 5 3 5 13 6 3)    #VT before checking
(1 1 1 1 1 1 1 1 1)     #VT after checking

#VT: (1 1 1 1 1 1 1 1 1)
Cells: (5 21 33 47) (17 34 38 66) (2 16 22 41 57) (25 32 37 56 71 76) (24 35 49 77)       ste.
       (9 30 42 53 65) (4 29 44 50 70) (6 12 26 40 52) (8 45 48 61 64)
SetVC: ( n3r1c2   n7r1c4   n1r1c5   n8r1c6   n9r1c8   n6r1c9   n8r2c3   n3r2c7   n2r2c8   n1r3c3
         n3r3c4   n5r3c6   n4r3c7   n8r3c8   n7r4c2   n6r4c3   n4r4c5   n1r4c6   n2r4c7   n5r4c8
         n4r5c1   n2r5c2   n8r5c4   n3r5c5   n6r5c6   n7r5c8   n9r5c9   n1r6c2   n9r6c3   n5r6c4
         n7r6c5   n8r6c7   n6r6c8   n4r7c2   n3r7c3   n9r7c7   n9r8c1   n6r8c2   n2r8c3   n7r8c7
         n4r8c8   n4r9c4   n5r9c5 )
2 3 4   7 1 8   5 9 6
7 5 8   6 9 4   3 2 1
6 9 1   3 2 5   4 8 7
8 7 6   9 4 1   2 5 3
4 2 5   8 3 6   1 7 9
3 1 9   5 7 2   8 6 4
5 4 3   2 6 7   9 1 8
9 6 2   1 8 3   7 4 5
1 8 7   4 5 9   6 3 2


[rjamil]

Hi P.O.,

each time templates are eliminated, i check whether there is placement or elimination of candidates
combinations are made from possible templates, but some of them do not fit into the combinations and are therefore eliminated and as the combinations are checked for validity this results in new template eliminations

Now, it seems to me that, after filter performed, single-digit POM move should be checked. If no single-digit POM elimination/placement found then there will also be no double-digit POM elimination/placement found.

Now, if I comment about your above mentioned method in database model, it is called many-to-many relationship method, i.e., complexity and redundancy at the cost of time impact. (However, if you achieved positive results with no time barriers then its up to you.)

Where as, I am using normalized one-to-many relationship only without any barriers.

R. Jamil

[P.O.]

i have a template procedure that solves puzzles by combining templates only, with no relation to the grid other than initially retrieving the possible templates
combining templates has the effect of eliminating those that are not part of the solution(s), and that alone is enough to solve all puzzles
it should also be noted that it is not necessary to check the validity of templates or combinations, doing so only speeds up the process by eliminating more templates earlier and in the case of a single-solution puzzle may reduce the maximum size of the combinations needed to solve it
here are the three situations with this puzzle
2.4...5..75.694..169..2...78..9....3..5...1..3....2..45...6..18...183..5187...63.
without n4r1c3 it has 13 solutions:

Hidden Text: Show

Code: Select all

2.....5..75.694..169..2...78..9....3..5...1..3....2..45...6..18...183..5187...63.

2      134    1348   378    137    178    5      4689   69             
7      5      38     6      9      4      238    28     1               
6      9      1348   358    2      158    348    48     7               
8      12467  1246   9      1457   1567   27     2567   3               
49     2467   5      3478   347    678    1      26789  269             
3      167    169    578    157    2      789    56789  4               
5      234    2349   247    6      79     2479   1      8               
49     246    2469   1      8      3      2479   2479   5               
1      8      7      245    45     59     6      3      29             
153 candidates. 33 values.

initialization
(7 7 6 13 6 9 31 17 5)

2 combs
(7 6 6 9 6 8 23 14 4)

2 combs
(7 5 6 9 6 8 18 14 4)

2 combs
(7 5 6 9 6 8 18 14 4)

3 combs
(6 5 6 5 4 8 8 9 4)

2 combs
(5 4 6 5 4 7 8 9 4)

2 combs
(5 4 6 5 4 7 8 9 4)

3 combs
(4 4 5 5 4 5 8 7 4)

2 combs
(4 4 5 5 4 5 8 7 4)

3 combs
(4 4 4 5 4 5 8 7 4)

2 combs
(4 4 4 5 4 5 8 7 4)

3 combs
(4 4 4 5 4 5 8 7 4)

4 combs
(4 4 4 5 4 5 8 7 4)

5 combs
(4 4 4 5 4 5 8 7 4)

6 combs
(4 4 4 5 4 5 8 7 4)

7 combs
(4 4 4 5 4 5 8 7 4)

8 combs
(4 4 4 5 4 5 8 7 4)

9 combs
(4 4 4 5 4 5 8 7 4)

(2 2 2 3 2 2 3 2 3 2 3 4 5 6 7 8 9)
puzzle in 9-template
13 solutions
248731569753694821691825347874916253925348176316572984539267418462183795187459632
248371569753694821691825347874916253925438176316752984539267418462183795187549632
243871569758694321691325847874916253925438176316752984539267418462183795187549632
248731569753694281691825347824916753975348126316572894539267418462183975187459632
248371569753694281691825347824916753975438126316752894539267418462183975187549632
248731569753694821691825347814976253925348176376512984539267418462183795187459632
248731596753694281691825347812946753465378129379512864534267918926183475187459632
248371596753694281691825347812946753465738129379512864534267918926183475187459632
248371596753694281691528347812945763475836129369712854534267918926183475187459632
243718596758694321691325487876941253425836179319572864534267918962183745187459632
234718596758694321691325487876941253425836179319572864543267918962183745187459632
248317596753694821691528347824951763975436182316872954532769418469183275187245639
241378596753694281698521347812945763475836129369712854534267918926183475187459632


without verification it requires size 4 combinations:

Hidden Text: Show

Code: Select all

2.4...5..75.694..169..2...78..9....3..5...1..3....2..45...6..18...183..5187...63.

2      13     4      378    137    178    5      689    69             
7      5      38     6      9      4      238    28     1               
6      9      138    358    2      158    348    48     7               
8      12467  126    9      1457   1567   27     2567   3               
49     2467   5      3478   347    678    1      26789  269             
3      167    169    578    157    2      789    56789  4               
5      234    239    247    6      79     2479   1      8               
49     246    269    1      8      3      2479   2479   5               
1      8      7      245    45     59     6      3      29             
143 candidates. 34 values.

initialization
(5 10 5 6 6 9 34 12 6)

2 combs
(5 5 5 5 6 9 34 12 5)

2 combs
(5 5 5 5 6 9 24 12 5)

2 combs
(5 5 5 5 6 9 24 12 5)

3 combs
(5 5 5 5 6 8 21 10 4)

2 combs
(5 5 5 5 6 8 21 10 4)

3 combs
(5 5 5 5 6 8 19 10 4)

2 combs
(5 5 5 5 6 8 19 10 4)

3 combs
(5 5 5 5 6 8 19 10 4)

4 combs
(5 4 4 5 4 7 14 7 4)

2 combs
(5 4 4 5 4 7 12 7 3)

2 combs
(5 4 4 5 4 6 12 7 3)

2 combs
(5 4 4 5 4 6 12 7 3)

3 combs
(5 4 4 5 4 6 12 7 3)

4 combs
(3 3 3 5 3 6 8 6 3)

2 combs
(3 3 3 5 3 6 8 4 3)

2 combs
(3 3 1 5 3 6 8 4 3)

2 combs
(3 1 1 4 2 6 5 4 1)

2 combs
(3 1 1 2 2 1 3 4 1)

2 combs
(1 1 1 2 1 1 3 2 1)

2 combs
(1 1 1 2 1 1 1 1 1)

2 combs
(1 1 1 1 1 1 1 1 1)

(2 2 2 3 2 3 2 3 4 2 2 2 3 4 2 2 2 2 2 2 2)
puzzle in 4-template
1 solution
234718596758694321691325487876941253425836179319572864543267918962183745187459632


with verification size 2 combinations are sufficient:

Hidden Text: Show

Code: Select all

2.4...5..75.694..169..2...78..9....3..5...1..3....2..45...6..18...183..5187...63.

2      13     4      378    137    178    5      689    69             
7      5      38     6      9      4      238    28     1               
6      9      138    358    2      158    348    48     7               
8      12467  126    9      1457   1567   27     2567   3               
49     2467   5      3478   347    678    1      26789  269             
3      167    169    578    157    2      789    56789  4               
5      234    239    247    6      79     2479   1      8               
49     246    269    1      8      3      2479   2479   5               
1      8      7      245    45     59     6      3      29             
143 candidates. 34 values.

initialization
(5 5 5 5 6 9 24 12 5)

2 combs
(5 4 5 5 4 6 14 8 3)

2 combs
(1 1 1 1 1 1 1 1 1)

(2 2)
puzzle in 2-template
1 solution
234718596758694321691325487876941253425836179319572864543267918962183745187459632


[rjamil]

Hi P.O.,

Congratulations. Yoi are doing exactly as how Ruud explained in this post.

Once again, congratulations for your big achievement.

R. Jamil

[Wepwawet]

Is there any examples of some code for generating the 46656 POM templates.
Also is there a guide on how templates are processed once they have been generated.

Thanks in advance.

[rjamil]

Hi Wepwawet,

I see your interest in POM. But, don't know how much deep you are.

In my understanding, if you are interested in generating POM, i.e., 9 disjoint cells all combination for placing single digit in vanilla Sudoku 9x9 board, then, this is what I can help you. Look StrmCkr explanation and source code in Pascal; and mine in C Language.

Also, if you are fimiliar with C Language, then dig in to my source code of RJSudoku.c and RJSukaku.c program, written entirely in pure C Language, where you can find separate routines to search single-digit, double-digit and triple-digit POM moves.

Similarly, P.O. shares his source code written in Common Lisp partially.

R. Jamil

[P.O.]

hi Wepwawet,
here is the list of templates in row order with cell numbering from 0 to 80
Mladen Dobrichev provides his procedure for generating them, along with an example of their use, here

[Wepwawet]

Thanks guys for your help. My POM post certainly peked some interest. At the moment I am interested in using POM to solve advanced fish, e,g, Franken, Mutant and perhaps,some Kraken types, upto N=4.

Needless to say, I have taken a lot of the info on board, that was supplied by you guys (and from elsewhere), thanks. As it happens, I have now managed to develop some code up to the stage where I can test it, but, I have a few questions.

(i) Can all potential deletions be attributed to being a fish? If so, how does one go about ascertaining what fish it is from the templates.
(ii) When a fish digit is found to be true, what rule (or method/property) explains it

I have to admit I am surprised by the amount of deletions that can be found.

[P.O.]

(i) Can all potential deletions be attributed to being a fish? If so, how does one go about ascertaining what fish it is from the templates.
(ii) When a fish digit is found to be true, what rule (or method/property) explains it

the logic of the templates is very simple:
- 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

i don't see the need to link these eliminations and placements of candidates to the usual techniques which, according to this post by Myth Jellies are numerous:
(POM) "finds every single-digit reduction possible at that point in the puzzle. All locked candidates, x-wings, swordfish, jellyfish, finned fish, simple coloring, strong links, multi-coloring, grouped multi-coloring, x-cycles, grouped x-cycles, and franken-fish reductions for any converted digits are found"

[StrmCkr]

It also finds the few exclusions as well not found by fish ie "no fish"

For fishing templating can speed up the search when you build them backwards or skip the digits wth no elims
(hodoku does this)

[rjamil]

And, may be, Pattern Overlay Method also covered Broken-Wings techniques.

R. Jamil

[Wepwawet]

i don't see the need to link these eliminations and placements of candidates to the usual techniques"

My solver displays a move log explaining, step-by-step, which algorithm was used for every change to the puzzle, so I do need to know them. I would not employ it until all other algorithms had been exhausted (except, perhaps, Forcing chains, etc).

I just cannot see any kudos in solving a puzzle by using one technique or without reporting on the stages that led to the final solution.

As far as I am concerned the implementation to use POM to eliminate candidates or to set them, is a last resort technique. Whilst, I appreciate it is a great tool to find some of the elusive algorithms, to that end, I hope you guys can supply me with some info that I need, and please, refrain from making any explanations too complex, I am only a simple man.

So, to the point, I am stumped on some elements of POM, I have coded the single digit POM, which works incredibly fast, so no problems there, but I cannot find any info on how to process multi digit templates, neither, do I understand the labelling in the POM maths equations, for instance, what does a,b,c,d,e,f imply, what do they represent, and how are they derived. If someone would give a simple puzzle with a key guide for the labels, a,b,c,d etc, it may help my understanding of it.

[edited to tidy up sloppy semantics]

[P.O.]

combining templates allows you to eliminate those that don't fit in any of the combinations
then the single-digit POM procedure checks whether candidates can be placed or eliminated
there is an example here that makes use of letters