Help A

Post the puzzle or solving technique that's causing you trouble and someone will help

Help A

Postby JPF » Wed Jun 21, 2006 7:04 pm

Just curious to know the best way to solve this one.

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


Thanks.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby daj95376 » Wed Jun 21, 2006 8:36 pm

It depends upon your definition of best and what you allow for a solution.

Code: Select all
r8c9    =  3     Naked  Single
r6c9    =  5     Naked  Single
r7c9    =  8     Naked  Single
r6c6    =  9     Naked  Single
r3c7    =  3     Hidden Single
r3c1    =  8     Hidden Single
r2c1    =  9     Hidden Single
r3c5    =  9     Hidden Single
r2c9    =  2     Hidden Single
r5      -  1268  Naked  Quad
    b4  -  2     Locked Candidate (1)

r1c9    =  1     [r1c9]<>4 (elimination-by-contradiction using naked/hidden singles)


                 Singles follow
Last edited by daj95376 on Wed Sep 13, 2006 5:42 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Wed Jun 21, 2006 9:59 pm

daj95376 wrote:r1c9 = 1 [r1c9]<>4 (elimination-by-contradiction using naked/hidden singles)

Is that a deduction that I, as a human solver, might have some chance of finding? Is that deduction even expressible with an error net of "reasonable" complexity?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Reasonable complexity?

Postby keith » Wed Jun 21, 2006 11:13 pm

ronk,

Here is what Sudoku Susser uses to solve the puzzle:

Heuristics used:

1 x Trebor's Tables
2 x Nishio
1 x Comprehensive Forcing Chains
1 x Comprehensive Naked Sets
1 x Intersection Removal
5 x Pinned Squares

The small number of (forced or) pinned squares is an indication that there are "backdoor" squares that easily solve the puzzle. How a human would find these, I have no idea.

This is kind of like the stock market. At the end of the day, any "expert" can explain why the market went up or down. Did you notice, they are far less precise about tomorrow? (Predict or postdict?)

What I mean is, given a computer program that identifies the backdoor squares, one can easily construct logic to solve the puzzle. But, where is the human logic to identify these squares in the first place?

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby daj95376 » Thu Jun 22, 2006 2:54 am

My solver flags backdoor singles as a FYI during processing, but does not use that information to influence/control/force a solution. However, it did discover [r1c9]<>4 and used it to perform an elimination.

I included the backdoor single information in my solution as a FYI, not as part of the solution.

As to whether or not a human solver could make the same discovery, that was not part of the original specifications. JPF was looking for best without specifying how he wanted it attained. He is perfectly free to ignore my results -- as some of you have done.

BTW, just how complicated of a chain should a typical human solver be able to handle? Mulit-Coloring is an accepted technique. Do many human solvers employ it?

As a final note, setting [r1c9]=4 and resolving 24 naked/hidden singles -- probably not all actually necessary -- results in an invalid puzzle. Whether or not this is better than another approach is up to the person trying to replay a solution.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Thu Jun 22, 2006 8:48 am

daj95376 wrote:However, it did discover [r1c9]<>4 and used it to perform an elimination.

Without making any reference to backdoors, it's that elimination I asked about. Based on your answer, it seems we are left to try the placement r1c9=4 ourselves ... to discover the contradicition and the complexity of the error net.

daj95376 wrote:BTW, just how complicated of a chain should a typical human solver be able to handle? Mulit-Coloring is an accepted technique. Do many human solvers employ it?

I think it's fair to say that on this forum ... more people present multi-coloring eliminations than brute-force eliminations. Turbot fish, "skyscraper", "two-stringed kite", and x-cycles are specific examples of multi-coloring (although some are just simple coloring).
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Carcul » Thu Jun 22, 2006 10:21 am

Here's what I have found:

Code: Select all
 *----------------------------------------------------------*
 | 2456   24567   2467  | 1457  1357   1345  | 8    9    14 |
 | 9      1       3     | 457   8      6     | 457  57   2  |
 | 8      457     47    | 2     9      145   | 3    157  6  |
 |----------------------+--------------------+--------------|
 | 246    24679   24679 | 3     1567   158   | 469  168  14 |
 | 34     349     5     | 168   126    128   | 49   168  7  |
 | 1      67      8     | 67    4      9     | 2    3    5  |
 |----------------------+--------------------+--------------|
 | 23456  234569  12469 | 1456  12356  12345 | 567  567  8  |
 | 256    8       126   | 9     1256   7     | 56   4    3  |
 | 7      3456    46    | 4568  356    3458  | 1    2    9  |
 *----------------------------------------------------------*

1. This first step is simply coloring:

[r4c6]-1-[r3c6]=1=[r3c8]-1-[r1c9]=1=[r4c9]-1-[r4c6], => r4c6<>1.

2. Now we have a discontinuous multiple implication nice loop:

