Posted: Sun Dec 31, 2006 11:49 pm Post subject: A new candidate for "toughest puzzle"?

This user submission to the "Scanraid Sudoku Solver" web site has a single unique solution, but other than a single hidden pair doesn't seem to have fall to any known solving techniques. It also gives SudoCue and my own slightly brain-damaged solver fits. Anyone else want to have a go at it?

* A set of 2 squares form a simple hidden pair. R2C3 and R3C1 all contain the 2 possibilities <17>. No other squares in block 1 have those possibilities. Since the 2 squares are the only possible locations for 2 possible values, any additional possibilities these squares have (if any) can be eliminated. These squares now become a simple naked pair.

R2C3 - removing <9> from <179> leaving <17>.
R3C1 - removing <59> from <1579> leaving <17>.

* Made progress using Trebor's Tables to find inferences about the puzzle. A total of 18475 implications about the puzzle were generated and examined in order to find these inferences - you'd run through several pencils working them out by hand!

The following verities were found (only first verity proving the assertion is shown):
R1C1<>9 (Implied by all valid values of R1C1)
R7C9<>3 (Implied by all valid values of R1C1)
R2C7<>5 (Implied by all valid values of R1C1)
R8C8<>4 (Implied by all valid values of R1C1)
R1C7<>4 (Implied by all valid values of R1C1)
R7C8<>4 (Implied by all valid values of R1C1)
R3C8=4 (Implied by all valid values of R1C1)
R3C8<>1 (Implied by all valid values of R1C1)
R3C8<>3 (Implied by all valid values of R1C1)
R3C8<>9 (Implied by all valid values of R1C1)
R3C4<>4 (Implied by all valid values of R1C1)
R3C5<>4 (Implied by all valid values of R1C1)
R3C6<>4 (Implied by all valid values of R1C1)
R5C7<>7 (Implied by all valid values of R1C1)
R2C9<>8 (Implied by all valid values of R2C4)
R7C9<>7 (Implied by all valid values of R2C8)
R3C9<>5 (Implied by all valid values of R2C9)
R7C1<>7 (Implied by all valid values of R3C2)
R7C1<>9 (Implied by all valid values of R3C2)
R4C1<>2 (Implied by all valid values of R3C2)
R4C4<>4 (Implied by all valid values of R4C4)
R1C6<>5 (Implied by all valid values of R6C9)
R5C3<>9 (Implied by all valid values of R7C1)
R5C8<>2 (Implied by all valid values of R7C9)
R6C9<>3 (Implied by all valid values of R8C5)
R1C7<>3 (Implied by all valid values of R8C5)
R6C1<>2 (Implied by all valid values of R8C5)
R7C1<>8 (Implied by all valid values of R8C5)
R7C9=8 (Implied by all valid values of R8C5)
R7C9<>1 (Implied by all valid values of R8C5)
R3C9<>8 (Implied by all valid values of R8C5)
R8C7<>8 (Implied by all valid values of R8C5)
R2C7=8 (Implied by all valid values of R8C5)
R2C7<>9 (Implied by all valid values of R8C5)
R2C4<>8 (Implied by all valid values of R8C5)
R7C2<>5 (Implied by all valid values of R8C5)
R1C1<>5 (Implied by all valid values of R8C5)
R1C4<>2 (Implied by all valid values of R8C5)
R1C6<>2 (Implied by all valid values of R8C5)
R2C2<>2 (Implied by all valid values of R8C5)
R1C1=2 (Implied by all valid values of R8C5)
R7C1=5 (Implied by all valid values of R8C5)
R8C6<>4 (Implied by all valid values of R8C6)
R8C6<>6 (Implied by all valid values of R8C6)
R2C8<>1 (Implied by all valid values of R9C1)
R8C3<>3 (Implied by all valid values of R9C6)
R9C9<>3 (Implied by all valid values of R9C7)

