The New Sudoku Players' Forum

[gurth]

Solution to Ocean's #4/gold, using the Simple Sudoku program.

Code: Select all

 *-----------*
 |..1|..2|...|
 |.3.|.4.|.5.|
 |6..|7..|8..|
 |---+---+---|
 |..6|...|..7|
 |.1.|...|.2.|
 |9..|...|5..|
 |---+---+---|
 |..3|..1|..6|
 |.4.|.5.|.3.|
 |...|8..|9..|
 *-----------*    gsfr=99920, ER=N/A


Note: This solution is designed to be followed using the Simple Sudoku program.
"..." means proceed as far as SS allows, following the hints given by SS in the order given.
This will facilitate rapid checking of this solution.

"?" introduces a move that will be disproved by contradiction. (These moves are only introduced when SS grinds to a halt, saying "no hint available".) In order to "play" this move, you will have to turn off the "block invalid moves" feature of the program. Then insert the move and follow all hints given until you see a contradiction. Once you find the contradiction, you must retrace (withdraw in reverse order) all moves made since the disproved move, by clicking the "undo" arrow repeatedly. Then "correct" the disproved move. EG if this move was "?3f6", then REMOVE the 3 at f6, because you have proved the 3 at f6 false.

Solution:

(1) 6k2, 5k9, -5e4(MC).

(2) ?-3def46...?? -3def5. (A disproved multiple elimination of 6 candidates, giving elimination of 3).

(3) ?-3def4... (?7k8...??)-7k8, (?7k6...??)-7k6...?? -3def6...

(4) ?-3f4... (?1k8...??)-1k8... (?1c9...??)-1c9... (?1h7...??)-1h7... (?9c9...??)-9c9... (?4c9...??)-4c9...?? 3f4.

(5) ?-3k5... (?1d8...??)-1d8, (?1b9...??)-1b9... (?1c9...??)-1c9... (?1b7...??)-1b7... (?6e6...??)-6e6... (?6f5...??)-6f5... (?6h4...??)-6h4... (7g8...??)-7g8... (?9c6...??)-9c6...?? 3k5...

(6) Create Swordfish: ?-1d47...?? (1d4 OR 1d7), -1d58...

(7) ?-4k6... (?8h9...??)-8h9...?? 4k6.

(8) ?1c8...?? -1c8...

(9) ?1c9...?? -1c9...

(10) ?1h7...?? -1h7... End.

Note: In order to avoid sub-sub-nets, I scrapped 5 sub-nets along the way and chose others in their place. All of these were in step (5).

[leon1789]

Other solution :
C#z means "zC leads to contradiction using singles".

Code: Select all

   abc def ghi
  *-----------*
1 |..1|..2|...|
2 |.3.|.4.|.5.|
3 |6..|7..|8..|
  |---+---+---|
4 |..6|...|..7|
5 |.1.|...|.2.|
6 |9..|...|5..|
  |---+---+---|
7 |..3|..1|..6|
8 |.4.|.5.|.3.|
9 |...|8..|9..|
  *-----------*


1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

2) after that, if 2c9 then i3#2, b1#9, h9#1, b1#7, c2#9, i6#8, and contradiction using singles,
so -2c9.

3) after that, b1#7, g5#6, e5#7, b1#8, g2#2, a9#1 and finish with singles.

[gsf]

Other solution :
C#z means "zC leads to contradiction using singles".

Code: Select all

   abc def ghi
  *-----------*
1 |..1|..2|...|
2 |.3.|.4.|.5.|
3 |6..|7..|8..|
  |---+---+---|
4 |..6|...|..7|
5 |.1.|...|.2.|
6 |9..|...|5..|
  |---+---+---|
7 |..3|..1|..6|
8 |.4.|.5.|.3.|
9 |...|8..|9..|
  *-----------*


1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

if I read this correctly step 1 claims that the placement r3c3=4 leads to a contradiction using singles only
but pasting

Code: Select all

..1..2....3..4..5.6..7..8....6.....7.1.....2.9.....5....3..1..6.4..5..3....8..9..

into ss or other solvers restricted to singles leads to a position where
the next move is inconclusive (ss No hint available)

[RW]

1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

if I read this correctly step 1 claims that the placement r3c3=4 leads to a contradiction using singles only

