The New Sudoku Players' Forum

[pjb]

I have been interested in the application of patterns to solve sudokus, and have used them in two different capacities in my online solver (www.philsfolly.net.au). I order to achieve this I developed a method to generate all possible patterns for each number for a given puzzle state. Patterns are nice because by definition they already conform to the basic constraint rules. It occurred to me that these patterns could be employed to directly solve puzzles, and I've recently implemented it in my solver. Briefly, one takes the first pattern of number 1 and adds the 9 addresses to an array. One then takes the first pattern of number 2 and checks if any one of its 9 addresses coincides with one of those of the pattern for 1. If not, its 9 addresses are added to the array, otherwise it is discarded and the second pattern of number 2 is taken. By working through digits 1 to 9 using this process, one eventually ends up with all 81 addresses in the array, and the puzzle is solved.

In practice it should be used when basic techniques are exhausted, since the fewer the number of patterns the quicker the solution. Most simple puzzles are solved in moments. However, it can be applied at any stage in the process. As an example, after the SK loop eliminations in the 'easter monster' (146 extra candidates left), the puzzle is solved in a second or so.

If this was re-coded in C by someone with good programming skills, I imagine it would be impressively fast.

PJB

[ronk]

... one takes the first pattern of number 1 and adds the 9 addresses to an array. One then takes the first pattern of number 2 and checks if any one of its 9 addresses coincides with one of those of the pattern for 1. If not, its 9 addresses are added to the array, otherwise it is discarded and the second pattern of number 2 is taken. By working through digits 1 to 9 using this process, one eventually ends up with all 81 addresses in the array, and the puzzle is solved.

It sounds like you are using templating, a.k.a. the Pattern Overlay Method ("POM"). I've been unable to find the POM seminal thread by Myth Jellies, but see ...

http://sudopedia.org/wiki/Templating

http://www.sudokuwiki.org/Pattern_Overlay

[daj95376]

It sounds like you are using templating, a.k.a. the Pattern Overlay Method ("POM"). I've been unable to find the POM seminal thread by Myth Jellies, ...

Ruud and Myth Jellies posts. The original thread by Myth Jellies was lost during a computer crash, but it was reintroduced from a copy that had been archived by another user.

[pjb]

Thank you ronk & daj95376

As I mentioned in my post, I have had a particular interest in the pattern overlay method, and as such I am fully aware of your links and the pioneering postings by Myth Jellies. For some time I have had the methods described in Sudopedia & sudokuwiki implemented in my solver in the advanced set (POM button). Myth Jellies identified patterns by letters a-z and it appears to me he was limited to puzzles with a limited number of patterns. My small advance was to apply the method irrespective of how many patterns occur for a number (can be >2000). I have not as yet attempted to implement his more complicated method of substitution equations. The reference to Ruud's post is confusing as it does not appear to really be about patterns at all, but templates of all 81 cells.

While the new method I described here does involve patterns, it otherwise bares no resemblance to these previous postings. I encourage you to look a bit more closely at what I have suggested.

Regards, pjb

[ronk]

I encourage you to look a bit more closely at what I have suggested.

You mean the first paragraph of your opening post above? I don't think there's enough detail there for anyone to determine exactly what you're doing.

[pjb]

I've placed a flow diagram to clarify the logic further: http://www.philsfolly.net.au/quicksolve_help.htm. I hope this helps.
pjb

[dobrichev]

Hi pjb,

Is your approach similar to the one described in the hidden text of this post?

[pjb]

Hi dobrichev

Thank you for drawing my attention to this link. Some similarities, but really not the same. My approach differs because I'm yet to see a post where someone has firstly generated all valid patterns for each of the 9 digits. Having done this my method then takes a blank 9x9 grid and progressively adds the patterns 1 through 9 as long as any of the 9 cells doesn't overlap one added earlier. If it does then then it steps back and adds next pattern as detailed in my link above. This way it creates the solution like fitting together a jig-saw puzzle. Because a pattern for any digit has only one in each row/column/box, no further logic or eliminations are needed.

Cheers, pjb

[David P Bird]

pjb, having listed the sets of all the valid templates for each digit wouldn't it be more efficient to bring them into the work grid in set size order starting the with smallest?

