The New Sudoku Players' Forum

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

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

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

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

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

by **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).

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

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

The New Sudoku Players' Forum

Help A

Help A

Reasonable complexity?