Just One Step

Advanced methods and approaches for solving Sudoku puzzles

Just One Step

Postby Carcul » Wed Mar 15, 2006 4:27 pm

Consider the following puzzle:

Code: Select all
 9 . . | . . . | . . 7
 . 6 7 | . 5 . | 9 4 .
 2 4 . | . . . | . 1 6   
-------+-------+-------
 . . . | 2 . 7 | . . .
 3 . . | . 6 . | . . 2
 . . . | 3 . 1 | . . .
-------+-------+-------
 7 3 . | . . . | . 5 1
 . 5 2 | . 3 . | 6 7 .
 6 . . | . . . | . . 4

(Henk Collection, Puzzle #212, rating 25714)

After the basic steps we arrive at the following grid:

Code: Select all
 9    18   35   | 468   148    3468 | 258  28   7     
 18   6    7    | 18    5      2    | 9    4    3     
 2    4    35   | 789   789    389  | 58   1    6     
----------------+-------------------+---------------
 458  189  6    | 2     489    7    | 14   3    589   
 3    7    1489 | 4589  6      4589 | 14   89   2     
 458  2    489  | 3     489    1    | 7    6    589   
----------------+-------------------+---------------
 7    3    489  | 4689  2489   4689 | 28   5    1     
 148  5    2    | 1489  3      489  | 6    7    89     
 6    189  189  | 5789  12789  589  | 3    289  4     

Now, I am interested to know how the various solvers (humans and computer programs) out there would solve this puzzle from here in a single step. For reference, here is my definition of "single step":

Single Step: a logical deduction with which the puzzle is solved, i. e., a logical deduction from which all other further logical deductions needed to complete the puzzle are the most basic ones: naked and hidden singles, locked candidates, pairs, triples and quads, and eventually X-Wings and type-1 URs, but nothing beyond that (Swordfish, XY-Wing, Colors, etc).

Every contribution is welcome.

Thanks in advance.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ravel » Wed Mar 15, 2006 5:57 pm

From all the cells, where my program can eliminate all but one candidates, only r5c3=1, r5c6=8, r7c5=8 and r8c1=8 can be solved with such basic methods (no warranty, it is not bug free). So it would need at least 2 chains (for the last). It just works until a contradiction arises, so it does not give a good way, how the elimination can be done.
PS: What i overlooked before: Also eliminating 4 from r8c14 (or 8 from r579c3) would do the job.
(I know, Carcul, this is not what you asked for, it was just the easy part to get a starting point for a good solution for an obviously hard puzzle)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby tarek » Wed Mar 15, 2006 7:55 pm

I couldn't find a single step......

The key to me is probably to try & crack either r4c9 or r6c1

there is this fantastic pattern, which I couldn't help but share...
Code: Select all
*-----------------------------------------------------------------*
| 9      18     35    | 468    148    3468  | 258    28     7     |
| 18     6      7     |^18     5      2     | 9      4      3     |
| 2      4      35    | 789    79     389   | 58     1      6     |
|---------------------+---------------------+---------------------|
| 458    189    6     | 2      489    7     | 14     3      58    |
| 3      7      148   | 4589   6      4589  | 14     89     2     |
| 458    2      489   | 3      489    1     | 7      6      589   |
|---------------------+---------------------+---------------------|
| 7      3      489   |*4689   2489  *4689  | 28     5      1     |
| 148    5      2     |*1489   3     *489   | 6      7      89    |
| 6      189    189   |-5789   12789  589   | 3      289    4     |
*-----------------------------------------------------------------*
Eliminating 8 from r9c4(ALS-XZ A=14689 in r8c6, r7c4, r7c6, r8c4 B=18 in r2c4  x=1 z=8, almost classic VWXYZ wing)

Tarek
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Postby Carcul » Wed Mar 15, 2006 8:44 pm

Ravel wrote:From all the cells, where my program can eliminate all but one candidates, only r5c3=1, r5c6=8, r7c5=8 and r8c1=8 can be solved with such basic methods


Thanks for your time Ravel. r5c3=1 does not solve the puzzle as I have defined, but the other cells do the job. A very important question: how did your program arrive to the conclusion that any of r5c6=8, r7c5=8, r8c1=8 solve the puzzle?

Ravel wrote:So it would need at least 2 chains (for the last).


What do you mean by that? For example, how do you prove that r8c1 must be "8"?

Ravel wrote:PS: What i overlooked before: Also eliminating 4 from r8c14 (or 8 from r579c3)


r8c6=4 also solve the puzzle, but r6c3=8 does not.

Tarek wrote:The key to me is probably to try & crack either r4c9 or r6c1


Thanks for your time Tarek. Both r4c9 and r6c1 don't solve the puzzle.

Tarek wrote:there is this fantastic pattern, which I couldn't help but share...


Very good catch indeed.:D

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby re'born » Wed Mar 15, 2006 9:26 pm

Carcul,

Great puzzle. I can't yet see the single step needed. However, along the same lines as tarek's post above there is a nice application of aeb's Extended Subset Principle.

Code: Select all
| 9      18     35    | 468    148    3468  |  258    28     7     |
| 18     6      7     | 18     5      2     |  9      4      3     |
| 2      4      35    | 789    79     389   |  58     1      6     |
|---------------------+---------------------+----------------------| 
| 458    189    6     | 2      489    7     |  14     3      58    |
| 3      7      148   | 4589   6      4589  |  14     89     2     |
| 458    2      489   | 3      489    1     |  7      6      589   |
|---------------------+---------------------+----------------------|
| 7      3     -489   | 4689   2489   4689  | #28     5      1     |
| 148    5      2     | 1489   3      489   |  6      7      89    |
| 6     #189   #189   | 5789   12789  589   |  3      289    4     |


which other than implying (7,3)!8, does not seem to advance the solution much (with Carcul's restrictions).

Edit : The conclusion is true, but until further notice, the reasoning is bunk.
Last edited by re'born on Wed Mar 22, 2006 6:55 am, edited 1 time in total.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ravel » Thu Mar 16, 2006 10:54 am

Hi Carcul,

when i add r5c3=1 or r6c3=8 to the puzzle, my solver only needs singles.

My program only has some basic techniques implemented. But i added a loop, where each candidate is dropped. If a contradiction is reached then without further guessing, i know, that it can be eliminated (the classical t&e method). But i do not know, which of (normally very much) steps are necessary or if another order of steps would provide a better solution. Also other techniques could give a more elegant solution or eliminate other candidates. It is similar to enter a wrong candidate in susser and look how far it gets with basic methods.

r8c1 has the candidates 148. Since i know that 1 and 4 can be eliminated this way, there must be 2 (probably very long) chains that can solve the puzzle. Same for showing that r8c6=4, because there must be chains, that eliminate 4 from r8c1 and r8c4.
When i understood you right, e.g. a chain that eliminates both, would be what you asked for.
ravel
 
Posts: 998
Joined: 21 February 2006

Logic

Postby Jumper » Wed Mar 22, 2006 2:36 am

It is arguable that the logical step to take is to eliminate 2 combinations from R1, C2 and C3:

8,5 shows contradiction so quickly I needed no pencil, and the combination 1,5 in the same cells likewise.

After that, it gets interesting.
Jumper
 
Posts: 8
Joined: 23 September 2005

Postby ravel » Wed Mar 22, 2006 9:29 am

The elimination 1,3 should be possible, but is the puzzle solved, when you have the 8,3 ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Neunmalneun » Wed Mar 22, 2006 9:47 am

Maybe it's too early but I don't see the contradiction caused by 15 in R1C23. (No problem with the 58-move which leads to a contradiction in R1/Box3.)

By the way: can anyone explain the Extended Subset Principle which allows the elimination of 8 in R7C3 due to the 28-pair in R7C7 (posted by rep'nA)?

Thanks in advance
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby re'born » Wed Mar 22, 2006 10:19 am

Neunmalneun,

For an explanation of the Subset Principle, check out

http://forum.enjoysudoku.com/viewtopic.php?t=3479

where aeb explains it in full.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Neunmalneun » Wed Mar 22, 2006 10:26 am

Thank you for your reply. To be honest: I knew this link but just did not understand it. I thought there could be an (easier) explanation why (and how) this principle works in this puzzle (elimination of 8 in R7C3).
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby ravel » Wed Mar 22, 2006 10:48 am

Hm, i cannot find anything with the cells marked above either. Rep'nA, can you give the cells, set and the multiplicities, please?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby re'born » Wed Mar 22, 2006 10:56 am

Neunmalneun,

I have a really easy explanation. I don't think that it works in this situation. At the time, I remember double checking, but now it doesn't make sense to me.

S={(7,7), (9,2), (9,3)}
Relevant Candidates: 1,2,8,9
maximal counts: 1,1,2,1.

This would imply that we would need to decrease the maximal count by 3 to get a contradiction. (7,3)8 only decreases the count by 2. Hence, no elimination can be made. Hmmph.
re'born
 
Posts: 551
Joined: 31 May 2007

One question

Postby Jumper » Wed Mar 22, 2006 10:48 pm

Is this a valid puzzle?
Jumper
 
Posts: 8
Joined: 23 September 2005

Postby tarek » Wed Mar 22, 2006 10:59 pm

It is valid Jumper, but it is a toughie...:D

tarek
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Next

Return to Advanced solving techniques