It would also be possible to filter the set lists as each template is added to temporarily remove those that covered occupied cells (which would affect the order the digits were added to the grid). If one digit had no options remaining, the procedure could immediately backtrack.

[daj95376]

I consider your "patterns" to be the same as "templates". The POM is more about solving techniques using the templates -- if I recall correctly. Bottom line: there are 46,656 templates that can be partitioned onto nine sets of 5,184 templates. Sometimes, this partitioning is useful. Other times it isn't useful.

For sure, there is a difference between using templates in solving techniques and using templates as a backtracking solver. I believe that most of the posts being referenced are primarily dealing with templates in solving techniques. You appear to be using templates as a backtracking solver once you've run out of other solving techniques.

Since you mentioned the Easter Monster puzzle, I'll work from it.

Code: Select all

# Easter Monster  -- by JPF 2007 04/07/01  mm/dd/sequence

 +-----------------------+
 | 1 . . | . . . | . . 2 |
 | . 9 . | 4 . . | . 5 . |
 | . . 6 | . . . | 7 . . |
 |-------+-------+-------|
 | . 5 . | 9 . 3 | . . . |
 | . . . | . 7 . | . . . |
 | . . . | 8 5 . | . 4 . |
 |-------+-------+-------|
 | 7 . . | . . . | 6 . . |
 | . 3 . | . . 9 | . 8 . |
 | . . 2 | . . . | . . 1 |
 +-----------------------+

+--------------------------------------------------------------------------------------+
|  1        478      34578   |  3567     3689     5678    |  3489     369      2       |
|  238      9        378     |  4        12368    12678   |  138      5        368     |
|  23458    248      6       |  1235     12389    1258    |  7        139      3489    |
|----------------------------+----------------------------+----------------------------|
|  2468     5        1478    |  9        1246     3       |  128      1267     678     |
|  234689   12468    13489   |  126      7        1246    |  123589   12369    35689   |
|  2369     1267     1379    |  8        5        126     |  1239     4        3679    |
|----------------------------+----------------------------+----------------------------|
|  7        148      14589   |  1235     12348    12458   |  6        239      3459    |
|  456      3        145     |  12567    1246     9       |  245      8        457     |
|  45689    468      2       |  3567     3468     45678   |  3459     379      1       |
+--------------------------------------------------------------------------------------+

Value  Templates
-----  ---------
  1   =    41
  2   =    39
  3   =   130
  4   =    32
  5   =    18
  6   =    41
  7   =     8
  8   =   148
  9   =    18


My suggestions mirror those of David P Bird. Using a recursive approach, your level-1 choices would come from the eight templates for value=7. You can now reduce the number of usable templates for the remaining values. The level-2 choices would be for the value with the smallest number of remaining templates. You would continue recursing until you reach a solution or must backtrack. Should any value be reduced to zero usable templates at any level, then choosing that value effectively forces you to backtrack without wasting time examining choices for any other unassigned values.

[coloin]

Hi danny.
i remember when, a while back, yourself and gsf established the rules for the determination of the template count for each clue ...... we noticed then that hard puzzles like Easter Monster tended to have high counts - but it wasnt considered specific.....

its just a thought but - i wonder if taking this furthur might be more rewarding

eg looking at the counts for the 36 2-clue-templates or the 84 3-clue templates.

At some point there will be an n-clue template which reaches the minimum value [1]

I am not sure when this happens [although in easy puzzles it is at the 1-clue level]

It might also indicate the weakest link - or solving path in a puzzle

champagnes solver gets eliminations on a "level 4 or level 5" - and it was this what made me think is this similar to what is going on in POM.

C

[dobrichev]

Here are the template counts per digit after basic eliminations for few more puzzles.

Code: Select all

