The New Sudoku Players' Forum

[daj95376]

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

FYI: Here's the hierarchy used in my solver for your grid.

Code: Select all

*) Naked  Singles
*) Hidden Singles
*) Locked Candidate 1
*) Locked Candidate 2
*) Single-digit template reduction and eliminations
*) quasi-dobrichev "Step D" template reduction logic
*) 2/3/4/5/6/7-templates


You have some smaller template counts for this grid, but I still find 5-templates eliminations present.

Hidden Text: Show

Code: Select all

 +--------------------------------------------------------------------------------+
 |  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       |
 +--------------------------------------------------------------------------------+
 # 185 eliminations remain

Value Templates
  1  =    30
  2  =    10
  3  =    71
  4  =    24
  5  =    42
  6  =    28
  7  =    57
  8  =    97
  9  =    56

 <13467>-templates     r4c4,r456c5<>5
   elims = 4
   combinations = 39304

 <14567>-templates     r4c4<>3
   elims = 1
   combinations = 2836

 <16789>-templates     r128c6<>5
   elims = 3
   combinations = 27955

   c5b5  Locked Candidate 1              <> 3    r13c5

         Templates (A: 1)                <> 5    r1c4,r9c5

 *** quasi-dobrichev "Step D"

Value Templates
  1  =    27
  2  =    10
  3  =    48
  4  =    24
  5  =     9
  6  =    27
  7  =    50
  8  =    88
  9  =    56

 *** then I need 6-templates to proceed


[daj95376]

[Not relevant.]

[denis_berthier]

I've been very busy since my last post.

In short:
1) by "partial template", I meant nothing more precise than not based on 9 cells. As I said, my main interest in this thread was about the full templates, and I can't say more about the partial ones. Maybe exploring the partial templates can be useful to find new patterns in the multi-Fish family, but this is just a vague idea.

2) referring to my definitions of templates and associated concepts here, I now suspect that this approach is very unnatural:
- it is obviously not for a human solver.
- how can one write a resolution path with templates, i.e. what's the readability of such a solution? I think, not better than standard DFS.
- for a computer solver, template-DFS seems arbitrarily restrictive wrt to standard DFS; why should one want to restrict his possible tries to sequences of 9 candidates for the same digits (which is what a template for this digit amounts to)? What's the motivation wrt to the Sudoku problem? Worse, it seems that it leads to making unnecessary choices (still compared to standard DFS).
- template-DFS raises the same questions as DFS: do we accept a solution found by chance (this is the "guessing" part of template-DFS, as in standard DFS) or do we continue until we have proven that no other solution is possible ("template-T&E")? In the first case, the relevant questions would be about "template-backdoor size"; in the second case, about "template-T&E-depth". I wonder which version of the algorithm was used in the results reported above.

[ronk]

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.

I don't get this part. For the case 1 and case 2 chains, it appears you're assuming the the exclusions are already made. For example, for the first strong inference in case 1, r6c7 still contains candidate 1.

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

Interesting MUG deduction with a continuous loop and two (?) "self-loops."

____

[David P Bird]

I don't get this part. For the case 1 and case 2 chains, it appears you're assuming the exclusions are already made. For example, for the first strong inference in case 1, r6c7 still contains candidate 1.

