The New Sudoku Players' Forum

[daj95376]

This may be the "partial templates" to which denis_berthier referred not too many posts ago.

Did you use "partial templates" within your templates() pre-screen for GFF() too?

IMO, denis' reference to "partial templates" is a reference to our n-templates for n < 9. An example from Tungsten Rod:

Code: Select all

 <123467>-templates      r4c4,r456c5<>5
   elims = 4
   combinations = 19561


No, I don't use partial templates anywhere in my normal solver. I especially wouldn't use them in GFF() because it's single-value logic applied to each digit.

[eleven]

Sorry, i had not time to read both this thread and Mladen's program carefully.

What i dont understand is:
In pjb's method (which seems to be equivalent to Ruud's ?), no intermediate results are used, because it is done DFS ? Doing it BFS, e.g. examining all templates for digits 1234 could exclude templates for each of them, making other combinations with one or more of these digits simpler.
If we are dumb for such intermediate results, we only would look for one combination of digits, which solves the puzzle, like 1234567.
And there is no need to look at 9! combinations, because the order of the digits is not relevant. E.g 3*4*7 combinations would be enough to look, if a puzzle can be solved with 7 digits.

But when you use intermediate results, it could be possible to solve a puzzle applying 123456 and 235679 templates, which otherwise would need 7 digits.

Is that right ?
What did you mean with your definition, Denis ?

[ronk]

This may be the "partial templates" to which denis_berthier referred not too many posts ago.

IMO, denis' reference to "partial templates" is a reference to our n-templates for n < 9.

Hmm, you may well be correct, but it's poor English IMO. I await denis_berthier's reply to my previous question on this point.

Did you use "partial templates" within your templates() pre-screen for GFF() too?

No, I don't use partial templates anywhere in my normal solver. I especially wouldn't use them in GFF() because it's single-value logic applied to each digit.

I think you switched from my definition of "partial templates" to yours.

[eleven]

Ok, Denis seems to be away.
Anyway, i gave it some more thoughts, and i hope to be clearer now.

For a puzzle P, define TD(P), the template-depth of P, as the minimum number of digits such that:
there is a way of choosing templates for TD(P) digits and a way of ordering the remaining 9 - TD(P) digits such that there is at each step a unique possibility for the templates for each of these remaining digits;
...
- what is the maximal template-depth for all the minimal puzzles?
... (other post:)
Alternative formulation: applying BFS (breadth-first search) instead of DFS to templates, what is the maximal depth of search necessary to solve all the minimal puzzles?

First i want to note, that Mladen already had implemented pjb's algorithm long before, in a very effective way, its what he described as "last resort" in the comments heading his code:

//Step Z. Last resort: Reorder digits (relabel) in accending order by number of templates, perform 9 nested loops, find all disjoint templates.

[Edit:] What i said here was wrong. In fact pjb's method needs level 8 to find a solution for e.g. "champagne dry". However you select 7 out of the 9 digitss (126 ways) and calculate all compatible 7-templates, there will always remain several possibilities for the last 2 templates. So you have to check an 8th digit to find a solution.[/edit]

More interesting i find another question. It would be stupid to implement the algorithm breadth first (BFS) without trying to get "intermediate results", which allow you to exclude subtrees (of the searching tree consisting of the nodes with all template combinations of 1-9 digits), before continuing with the next node or level. Otherwise you would visit all the same nodes, but would need a lot more memory.
Also here Mladen already showed, how this can be done, in his

//Step D. Remove all templates that have not at least one disjoint template for each of the other digits.
//Repeat until solution found or no more eliminations exist.