The following veracities were found (may duplicate verities, above):
R1C1=2 (Implied by at least 2 R8<>1 squares)
R1C1<>5 (Implied by at least 2 R8<>1 squares)
R1C1<>9 (Implied by all R1=2 squares)
R1C4<>2 (Implied by at least 2 R8<>1 squares)
R1C6<>2 (Implied by at least 2 R8<>1 squares)
R1C6<>5 (Implied by all R7=1 squares)
R1C7<>3 (Implied by at least 2 R8<>1 squares)
R1C7<>4 (Implied by all R1=2 squares)
R2C2<>2 (Implied by at least 2 R8<>1 squares)
R2C4<>8 (Implied by at least 2 R8<>1 squares)
R2C7=8 (Implied by at least 2 R8<>1 squares)
R2C7<>5 (Implied by all R1=2 squares)
R2C7<>9 (Implied by at least 2 R8<>1 squares)
R2C8<>1 (Implied by all R9=6 squares)
R2C9<>8 (Implied by all R2=1 squares)
R3C4<>4 (Implied by all R1=2 squares)
R3C5<>4 (Implied by all R1=2 squares)
R3C6<>4 (Implied by all R1=2 squares)
R3C8=4 (Implied by all R1=2 squares)
R3C8<>1 (Implied by all R1=2 squares)
R3C8<>3 (Implied by all R1=2 squares)
R3C8<>9 (Implied by all R1=2 squares)
R3C9<>5 (Implied by all R2=5 squares)
R3C9<>8 (Implied by at least 2 R8<>1 squares)
R4C1<>2 (Implied by at least 2 R3<>1 squares)
R4C4<>4 (Implied by at least 2 R4<>1 squares)
R4C4<>7 (Implied by all R5=7 squares)
R4C5<>7 (Implied by all R5=7 squares)
R5C2<>9 (Implied by all C1=9 squares)
R5C3<>9 (Implied by all R7=1 squares)
R5C7<>7 (Implied by all R1=2 squares)
R5C8<>2 (Implied by all R7=1 squares)
R6C1<>2 (Implied by at least 2 R8<>1 squares)
R6C8<>9 (Implied by all C1=9 squares)
R6C9<>3 (Implied by at least 2 R8<>1 squares)
R7C1=5 (Implied by at least 2 R8<>1 squares)
R7C1<>7 (Implied by at least 2 R3<>1 squares)
R7C1<>8 (Implied by at least 2 R8<>1 squares)
R7C1<>9 (Implied by at least 2 R3<>1 squares)
R7C2<>5 (Implied by at least 2 R8<>1 squares)
R7C8<>4 (Implied by all R1=2 squares)
R7C9=8 (Implied by at least 2 R8<>1 squares)
R7C9<>1 (Implied by at least 2 R8<>1 squares)
R7C9<>3 (Implied by all R1=2 squares)
R7C9<>7 (Implied by all R2=1 squares)
R8C3<>3 (Implied by all R9=2 squares)
R8C5<>7 (Implied by all R7=7 squares)
R8C6<>4 (Implied by all R8=1 squares)
R8C6<>6 (Implied by all R8=1 squares)
R8C6<>7 (Implied by all R7=7 squares)
R8C7<>8 (Implied by at least 2 R8<>1 squares)
R8C8<>4 (Implied by all R1=2 squares)
R9C4<>7 (Implied by all R7=7 squares)
R9C6<>7 (Implied by all R7=7 squares)
R9C9<>3 (Implied by all R9=3 squares)

The following squares can have possibilities eliminated:
R1C4: remove <2> from <249> leaving <49>.
R1C6: remove <25> from <2456> leaving <46>.
R1C7: remove <34> from <3459> leaving <59>.
R2C2: remove <2> from <259> leaving <59>.
R2C4: remove <8> from <2789> leaving <279>.
R2C8: remove <1> from <169> leaving <69>.
R2C9: remove <8> from <1568> leaving <156>.
R3C4: remove <4> from <4789> leaving <789>.
R3C5: remove <4> from <4579> leaving <579>.
R3C6: remove <4> from <4578> leaving <578>.
R3C9: remove <58> from <1358> leaving <13>.
R4C1: remove <2> from <126> leaving <16>.
R4C4: remove <47> from <12347> leaving <123>.
R4C5: remove <7> from <2347> leaving <234>.
R5C2: remove <9> from <269> leaving <26>.
R5C3: remove <9> from <189> leaving <18>.
R5C7: remove <7> from <579> leaving <59>.
R5C8: remove <2> from <269> leaving <69>.
R6C1: remove <2> from <289> leaving <89>.
R6C8: remove <9> from <239> leaving <23>.
R6C9: remove <3> from <235> leaving <25>.
R7C2: remove <5> from <3459> leaving <349>.
R7C8: remove <4> from <134> leaving <13>.
R8C3: remove <3> from <3478> leaving <478>.
R8C5: remove <7> from <23467> leaving <2346>.
R8C6: remove <467> from <12467> leaving <12>.
R8C7: remove <8> from <3478> leaving <347>.
R8C8: remove <4> from <1234> leaving <123>.
R9C4: remove <7> from <23479> leaving <2349>.
R9C6: remove <7> from <2467> leaving <246>.
R9C9: remove <3> from <237> leaving <27>.

