## Just One Step

Advanced methods and approaches for solving Sudoku puzzles

### Just One Step

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.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

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

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

tarek

Posts: 2687
Joined: 05 January 2006

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.

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

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

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

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

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

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)?

Neunmalneun

Posts: 52
Joined: 22 December 2005

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

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

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

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

Is this a valid puzzle?
Jumper

Posts: 8
Joined: 23 September 2005

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

tarek

tarek

Posts: 2687
Joined: 05 January 2006

Next