Now this could not only be done for pairs of digits, but also triples, quatrupels etc. E.g. you can calculate all compatible=disjoint templates for digits 1234. After that you can eliminate all possible templates you have at this moment for each of the digits, which are not part of the combined templates.
Doing it this way, i guess that the highest level you need to solve all (known) puzzles is less than 7, and i wonder, if its 5 or less or more.
(Of course this way of solving the puzzles would be a lot slower than Mladen's implementation).

One more remark:

- is there any relationship between template-depth and difficulty (measured e.g. by SER)?

Of course there will be some relationship, and i guess more for the second version. But in both cases the ratings will be significantly different to those you get by "chains" rating methods like SER, because its a basically different way of solving. Its a kind of meta coloring. We know, that there are simple examples for eliminations with coloring, which need complicated chains/nets and vice versa. To my knowledge under the public ratings only champagne's rating gives both sides wide room.

[pjb]

Thank you daj95376

It took me a while to get my head around your response as I am not a serious programmer, and bitmaps, etc I am yet to take on. However, the penny finally dropped and it all seemed so obvious. Starting with all valid templates for all numbers, take any 6 and find the subset of templates which are mutually compatible. Then use the reduced number of templates to identify candidates which are no longer members of the remaining templates. I have enabled this technique, so far for only 6 digits (I wanted to validate the methodology by comparing with your results for 'tungsten rod'), and installed it on my website (www.philsfolly.net.au). Below is the result of checking all of the 84 combinations of 6 from 9:

Hidden Text: Show

Tungsten rod after basics including naked quad in b3:

Code: Select all

34589  4568   34689  | 12356  123569 15689  | 24     1389   7     
3589   2      3789   | 4      13579  15789  | 1389   6      389   
1      4678   346789 | 2367   23679  6789   | 5      389    24     
---------------------+----------------------+---------------------
358    9      1378   | 13567  13567  2      | 1378   4      358   
2345   1457   12347  | 8      13457  157    | 6      13579  2359   
6      14578  123478 | 9      13457  157    | 12378  13578  2358   
---------------------+----------------------+---------------------
2489   1468   5      | 1267   12679  3      | 4789   789    4689   
49     3      1469   | 1567   8      15679  | 479    2      4569   
7      68     2689   | 256    2569   4      | 389    3589   1     

Number of patterns for current state are: 1: 30, 2: 10, 3: 75, 4: 24, 5: 42, 6: 28, 7: 57, 8: 97, 9: 56

Total number of combinations for 123456 are 14948
Total number of combinations for 123457 are 5221
Total number of combinations for 123458 are 28968
Total number of combinations for 123459 are 15726
Total number of combinations for 123467 are 19561
Total number of combinations for 123468 are 34095
Total number of combinations for 123469 are 19857
Total number of combinations for 123478 are 33912
Total number of combinations for 123479 are 19225
Total number of combinations for 123489 are 16437
Total number of combinations for 123567 are 3922
Eliminations for 3 in r2c5 (1)
Total number of combinations for 123568 are 37508
Total number of combinations for 123569 are 27929
Total number of combinations for 123578 are 15890
Total number of combinations for 123579 are 9222
Total number of combinations for 123589 are 21517
Total number of combinations for 123678 are 52513
Total number of combinations for 123679 are 36311
Total number of combinations for 123689 are 17465
Total number of combinations for 123789 are 27864
Total number of combinations for 124567 are 3337
Total number of combinations for 124568 are 26516
Total number of combinations for 124569 are 17209
Total number of combinations for 124578 are 18056
Total number of combinations for 124579 are 10374
Total number of combinations for 124589 are 42467
Total number of combinations for 124678 are 20225
Total number of combinations for 124679 are 12026
Total number of combinations for 124689 are 8393
Total number of combinations for 124789 are 26684
Total number of combinations for 125678 are 9975
Total number of combinations for 125679 are 4122
Total number of combinations for 125689 are 20409
Total number of combinations for 125789 are 15577
Total number of combinations for 126789 are 14531
Total number of combinations for 134567 are 282
Eliminations for 3 in r123c5 r4c4 (4)
Eliminations for 4 in r3c2 (1)
Eliminations for 5 in r1c146 r2c6 r4c45 r5c159 r6c59 r8c6 r9c5 (13)
Eliminations for 6 in r3c5 r78c4 (3)
Eliminations for 7 in r3c3c6 r7c7(3)
Total number of combinations for 134568 are 35355
Total number of combinations for 134569 are 37080
Total number of combinations for 134578 are 22374
Total number of combinations for 134579 are 19655
Total number of combinations for 134589 are 80259
Total number of combinations for 134678 are 57666
Total number of combinations for 134679 are 52969
Total number of combinations for 134689 are 62067
Total number of combinations for 134789 are 97323
Total number of combinations for 135678 are 2963
Eliminations for 3 in r2c5 (1)
Total number of combinations for 135679 are 3645
Eliminations for 3 in r2c5 (1)
Total number of combinations for 135689 are 24458
Total number of combinations for 135789 are 13790
Total number of combinations for 136789 are 36746
Total number of combinations for 145678 are 3536
Total number of combinations for 145679 are 2213
Total number of combinations for 145689 are 32717
Total number of combinations for 145789 are 24814
Total number of combinations for 146789 are 26231
Total number of combinations for 156789 are 342
Eliminations for 5 in r1c146 r2c6 r4c45 r5c159 r6c59 r8c6 r9c5 (13)
Eliminations for 6 in r3c5 r78c4 (3)
Eliminations for 7 in r3c36 r7c7 (3)
Eliminations for 9 in r12c5 (2)
Total number of combinations for 234567 are 19850
Total number of combinations for 234568 are 29210
Total number of combinations for 234569 are 15638
Total number of combinations for 234578 are 53087
Total number of combinations for 234579 are 30201
Total number of combinations for 234589 are 17184
Total number of combinations for 234678 are 70970
Total number of combinations for 234679 are 38591
Total number of combinations for 234689 are 6429
Eliminations for 3 in in r2c5 (1)
Total number of combinations for 234789 are 46722
Total number of combinations for 235678 are 64934
Total number of combinations for 235679 are 53285
Total number of combinations for 235689 are 11750
Total number of combinations for 235789 are 48751
Total number of combinations for 236789 are 52479
Total number of combinations for 245678 are 47335
Total number of combinations for 245679 are 28489
Total number of combinations for 245689 are 19698
Total number of combinations for 245789 are 77171
Total number of combinations for 246789 are 27176
Total number of combinations for 256789 are 46258
Total number of combinations for 345678 are 44443
Total number of combinations for 345679 are 46762
Total number of combinations for 345689 are 31327
Total number of combinations for 345789 are 119770
Total number of combinations for 346789 are 109871
Total number of combinations for 356789 are 40086
Total number of combinations for 456789 are 47691

These results are very similar but slightly different to daj95376's (not sure why at present). I look forward to implementing other subsets when I have time.
Philip

[daj95376]

pjb: You appear to have one set of eliminations working -- those for values in the 6-tuple:

Code: Select all

 <123567>-templates      r2c5<>3
   elims = 1
   combinations = 3922


You are still missing eliminations for values that aren't in the 6-tuple:

Code: Select all

 <123467>-templates      r4c4,r456c5<>5
   elims = 4
   combinations = 19561


Initialize bitmap bm_all where all of the cells are set to True. Every time you obtain a legitimate 6-tuple combination, zero bitmap bm_temp and perform an OR operation of the templates -- bm_temp OR bm_template[i=1..9]. Now, perform bm_all = bm_all AND bm_temp.

For each of the 19561 6-tuples in <123467>-templates, bm_temp will indicate the cells where a 6-tuple value has been assigned. Recursively ANDing bm_temp with bm_all will result in bm_all indicating the cells where at least one of the 6-tuple values is assigned for every combination. This means that any other candidates in these cells can be eliminated.

[pjb]

daj95376

Thank you for the response. I can see I need to upgrade my skills for logical operations of bitmaps. In the real world I look after sick babies, so I'm out of my comfort zone here conversing with experts in maths and computing. I'm hoping all this will delay Alzheimer's. I will go away and try to digest what you suggest.

Philip

[eleven]

Doing it this way, i guess that the highest level you need to solve all (known) puzzles is less than 7, and i wonder, if its 5 or less or more.

Its probably 6.
I only had time to adopt Mladen's program to check all 5 digit templates for possible templates eliminations (and repeat that, when eliminations could be made). This did not solve about 13% of the puzzles in the hardest list. The first of them is

Code: Select all

1.......9.5....2....87...4.2...3......48.5....8.6...7...6..4.5.........1....9.3.. (ED 11.8 11.8 07.9)

The method only could reduce the number of templates for the 9 digits from

Code: Select all

39 50 62 8 24 95 28 43 31

to

Code: Select all

11 14 17 8 14 24 14 28 13

[daj95376]

I only had time to adopt Mladen's program to check all 5 digit templates for possible templates eliminations (and repeat that, when eliminations could be made). This did not solve about 13% of the puzzles in the hardest list. The first of them is

Code: Select all

1.......9.5....2....87...4.2...3......48.5....8.6...7...6..4.5.........1....9.3.. (ED 11.8 11.8 07.9)

The method only could reduce the number of templates for the 9 digits from

Code: Select all

39 50 62 8 24 95 28 43 31

to

Code: Select all

11 14 17 8 14 24 14 28 13

I wasn't as successful as eleven using 5-templates.

Code: Select all

Templates: 39 50 62 8 24 95 28 43 31

 <45678>-templates     r28c1<>39; r4c2<>19; r5c2<>67;
                       r2c5,r4c7<>1; r18c5,r9c9<>2; r2c9<>3; r6c3<>5;
                       r3c26,r5c8<>6; r7c2,r8c3<>7; r8c7<>9
   elims = 21
   combinations = 239

Templates: 23 36 38 8 16 36 18 43 17


My next eliminations came from 7-templates.

However, I did manage to work through the puzzle using 4/5/6/7-templates to get the solution.

Code: Select all

123456789457189236698723145265937814734815692981642573316274958579368421842591367


[eleven]

I wasn't as successful as eleven using 5-templates.

These are the candidates i had at the end. If i made no mistake, here no method can lead to an elimination, which does not use at least 6 digits.

Code: Select all

 *-------------------------------------------------------------*
 | 1     23467  237   | 2345  4568  2368   | 5678  368   9     |
 | 467   5      379   | 149   468   13689  | 2     1368  678   |
 | 369   239    8     | 7     1256  1239   | 156   4     356   |
 |--------------------+--------------------+-------------------|
 | 2     67     1579  | 149   3     179    | 4568  1689  4568  |
 | 3679  139    4     | 8     127   5      | 169   1239  236   |
 | 359   8      139   | 6     124   129    | 1459  7     2345  |
 |--------------------+--------------------+-------------------|
 | 3789  1239   6     | 123   1278  4      | 789   5     278   |
 | 4578  23479  2359  | 235   5678  23678  | 4678  2689  1     |
 | 4578  1247   1257  | 125   9     1678   | 3     268   4678  |
 *-------------------------------------------------------------*

With 6-digit templates all puzzles in the hardest list could be solved.
[Edit2:]
I had wrong results with 4-templates solutions of the puzzles in the hardest list. These should be correct now:
6% of the first 100, 9.1% of 1000, 15.1 % of 5000, 16.8% of 10000, and 18.9 % of 14258 could be solved with 4-digit templates.
The first one is

Code: Select all

12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7;11.90;11.90;2.60;elev;1;5

So there is some correlation with this "templates rating" and SER.
On the other hand there will be many puzzles with lower ER like Tungston Rod, which need 6-digit templates.

[daj95376]

My templates logic doesn't quite match eleven's.

Code: Select all

 after 5-templates
 +------------------------------------------------------------------------+
 |  1      23467  237    |  2345   4568   2368    |  5678   368    9      |
 |  467    5      379    |  1(3)49 468    13689   |  2      1368   678    |
 |  369    239    8      |  7      1256   1239    |  156    4      356    |
 |-----------------------+------------------------+-----------------------|
 |  2      67     1579   |  149    3      179     |  4568   1689   4568   |
 |  3679   139    4      |  8      127    5       |  169    1239   236    |
 |  359    8      139    |  6      124    129     |  1459   7      2345   |
 |-----------------------+------------------------+-----------------------|
 |  3789   1239   6      |  123    1278   4       |  789    5      278    |
 |  4578   23479  2359   |  235    5678   23678   |  4678   2689   1      |
 |  4578   1247   1257   |  125    9      1(2)678 |  3      268    4678   |
 +------------------------------------------------------------------------+

 # 157 eliminations remain in my  grid

 # 155 eliminations remain in his grid


[eleven]

My templates logic doesn't quite match eleven's.

Hm, the 3 in r2c4 vanished very early, after the 5 templates 12345-12349, the 2 in r9c6 late in the 4th test of the digits 12359.

I had a bug, when calculating the 4-digit-templates. I updated the results in my last post.


PS: This is, what i have left for Tungston Rod after 5-digit templates:

Code: Select all

  27 10 53 24 32 28 45 84 51
 *---------------------------------------------------------------------*
 | 34589  4568   34689   | 12356  123569  15689  | 24     1389   7     |
 | 3589   2      3789    | 4      1579    15789  | 1389   6      389   |
 | 1      4678   346789  | 2367   23679   6789   | 5      389    24    |
 |-----------------------+-----------------------+---------------------|
 | 358    9      1378    | 13567  13567   2      | 1378   4      358   |
 | 2345   1457   12347   | 8      13457   157    | 6      13579  2359  |
 | 6      14578  123478  | 9      13457   157    | 12378  13578  2358  |
 |-----------------------+-----------------------+---------------------|
 | 2489   1468   5       | 1267   12679   3      | 4789   789    4689  |
 | 49     3      1469    | 1567   8       15679  | 479    2      4569  |
 | 7      68     2689    | 256    2569    4      | 389    3589   1     |
 *---------------------------------------------------------------------*

[ronk]

I took another look at candidate eliminations for Tungsten Rod. With an assist from the <157>-ALS in r56c6, there remain 29 <157>-template sets.

"29 <157>-template sets": Show

Code: Select all

.5.1....7..7.5.1..1...7.5..5.1...7......17.5..7...5.1..15....7....7.1..57..5....1
.5.1....7..7.5.1..1...7.5..5.1...7...7...5.1.....17.5..15....7....7.1..57..5....1
.5.1....7..7.5.1..1...7.5..5...1.7....1..7.5..7...5.1..15....7....7.1..57..5....1
...15...75...7.1..17....5....7.1...5..1..5.7..5...7.1..157........5.17..7......51
.5.1....7..7.5.1..1...7.5..5...1.7...7...5.1...1..7.5..15....7....7.1..57..5....1
...15...75...7.1..17....5....7.1...5.5...7.1...1..5.7..157........5.17..7......51
.5..1...7..7.5.1..1..7..5..5.1.7.....7...1.5......571..15....7....1.7..57..5....1
.5..1...7..7.5.1..1..7..5..5.1...7...7...1.5.....75.1..15....7....1.7..57..5....1
.5..1...7..7.5.1..1..7..5..5.1...7......71.5..7...5.1..15....7....1.7..57..5....1
.5..1...7..7.5.1..1...7.5..5.17......7...1.5......571..15....7....1.7..57..5....1
.5..1...7..7.5.1..1..7..5..5.1.7.....7...5.1......175..15....7....1.7..57..5....1
.5..1...7..7.5.1..1..7..5..5.1...7...7...5.1.....71.5..15....7....1.7..57..5....1
.5..1...7..7.5.1..1..7..5..5.1...7......75.1..7...1.5..15....7....1.7..57..5....1
.5..1...7..7.5.1..1...7.5..5.17......7...5.1......175..15....7....1.7..57..5....1
.5..1...7..7.5.1..1...7.5..5..1..7....1..7.5..7...5.1..15....7....7.1..57..5....1
.5..1...7..7.5.1..1...7.5..5..1..7...7...5.1...1..7.5..15....7....7.1..57..5....1
.5...1..7..7.5.1..1...7.5..5..1..7...1...7.5..7...5.1...5.1..7...17....57..5....1
....51..75...7.1..17....5....71....5.1...5.7..5...7.1...571......15..7..7......51
.5...1..7..7.5.1..1...7.5..5..1..7...7...5.1..1...7.5...5.1..7...17....57..5....1
....51..75...7.1..17....5....71....5.5...7.1..1...5.7...571......15..7..7......51
.5...1..7..7.5.1..1...7.5..5...1.7...1...7.5..7...5.1...51...7...17....57..5....1
.5...1..7..7.5.1..1...7.5..5...1.7...7...5.1..1...7.5...51...7...17....57..5....1
....5..175...17...17....5.....7..1.5.17..5....5...1.7...517......15..7..7......51
....5..175...17...17....5.....7..1.5.1...5.7..57..1.....517......15..7..7......51
....5..175...17...17....5.....7..1.5.57..1....1...5.7...517......15..7..7......51
....5..175...17...17....5.....7..1.5.5...1.7..17..5.....517......15..7..7......51
.5.....17..7.51...1...7.5..5..1..7...1...7.5..7...51....5.1..7...17....57..5....1
....5..175...71...17....5....71....5.1...5.7..5...71....571......15..7..7......51
.5.....17..7.51...1...7.5..5...1.7...1...7.5..7...51....51...7...17....57..5....1


These 29 <157>-template sets imply the following eliminations, [edit: which match those posted by champagne here.]

Code: Select all

r1c146, r2c6, r4c45, r5c159, r6c59, r8c6, r9c5<>5

r3c36, r7c7<>7

r2c5, r8c4=157 implying r2c5<>39, r8c4<>6

[edit: previous list of 15 <157>-template sets was incomplete]

[daj95376]

Hm, the 3 in r2c4 vanished very early, after the 5 templates 12345-12349, the 2 in r9c6 late in the 4th test of the digits 12359.

Thanks! A bug existed when I used 9-choose-N with indexing of 1..9, and failed to properly align it with indexing of 0..8 for an array in C. However, there's still a discrepancy because I need to use 6-templates for r9c6<>2. Hmmm!

[David P Bird]

This is the PM grid for Tungsten Rod after (5) has been identified as being true in r56c6 as per my post of 29th Jan

Code: Select all

 |----------------------|-----------------------|--------------------|
 | 3489  4568  (34689 ) | (1236) 123569  (1689) | (24   ) 1389  7    |
*| 3589  2      3789    | (4   ) 157     (1789) |  1389   6     389  |*
 | 1     4678  (346789) | (2367) 23679   (6789) | (5    ) 389   24   |
 |----------------------|-----------------------|--------------------|
*| 358   9      1378    | (1367) (1367 )  2     |  1378   4     358  |*
 | 234   1457  (12347 ) | (8   ) (1347 )  157   | (6    ) 13579 239  |
 | 6     14578 (123478) | (9   ) (1347 )  157   | (12378) 13578 238  |
 |----------------------|-----------------------|--------------------|
 | 2489  1468  (5     ) |  1267  (12679) (3   ) | (4789 ) 789   4689 |
*| 49    3      1469    |  157   (8    ) (1679) |  479    2     4569 |*
 | 7     68    (2689)   |  256   (269  ) (4   ) | (389  ) 3589  1    |
 |----------------------|-----------------------|--------------------|

Similar sets of exclusions will be available for (1) and (7) when one of them is found to be the second digit in r56c6. As they share the same columns in the partial fish covering rows 248, a common exclusion map can be constructed using brackets to show the cells involved.

There are now two cases; in case 1 these cells contain no (7)s and in case 2 they contain no (1)s. Considering case 0 to be the known case for (5), chains for each digit can be constructed showing their equivalences with the focus on the potential (157)Deadly Patterns in r56c268.

Case 0: (5)r56c8 = (5)r9c8 - (5)r9c4 = (5)r8c4 -[Exocet]- (5)r2c5 = (5)r1c5 - (5)r1c2 = (5)r56c2
Case 1: (1)r56c8 = (1)r4c7 - (1)r2c7 = (1)r2c5 -[Exocet]- (1)r8c4 = (1)r8c3 - (1)r4c3 = (1)r56c2
Case 2: (7)r56c2 = (7)r4c2 - (7)r2c3 = (7)r2c5 -[Exocet]- (7)r8c4 = (7)r8c7 - (7)r4c7 = (7)r56c8

The nodes for case 0, can be combined step by step with those for either case 1 or 2, to show that in case (1) a (15)UR will exist either in r56c26 or r56c68, but not in case 2 for the (57) pairing, so eliminating (1) as a base digit.

(7) can therefore be eliminated from 14 bracketed cells and (1) can be eliminated from 4 cells for the base and target nodes.

A further (1) can also be eliminated just by considering digits (157) from this chain:
(1)r1c8 = (1)r56c8 –[(157)DP:r56c268]- (1)r56c2 = (1)r7c2 – (1)r8c3 = (1)r8c6 => r1c6 <> 1

I haven't got the tools to examine the 157 templates that include uncovered Deadly Patterns, but it might be worth exploring. Of course it depends on whether the aim is to find one solution or all solutions for the input puzzle.