Exactly – I am assuming that either one set of exclusions or the other must happen.
If you like there is the inference chain (1#1)ExclusionMap - (15=7)r56c6 - (7#1)ExclusionMap.
It's far from pretty but, if that premise is understood, it's the simplest way to notate the logic. There might be other ways involving split nodes all of which would include 'OR' relationships, but they would be horrendous to follow.

In tackling these monster's I have to relax my acceptability criteria, and I'm trying to find ways keep any relaxation to a minimum. Another objective is to employ methods where the discovery method can be explained. That's why I'm not a fan of complicated sets of truths and links as used in your diagram. For example I can't immediately see how (1)r1c7 can be eliminated.

The way I saw that Deadly Pattern threat was that in rows 5 & 6, digits (5) & (7) must occupy 4 of these 6 cells. They can't both be in c2 or c8 otherwise they'd form a UR, consequently to avoid forming a 6-cell DP (1)r56c28 can only hold 1 truth at most (a mini theorem). No truths or links for (5) or (7) outside the two rows are therefore needed. Could you express that in a truth and link sets diagram?

[Edit] Thanks for your PM telling me that your original list of fifteen (157)templates had been revised to twenty nine.
I've just run through these looking for DPs in r56c268. 12 of them have 4-cell DPs and 6 have 6-cell DPs, so only 11 of them would survive this check. However, you've already achieved many of the (7) eliminations that I'd expect would follow.[End edit]

I guess that building in uncovered DP checks would be complicated, but a subroutine to check just for URs between the latest digit added to the list against the previous ones might pay for its keep.

[Edit 1] Marked para edited after ronk kindly advised me that his previously posted list was incomplete
[Edit 2] Saving made by checking for DPs corrected after further PM from ronk (thanks)

[eleven]

Hi Denis,

the question i was interested in here is obviously one you have not asked for:

Suppose you have an algorithm, which in each step of solving a puzzle only considers maximum n (arbitrary/not fixed) digits (and the given/solved cells) to make some progress (eliminating a candidate or a possibility for a candidate's templates), something like meta-n-digit-multicoloring, what is the maximum n, it would need to solve all puzzles ?

My conjecture was 5, but it turned out to be 6, where those puzzles needing 6 are extremely rare (less than 2000 in the hardest list).
On the other hand one of the SER 11.9 puzzles can be solved with 4.

[denis_berthier]

Suppose you have an algorithm, which in each step of solving a puzzle only considers maximum n (arbitrary/not fixed) digits (and the given/solved cells) to make some progress (eliminating a candidate or a possibility for a candidate's templates), something like meta-n-digit-multicoloring, what is the maximum n, it would need to solve all puzzles ?
My conjecture was 5, but it turned out to be 6, where those puzzles needing 6 are extremely rare (less than 2000 in the hardest list).
On the other hand one of the SER 11.9 puzzles can be solved with 4.

Interesting.
But your notion of "making some progress" involves two very different things. Eliminating a candidate makes sense in all the usual solving paradigms. Using the elimination of a possibility for a candidate's templates supposes that, if A is the algorithm about which you are making this conjecture/assertion, then A deals with templates - which is very limitative.
Could you adapt your algorithm (the real one, that you use to analyse A) to limit "progress" in A to the first possibility?

Does anyone know how to disable automatic correction on this forum? This is a real nuisance.

[JasonLion]

Automatic spelling correction is not a feature of the forum. It is, however, a feature of several web browsers. Most of them allow you to disable it in their preference settings.

[denis_berthier]

Automatic spelling correction is not a feature of the forum. It is, however, a feature of several web browsers. Most of them allow you to disable it in their preference settings.

Jason, thanks. Actually, not in Safari; but it seems a system setting was automatically changed when I upgraded to OSX 10.7.3.

[eleven]

Could you adapt your algorithm (the real one, that you use to analyse A) to limit "progress" in A to the first possibility?

Hm, i guess this would lead to, what Danny has made (he finds almost all possible eliminations, see above).

btw different to Danny i did not make "outside" eliminations, i.e. when all n-templates need a cell, you can remove all templates of the other digits, which use this cell. I have tried this too now, but so far i cannot see a difference in the resulting grids, though its theoretically possible.
[Edit:] oops, yes, there are some more eliminations in Tungsten Rod. We have to be careful how we define "using 4 digits only".
This is my final grid then:

Hidden Text: Show

Code: Select all

  17 10 29 20 9 22 24 60 36
 *------------------------------------------------------------------*
 | 34589  4568   34689   | 1236  12569  1689  | 24     1389   7     |
 | 3589   2      3789    | 4     157    1789  | 1389   6      389   |
 | 1      4678   346789  | 2367  2679   6789  | 5      389    24    |
 |-----------------------+--------------------+---------------------|
 | 358    9      1378    | 167   1367   2     | 1378   4      358   |
 | 2345   1457   12347   | 8     1347   157   | 6      13579  2359  |
 | 6      14578  123478  | 9     1347   157   | 12378  13578  2358  |
 |-----------------------+--------------------+---------------------|
 | 2489   1468   5       | 1267  12679  3     | 4789   789    4689  |
 | 49     3      1469    | 1567  8      1679  | 479    2      4569  |
 | 7      68     2689    | 256   269    4     | 389    3589   1     |
 *------------------------------------------------------------------*

Also i have to mention, that my method does not see any uniqueness eliminations.

[daj95376]

GreenLantern posted this puzzle in the Eureka! forum. After examining the original grid, I thought that it might be appropriate for this thread as well.

Code: Select all

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

   c5b2  Locked Candidate 1              <> 4    r45c5

 +--------------------------------------------------------------------------------------------------+
 |  347       67        1         |  9         345       35        |  2         56        8         |
 |  2389      2689      368       |  1235      12358     7         |  59        4         169       |
 |  5         289       48        |  6         1248      28        |  3         19        7         |
 |--------------------------------+--------------------------------+--------------------------------|
 |  238       12568     9         |  12345     123568    23568     |  458       7         1234      |
 |  2378      125678    3568      |  123457    12356789  235689    |  4589      123589    12349     |
 |  2378      4         358       |  12357     1235789   23589     |  6         123589    1239      |
 |--------------------------------+--------------------------------+--------------------------------|
 |  489       89        2         |  37        3679      1         |  4789      3689      5         |
 |  1         3         45        |  8         25679     2569      |  479       269       2469      |
 |  6         589       7         |  235       2359      4         |  1         2389      239       |
 +--------------------------------------------------------------------------------------------------+
 # 164 eliminations remain


[SudoQ]

Code: Select all

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


I don't think it has any significance in this thread that this puzzle can be solved in one step: r3c2<>2.
/SudoQ

[pjb]

I was surprised that Ronk's post earlier in this thread regarding eliminations achieved by combining templates with the added constraint of ALSs above didn't attract more comment. In line with his result for 'tungsten rod', I found a nice haul of eliminations can be achieved with 'fata morgana' and quite a few others I have tested (but not all by any means). So, well done Ronk. I have incorporated this technique into my online solver. Thanks to all the discussion above, I was able to add a technique for template subsets (4, 5, or 6). As mentioned in this thread, I also found that with subsets of 6, every puzzle can be solved, but with 5, many but not all. I modified my solver to keep track of templates that are rejected as invalid by one technique, so when I try another it starts with the reduced number of possible templates.

Phil Beeby