100000002090400050006000700050903000000070000000850040700000600030009080002000001 41  39 130  32 18 41  8 148  18 Easter Monster
000000039000001005003050800008090006070002000100400000009080050020000600400700000 47  37 108  38 32 96 52  12  16 Golden Nugget
000000012000000003002300400001800005060070800000009000008500000900040500470006000 65 111 109  34 12 50 73  24  47 Platinium Blonde
000000007020400060100000500090002040000800600600900000005003000030080020700004001 42  10 113  24 42 28 57 144  88 Tungston Rod
000000003001005600090040070000009050700000008050402000080020090003500100600000000 34 150  66 154  9 68 66  65   7 Fata Morgana
100000007020400060003000500090040000000062040000900800005000003060200080700001000 34  22  36  18 44 16 43  92 116 Silver Plate


I counted this, along with the simple product of the counts (i.e. number of the tests required) while debugging my (unfinished) implementation.
Nothing special except there are more monsters.

[pjb]

Thank you all for the input. Like many new to this enterprise, I have found it hard to encompass all that has passed before. I have struggled with the multiple names associated with some of the older techniques. I now appreciate that 'template' equals 'pattern', also equals 'rookery' (?). Ruud's post, pointed to above, I can now see is similar, except that he takes all 49000 patterns or so, and eliminates them until the valid ones remain, while the method I came up with builds them up from zero. I therefore accept that it is not so new. I changed the order in the analysis so the the patterns are processed in increasing size, with increased speed in some but not all puzzles I tested.

[daj95376]

Hi danny.

i remember when, a while back, yourself and gsf established the rules for the determination of the template count for each clue ...... we noticed then that hard puzzles like Easter Monster tended to have high counts - but it wasnt considered specific.....

its just a thought but - i wonder if taking this furthur might be more rewarding

eg looking at the counts for the 36 2-clue-templates or the 84 3-clue templates.

At some point there will be an n-clue template which reaches the minimum value [1]

I am not sure when this happens [although in easy puzzles it is at the 1-clue level]

It might also indicate the weakest link - or solving path in a puzzle

champagnes solver gets eliminations on a "level 4 or level 5" - and it was this what made me think is this similar to what is going on in POM.

Hello Coloin,

I'm not sure that I follow your line of reasoning. FWIW ...

Template logic can't tell a puzzle with a unique solution from a puzzle with multiple solutions. A puzzle with a unique solution simply means that only one combination of templates across all values can be created. But, template logic is perfectly happy with multiple solution puzzles as well. Consider a multiple solution puzzle reduced to this grid:

Code: Select all

+--------------------------------------------------+
|  9    1    2   |  5    6    3   |  7    8    4   |
|  5    6    7   |  4    8    1   |  9    3    2   |
|  8    3    4   |  2    7    9   |  1    5    6   |
|----------------+----------------+----------------|
|  3    57   1   |  8    9    4   |  2    6    57  |
|  4    57   9   |  6    3    2   |  8    1    57  |
|  2    8    6   |  7    1    5   |  3    4    9   |
|----------------+----------------+----------------|
|  6    9    8   |  3    4    7   |  5    2    1   |
|  1    2    3   |  9    5    6   |  4    7    8   |
|  7    4    5   |  1    2    8   |  6    9    3   |
+--------------------------------------------------+

Value Templates
  1  =    1
  2  =    1
  3  =    1
  4  =    1
  5  =    2
  6  =    1
  7  =    2
  8  =    1
  9  =    1

...5.....5...............5.........5.5............5.........5......5......5......
...5.....5...............5..5...............5.....5.........5......5......5......

......7....7..........7............7.7..........7..........7..........7.7........
......7....7..........7.....7...............7...7..........7..........7.7........


Templates logic is perfectly happy to have two templates remaining for <5> and <7>, and one template for each of the seven other values. In addition, template logic is willing to combine the first template for <5> and the last template for <7>. It would also be willing to combine the last template for <5> and the first template for <7>.

Bottom Line: Even with seven "pinned" values, I don't see any way template logic can foresee how templates should be selected for the two remaining values.

Regards, Danny

[ronk]

I'm not sure that I follow your line of reasoning. FWIW ...

Template logic can't tell a puzzle with a unique solution from a puzzle with multiple solutions. A puzzle with a unique solution simply means that only one combination of templates across all values can be created. But, template logic is perfectly happy with multiple solution puzzles as well.

If all template combinations are tried and more than one non-contradictory combination is found, the user of template logic might not be happy.