The following squares can be solved:
R1C1 = 2
R2C7 = 8
R3C8 = 4
R7C1 = 5
R7C9 = 8

Tabling was terminated after 5 reductions or solves were found...

* Intersection of row 1 with block 3. The value <5> only appears in one or more of squares R1C7, R1C8 and R1C9 of row 1. These squares are the ones that intersect with block 3. Thus, the other (non-intersecting) squares of block 3 cannot contain this value.

* Intersection of block 3 with column 9. The values <13> only appears in one or more of squares R1C9, R2C9 and R3C9 of block 3. These squares are the ones that intersect with column 9. Thus, the other (non-intersecting) squares of column 9 cannot contain these values.

* Found a 5-link Simple Forcing Chain. If we assume that square R4C9 is <6> then we can make the following chain of conclusions:

R4C1 must be <1>, which means that
R3C1 must be <7>, which means that
R2C3 must be <1>, which means that
R2C9 must be <6>, which means that
R4C9 can't be <6>.

Since this is logically inconsistent, R4C9 cannot be <6>.

(5 links were considered before finding this chain)

* Squares R3C2 and R7C2 in column 2 and R3C5 and R7C5 in column 5 form a Simple X-Wing pattern on possibility <9>. All other instances of this possibility in rows 3 and 7 can be removed.

R3C4 - removing <9> from <789> leaving <78>.
R7C4 - removing <9> from <13479> leaving <1347>.

* Found a 4-link Comprehensive Chain. If we assume that square R8C1 is <6> then we can make the following chain of conclusions:

R8C3 must be <8> (R8 pin), which means that
R5C3 must be <1> (force), which means that
R4C1 must be <6> (force), which means that
R8C1 can't be <6> (buddy contradiction).

Since this is logically inconsistent, R8C1 cannot be <6>.

(8 links were considered before finding this chain)

* Found a 5-link Comprehensive Chain. If we assume that square R9C3 is <7> then we can make the following chain of conclusions:

R1C3 must be <3> (C3 pin), which means that
R1C9 must be <6> (force), which means that
R2C9 must be <1> (force), which means that
R2C3 must be <7> (force), which means that
R9C3 can't be <7> (buddy contradiction).

Since this is logically inconsistent, R9C3 cannot be <7>.

(15 links were considered before finding this chain)

* Found a 5-link Comprehensive Chain. If we assume that square R9C4 is <2> then we can make the following chain of conclusions:

R1C4 must be <9> (C4 pin), which means that
R1C6 must be <4> (R1 pin), which means that
R2C5 must be <6> (B2 pin), which means that
R2C4 must be <2> (R2 pin), which means that
R9C4 can't be <2> (buddy contradiction).

Since this is logically inconsistent, R9C4 cannot be <2>.

(15 links were considered before finding this chain)

* Found a 5-link Comprehensive Chain. If we assume that square R6C6 is <2> then we can make the following chain of conclusions:

R6C8 must be <3> (force), which means that
R8C8 must be <2> (C8 pin), which means that
R9C9 must be <7> (force), which means that
R9C6 must be <2> (R9 pin), which means that
R6C6 can't be <2> (buddy contradiction).

Since this is logically inconsistent, R6C6 cannot be <2>.

(24 links were considered before finding this chain)