I think it should be read: If r3c3=4 then r3c2=2, r2c9=1, r6c9=1 and r4c2=8 all lead to contradictions using singles, make these subnet eliminations, then the original proposition r3c3=4 also leads to a contradiction using singles.

RW

[gsf]

1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

if I read this correctly step 1 claims that the placement r3c3=4 leads to a contradiction using singles only

I think it should be read: If r3c3=4 then r3c2=2, r2c9=1, r6c9=1 and r4c2=8 all lead to contradictions using singles, make these subnet eliminations, then the original proposition r3c3=4 also leads to a contradiction using singles.

thanks
I get the if part: r3c3=4
its the then part
what is r3c2=2 a consequence of?
setting r3c3=4 and limiting to singles leaves the r3c2 pencilmarks untouched

[leon1789]

C#z means "zC leads to a contradiction using singles".

1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

I mean :
suppose c3=4

then b3#2 (because c3=4 with b3=2 leads to a contradiction using singles)
and now i2#1 (because c3=4 and b3#2 with i2=1 leads to a contradiction using singles)
and now i6#1 (because c3=4 and b3#2 and i2#1 with i6=1 leads to a contradiction using singles)
and now b4#8 (because ... ... to a contradiction using singles)
and now ( c3=4,b3#2,i2#1, i6#1,b4#8 ) there is a contradiction using singles,

so c3#4.

[gsf]

C#z means "zC leads to a contradiction using singles".

1) if 4c3 then b3#2, i2#1, i6#1, b4#8, and contradiction using singles,
so -4c3.

I mean :
suppose c3=4

then b3#2 (because c3=4 with b3=2 leads to a contradiction using singles)
and now i2#1 (because c3=4 and b3#2 with i2=1 leads to a contradiction using singles)
and now i6#1 (because c3=4 and b3#2 and i2#1 with i6=1 leads to a contradiction using singles)
and now b4#8 (because ... ... to a contradiction using singles)
and now ( c3=4,b3#2,i2#1, i6#1,b4#8 ) there is a contradiction using singles,

so c3#4.

aha, your notation overloads ","

Code: Select all

if c3==4
then
  if b3==2
  then contradiction
  therefore b3!=2
  if i2==1
  then contradiction
  therefore i2!=1
  if i6==1
  then contradiction
  therefore i6!=1
  if b4==8
  then contradiction
  therefore b4!=8
  finally a singles application leads to a contradiction
therefore c3!=4


in other words, a 2 ply constraint propagation backtrack tree search using singles as the constraint

this is related to the 9x9 sudoku backdoor conjecture:
all 9x9 sudoku are (singles)-n-constrained, 0 <= n <= 2,
for n==2 there exists at least two cells (a backdoor),
that when solved, produces a puzzle that solves with singles

all of ocean's golds are (singles)-2-constrained
so all can be solved by a 2 ply constraint propagation backtrack tree search
using singles as the constraint

[leon1789]

aha, your notation overloads ","

that's right...

in other words, a 2 ply constraint propagation backtrack tree search using singles as the constraint

this is related to the 9x9 sudoku backdoor conjecture:
all 9x9 sudoku are (singles)-n-constrained, 0 <= n <= 2,
for n==2 there exists at least two cells (a backdoor),
that when solved, produces a puzzle that solves with singles

all of ocean's golds are (singles)-2-constrained
so all can be solved by a 2 ply constraint propagation backtrack tree search using singles as the constraint

aha, the "backdoor conjecture" !

I don't know if I understand well, but I think this puzzle Ocean #14/vert. symm.: suexrat 1630 (RMS < 8)

Code: Select all

001000200030000040400050006000107000080030060000209000600000004050040080007000900

can't "be solved by a 2 ply constraint propagation backtrack tree search using singles as the constraint". But it can be with singles and locked set.

[RW]

aha, the "backdoor conjecture" !

I don't know if I understand well, but I think this puzzle Ocean #14/vert. symm.: suexrat 1630 (RMS < 8)

...

can't "be solved by a 2 ply constraint propagation backtrack tree search using singles as the constraint". But it can be with singles and locked set.

The backdoor conjecture says that for all 9x9 puzzles there exists two cells, such that if they both are solved, then the remaining puzzle solves with singles. For this puzzle, two such cells could be r9c4=3 and r8c9=1. Enter those values and only singles remain.

RW

[gsf]

The backdoor conjecture says that for all 9x9 puzzles there exists two cells, such that if they both are solved, then the remaining puzzle solves with singles. For this puzzle, two such cells could be r9c4=3 and r8c9=1. Enter those values and only singles remain.

here's one of the things that keeps me interested in sudoku
(and then extrapolating to general constraint satisfaction problems which also
have relatively small backdoors)

there are many 9x9 sudoku variants that provide extra information
that can be used to form new solution techniques
one solution => uniqueness constraints is one example

suppose the singles backdoor conjecture were true?
would this provide enough info for new techniques in solving the hardest sudoku?

if it were known that a given puzzle were singles-1-constrained then any
proposition that is inconclusive w.r.t. singles could be abandoned

what does that say about propositions/chains in singles-2-constrained puzzles?

[leon1789]

The backdoor conjecture says that for all 9x9 puzzles there exists two cells, such that if they both are solved, then the remaining puzzle solves with singles. For this puzzle, two such cells could be r9c4=3 and r8c9=1. Enter those values and only singles remain.

ok, I understand
(Now, the problem is to prove "easily" r9c4=3 and r8c9=1)

[ravel]

Now, the problem is to prove "easily" r9c4=3 and r8c9=1

If you want, it is proved by the fact, that the puzzle has a unique solution and the singles solution given, when you fix the 2 cells.
But for most of us this prove (or "solution") is not satisfying.

[gurth]

The backdoor conjecture says that for all 9x9 puzzles there exists two cells, such that if they both are solved, then the remaining puzzle solves with singles. For this puzzle, two such cells could be r9c4=3 and r8c9=1. Enter those values and only singles remain.

here's one of the things that keeps me interested in sudoku
(and then extrapolating to general constraint satisfaction problems which also
have relatively small backdoors)

there are many 9x9 sudoku variants that provide extra information
that can be used to form new solution techniques
one solution => uniqueness constraints is one example

suppose the singles backdoor conjecture were true?
would this provide enough info for new techniques in solving the hardest sudoku?

if it were known that a given puzzle were singles-1-constrained then any
proposition that is inconclusive w.r.t. singles could be abandoned

what does that say about propositions/chains in singles-2-constrained puzzles?

- This is one of the things that is keeping me interested in sudoku too.
The reference is to TWO cells : i.e. a pair of cells.
I am particularly interested in the Number of such Pairs: I propose to use it as a measure of the difficulty of the puzzle.

Very difficult puzzles are all what udosuk defined as diamonds (not to be confused with the Diamond Ratings used in the Pattern Game). They are diamonds if and because they do not have any single backdoor cell which will solve the puzzle with singles.

I define a Diamond Class 1 (DC1) as a diamond having only ONE possible Pair of backdoor cells.
Most sudokus up to SE 9.5 will almost certainly have MORE than one possible Pair, and will be of lower class, e.g. a sudoku with 7 possible Pairs would be labelled DC7.

I have rated dozens of the hardest sudokus of the last 5 years in terms of diamond CLASS, and the way in which the CLASS improved over time is quite fascinating. The CONJECTURE referred to in the above quote started to look like less of a certainty, and was finally demolished by the first sudoku which had CLASS ZERO - there simply was NO Pair that could solve it with singles.

Does any reader know which sudoku that was? The first one, and which ones since?

[JPF]

Hi gurth,
Welcome back!

The backdoor conjecture says that for all 9x9 puzzles there exists two cells, such that if they both are solved, then the remaining puzzle solves with singles. For this puzzle, two such cells could be r9c4=3 and r8c9=1. Enter those values and only singles remain.

....
The CONJECTURE referred to in the above quote started to look like less of a certainty, and was finally demolished by the first sudoku which had CLASS ZERO - there simply was NO Pair that could solve it with singles.
Does any reader know which sudoku that was? The first one, and which ones since?

Yes, here is Easter Monster

JPF

[gurth]

Thanks, JPF, and thanks for the link. Very interesting and surprising denouement to the M2 Conjecture!
It gives me food for thought, but I still think the M3 criterion is valid for the hardest puzzles.
Nearly all the very hardest puzzles are M3, so a puzzle of M2 is extremely unlikely to be a world-beater in terms of hardness.

The fact that very easy puzzles can also be M3, does nothing to alter that perception.