New Solving Technique (I think)

Everything about Sudoku that doesn't fit in one of the other sections

Re: Tungsten Rod

Postby daj95376 » Tue Feb 07, 2012 1:02 am

eleven wrote: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
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby daj95376 » Tue Feb 07, 2012 1:49 am

[Not relevant.]
Last edited by daj95376 on Tue Feb 07, 2012 5:53 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby denis_berthier » Tue Feb 07, 2012 6:57 am

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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby ronk » Tue Feb 07, 2012 12:40 pm

David P Bird wrote: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.

David P Bird wrote: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."

____ Image
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby David P Bird » Tue Feb 07, 2012 3:06 pm

ronk wrote: 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)
Last edited by David P Bird on Wed Feb 08, 2012 10:08 am, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: New Solving Technique (I think)

Postby eleven » Tue Feb 07, 2012 8:39 pm

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.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: New Solving Technique (I think)

Postby denis_berthier » Wed Feb 08, 2012 5:09 am

eleven wrote: 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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby JasonLion » Wed Feb 08, 2012 12:54 pm

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.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: New Solving Technique (I think)

Postby denis_berthier » Wed Feb 08, 2012 1:38 pm

JasonLion wrote: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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby eleven » Wed Feb 08, 2012 5:15 pm

denis_berthier wrote: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.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: New Solving Technique (I think)

Postby daj95376 » Thu Feb 16, 2012 5:46 pm

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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby SudoQ » Thu Feb 16, 2012 8:21 pm

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
SudoQ
 
Posts: 39
Joined: 09 September 2011

Re: New Solving Technique (I think)

Postby pjb » Thu Feb 23, 2012 9:12 am

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
pjb
2014 Supporter
 
Posts: 1671
Joined: 11 September 2011
Location: Sydney, Australia

Previous

Return to General