* A set of 2 squares form a simple hidden pair. R6C5 and R6C8 all contain the 2 possibilities <23>. No other squares in row 6 have those possibilities. Since the 2 squares are the only possible locations for 2 possible values, any additional possibilities these squares have (if any) can be eliminated. These squares now become a simple naked pair.

* Intersection of column 6 with block 8. The value <2> only appears in one or more of squares R7C6, R8C6 and R9C6 of column 6. These squares are the ones that intersect with block 8. Thus, the other (non-intersecting) squares of block 8 cannot contain this value.

* A set of 2 squares form a simple hidden pair. R8C6 and R8C8 all contain the 2 possibilities <12>. No other squares in row 8 have those possibilities. Since the 2 squares are the only possible locations for 2 possible values, any additional possibilities these squares have (if any) can be eliminated. These squares now become a simple naked pair.

* Found a 6-link Simple Forcing Chain. If we assume that square R6C3 is <9> then we can make the following chain of conclusions:

R6C1 must be <8>, which means that
R6C6 must be <4>, which means that
R1C6 must be <6>, which means that
R1C9 must be <3>, which means that
R1C3 must be <9>, which means that
R6C3 can't be <9>.

Since this is logically inconsistent, R6C3 cannot be <9>.

(7 links were considered before finding this chain)

* A set of 2 squares form a simple hidden pair. R1C3 and R9C3 all contain the 2 possibilities <39>. No other squares in column 3 have those possibilities. Since the 2 squares are the only possible locations for 2 possible values, any additional possibilities these squares have (if any) can be eliminated. These squares now become a simple naked pair.

* Found a 6-link Simple Forcing Chain. If we assume that square R9C6 is <6> then we can make the following chain of conclusions:

R9C1 must be <7>, which means that
R8C3 must be <4>, which means that
R6C3 must be <8>, which means that
R6C6 must be <4>, which means that
R1C6 must be <6>, which means that
R9C6 can't be <6>.

Since this is logically inconsistent, R9C6 cannot be <6>.

(14 links were considered before finding this chain)

* R9C1 is the only square in row 9 that can be <6>. It is thus pinned to that value.

From this deduction, the following moves are immediately forced:

R4C1 must be <1>.
R3C1 must be <7>.
R5C3 must be <8>.
R6C3 must be <4>.
R6C6 must be <8>.
R8C3 must be <7>.
R4C2 must be <6>.
R2C3 must be <1>.
R2C9 must be <6>.
R1C9 must be <3>.
R3C4 must be <8>.
R3C6 must be <5>.
R3C5 must be <9>.
R1C3 must be <9>.
R3C9 must be <1>.
R3C2 must be <3>.
R1C4 must be <4>.
R9C3 must be <3>.
R1C6 must be <6>.
R8C2 must be <4>.
R8C7 must be <3>.
R7C2 must be <9>.
R8C5 must be <6>.
R4C7 must be <7>.
R7C8 must be <1>.
R9C4 must be <9>.
R4C9 must be <2>.
R9C7 must be <4>.
R4C4 must be <3>.
R9C9 must be <7>.
R6C8 must be <3>.
R6C5 must be <2>.
R8C8 must be <2>.
R8C6 must be <1>.
R9C6 must be <2>.
R4C5 must be <4>.
R7C4 must be <7>.
R2C5 must be <7>.
R7C5 must be <3>.
R7C6 must be <4>.
R2C4 must be <2>.
R5C4 must be <1>.
R5C6 must be <7>.
R5C5 must be <5>.

1 x Trebor's Tables
4 x Comprehensive Forcing Chains
3 x Simple Forcing Chains
1 x Simple X-Wing
3 x Intersection Removal
4 x Simple Hidden Sets
5 x Pinned Squares

* Found a Nishio contradiction. After 4 cycles, it became clear that R7C6 could not be a <9>.

R7C6 - removing <9> from <25689> leaving <2568>.

Here is a trace of the Nishio matrix as it was simplified.

# = Squares that must be <9>.
O = squares that can be <9>.
X = the current square (also an "O").
. = squares that cannot be <9>.
- = squares that were invalidated in the previous cycle.
P = the square that invalidated them (also a "#").
@ = the invalid group that cannot contain a <9>.