[r6c4]=7=[r6c2]=6=[r4c123]-6-[r45c7]-4-[r2c7]=4=[r1c9](=1=[r3c8]-
-1-[r3c6])-4-[r1c123]=4=[r3c23]-4-[r3c6]-5-[r4c6]=5=[r4c5]=7=[r6c4],
=> r6c4=7.

3. In this step I have used the AUR in cells r27c78:

[r8c7]-6-[r45c7]-4-[r2c7]=4|6=[r7c78]-6-[r8c7], => r8c7<>6.

4. In this step let's start by noting that r8c5=2 or r3c6=5, because if r8c5 is not "2" and r3c6 is not "5", then:

{TILA: [r2c8]-7-[r7c8]-6-[r7c7]=6=[r4c7]=9=[r5c7]=4=[r5c12]-4-[r4c1]-
-2-[r8c1]-6-[r8c5]-1-[r7c4]=1=[r1c4]-1-[r1c9]-4-[r2c7]-7-[r2c8], =>
r2c8<>7; [r2c8]-5-[r2c4]-4-[r3c6]-1-[r3c8]-5-[r2c8], => r2c8<>5 =>
r2c8=7}.

Ok. So this means that we have here the link "[r8c5]=2|5=[r3c6]". We can now use it in the following discontinuous multiple implication loop:

[r8c5]=2|5=[r3c6](-5-[r79c6])-5-[r4c6](-8-[r9c6](-4-[r7c6])-4-[r9c3]-6-
-[r8c13]-1-[r8c5])(-8-[r5c456]-(UR:r57c56)-1,2-[r7c5])=5=[r4c5]-5-
-[r79c5]-6-[r8c5], => r8c5<>1,6 => r8c5=2.

5. To finnish the puzzle the following XY-Wing is enough:

[r2c8]-5-[r2c4]-4-[r3c6]-1-[r3c8]-5-[r2c8], => r2c8<>5

and the puzzle is solved.

Good job JPF, this is a very good puzzle.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby daj95376 » Thu Jun 22, 2006 8:13 pm

ronk wrote:Without making any reference to backdoors, it's that elimination I asked about. Based on your answer, it seems we are left to try the placement r1c9=4 ourselves ... to discover the contradicition and the complexity of the error net.

My solver dropped into elimination-by-contradiction (EBC) mode after exhausting the other techniques I've currently written. Below is the state of the grid when this occurred.

Code: Select all
*-----------------------------------------------------------------------------*
| 2456    24567   2467    | 1457    1357    1345    | 8       9       14      |
| 9       1       3       | 457     8       6       | 457     57      2       |
| 8       457     47      | 2       9       145     | 3       157     6       |
|-------------------------+-------------------------+-------------------------|
| 246     24679   24679   | 3       1567    158     | 469     168     14      |
| 34      349     5       | 168     126     128     | 49      168     7       |
| 1       67      8       | 67      4       9       | 2       3       5       |
|-------------------------+-------------------------+-------------------------|
| 23456   234569  12469   | 1456    12356   12345   | 567     567     8       |
| 256     8       126     | 9       1256    7       | 56      4       3       |
| 7       3456    46      | 4568    356     3458    | 1       2       9       |
*-----------------------------------------------------------------------------*

At this point, my EBC logic prioritizes unsolved cells based on the number of candidates they contain. This means that the first cell it examined was [r1c9]. While testing value <1>, my solver discovered that <1> was a backdoor single for this layout and noted it as a FYI only! Then my solver proceeded to test the value <4>.

Here's the full debug output for the 24 Naked/Hidden Singles that my solver resolved before encountering a contradiction. Only 18 moves, which I manually marked with asterisks, seem necessary.

Code: Select all
r1c9    =  4     (EBC testing depth 2)
r4c9  * =  1     Naked  Single
r2c4  * =  4     Hidden Single
r3c8  * =  1     Hidden Single
r3c6  * =  5     Naked  Single
r4c6  * =  8     Naked  Single
r4c8  * =  6     Naked  Single
r5c8    =  8     Naked  Single
r4c5  * =  5     Hidden Single
r9c4  * =  8     Hidden Single
r9c2  * =  5     Hidden Single
r1c1  * =  5     Hidden Single
r8c7  * =  5     Hidden Single
r2c7  * =  7     Naked  Single
r2c8    =  5     Naked  Single
r7c7  * =  6     Naked  Single
r7c8    =  7     Naked  Single
r7c4    =  5     Hidden Single
r8c1  * =  6     Hidden Single
r9c3  * =  4     Naked  Single
r3c3    =  7     Naked  Single
r3c2    =  4     Naked  Single
r9c6  * =  3     Naked  Single
r1c6  * =  1     Naked  Single
r1c4  * =  7     Naked  Single

r1c9    =  1     [r1c9]=4 => [b5]=INVALID    (hidden,naked) = ( 9,15)

I'm sorry that I don't know how to convert the above into proper chains, but I've found the threads on writing chains very confusing. It's hit-n-miss on reading the right threads in the right order to understand the terminology. Many very useful technical threads are full of banter that obfuscate the underlying information.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006


Return to Help with puzzles and solving techniques