Solution to Ocean's #4/gold

Advanced methods and approaches for solving Sudoku puzzles

Solution to Ocean's #4/gold

Postby gurth » Fri Nov 17, 2006 9:13 am

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).
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby leon1789 » Mon Nov 20, 2006 10:12 am

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.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby gsf » Mon Nov 20, 2006 3:38 pm

leon1789 wrote: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)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Mon Nov 20, 2006 3:47 pm

gsf wrote:
leon1789 wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Mon Nov 20, 2006 3:56 pm

RW wrote:
gsf wrote:
leon1789 wrote: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
Last edited by gsf on Mon Nov 20, 2006 3:00 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby leon1789 » Mon Nov 20, 2006 4:02 pm

leon1789 wrote: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.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby gsf » Mon Nov 20, 2006 6:58 pm

leon1789 wrote:
leon1789 wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby leon1789 » Mon Nov 20, 2006 7:34 pm

gsf wrote:aha, your notation overloads ","

that's right...

gsf wrote: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.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby RW » Mon Nov 20, 2006 7:57 pm

leon1789 wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Mon Nov 20, 2006 8:16 pm

RW wrote: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?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby leon1789 » Mon Nov 20, 2006 8:21 pm

RW wrote: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)
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ravel » Tue Nov 21, 2006 10:29 am

leon1789 wrote: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.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Backdoor Conjecture

Postby gurth » Fri Sep 10, 2010 6:21 pm

gsf wrote:
RW wrote: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?
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Re: Solution to Ocean's #4/gold

Postby JPF » Sat Sep 11, 2010 6:47 pm

Hi gurth,
Welcome back!

gurth wrote:
RW wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

M2 Conjecture

Postby gurth » Sun Sep 12, 2010 3:17 pm

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.
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa


Return to Advanced solving techniques