Nishio cycle 1 on <9> at R7C6

. . . . . . . # .
. . . O . O . . .
. . # . . . . . .
. . . . . . # . .
O . . O . O . . .
. O . O O . . . .
. O . O O X . . O
O . . O O O . . .
O O . O O O . . O

Nishio cycle 2 on <9> at R9C9

. . . . . - . # .
. . . O . - . . .
. . # . . - . . .
. . . . . - # . .
O . . O . - . . .
. O . O O - . . .
- - - - - P - - -
O . . - - - . . .
O O . - - - . . X

* Found a Nishio contradiction. After 4 cycles, it became clear that R7C4 could not be a <9>.

R7C4 - removing <9> from <245789> leaving <24578>.

Here is a trace of the Nishio matrix as it was simplified.

# = Squares that must be <9>.
O = squares that can be <9>.
X = the current square (also an "O").
. = squares that cannot be <9>.
- = squares that were invalidated in the previous cycle.
P = the square that invalidated them (also a "#").
@ = the invalid group that cannot contain a <9>.

Nishio cycle 1 on <9> at R7C4

. . . . . . . # .
. . . O . O . . .
. . # . . . . . .
. . . . . . # . .
O . . O . O . . .
. O . O O . . . .
. O . X O . . . O
O . . O O O . . .
O O . O O O . . O

Nishio cycle 2 on <9> at R9C9

. . . - . . . # .
. . . - . O . . .
. . # - . . . . .
. . . - . . # . .
O . . - . O . . .
. O . - O . . . .
- - - P - - - - -
O . . - - - . . .
O O . - - - . . X

* Found a Nishio contradiction. After 4 cycles, it became clear that R9C4 could not be a <9>.

R9C4 - removing <9> from <124589> leaving <12458>.

Here is a trace of the Nishio matrix as it was simplified.

# = Squares that must be <9>.
O = squares that can be <9>.
X = the current square (also an "O").
. = squares that cannot be <9>.
- = squares that were invalidated in the previous cycle.
P = the square that invalidated them (also a "#").
@ = the invalid group that cannot contain a <9>.

Nishio cycle 1 on <9> at R9C4

. . . . . . . # .
. . . O . O . . .
. . # . . . . . .
. . . . . . # . .
O . . O . O . . .
. O . O O . . . .
. O . . O . . . O
O . . O O O . . .
O O . X O O . . O

Nishio cycle 2 on <9> at R7C9

. . . - . . . # .
. . . - . O . . .
. . # - . . . . .
. . . - . . # . .
O . . - . O . . .
. O . - O . . . .
. O . - - - . . X
O . . - - - . . .
- - - P - - - - -

* Found a Nishio contradiction. After 4 cycles, it became clear that R9C6 could not be a <9>.

R9C6 - removing <9> from <125689> leaving <12568>.

Here is a trace of the Nishio matrix as it was simplified.

# = Squares that must be <9>.
O = squares that can be <9>.
X = the current square (also an "O").
. = squares that cannot be <9>.
- = squares that were invalidated in the previous cycle.
P = the square that invalidated them (also a "#").
@ = the invalid group that cannot contain a <9>.

Nishio cycle 1 on <9> at R9C6

. . . . . . . # .
. . . O . O . . .
. . # . . . . . .
. . . . . . # . .
O . . O . O . . .
. O . O O . . . .
. O . . O . . . O
O . . O O O . . .
O O . . O X . . O

Nishio cycle 2 on <9> at R7C9

. . . . . - . # .
. . . O . - . . .
. . # . . - . . .
. . . . . - # . .
O . . O . - . . .
. O . O O - . . .
. O . - - - . . X
O . . - - - . . .
- - - - - P - - -

57 x Hidden Single
2 x Naked Single
5 x Pointing
2 x Claiming
2 x Naked Pair
4 x Hidden Pair
1 x Turbot Fish
2 x Bidirectional Cycle
8 x Forcing Chain
1 x Nishio Forcing Chains
13 x Region Forcing Chains
5 x Cell Forcing Chains
3 x Dynamic Cell Forcing Chains
6 x Dynamic Contradiction Forcing Chains
4 x Dynamic Region Forcing Chains

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum