The New Sudoku Players' Forum

[Addlan]

So, there are a total of 4 branches:

R7C7=3 -> contradiction
R7C7=6 -> unique solution
R7C7=5 -> R5C5=3 -> contradiction
R7C7=5 -> R5C5=8 -> contradiction

Three branches will do:
Look at column 7
R3C7=6 -> contradiction
R7C7=6 -> unique solution
R9C7=6 -> contradiction

R3C7 = 6
{4} {6} {3} {1} {2} {8} {7} {9} {5}
{8} {2} {5} {6} {9} {7} {3} {14} {14}
{9} {7} {1} {5} {4} {3} {6} {8} {2}
{3} {9} {7} {2} {5} {1} {4} {6} {8}
{6} {4} {2} {3} {8} {9} {1} {5} {7}
{1} {5} {8} {7} {6} {4} {9} {2} {3}
{2} {1} {6} {8} {37} {5} {} {34} {9}
{5} {38} {9} {49} {1} {6} {2} {7} {4}
{7} {38} {4} {9} {3} {2} {358} {13} {6}

R7C7 = 6
{4} {3} {5} {1} {2} {8} {7} {9} {6}
{8} {2} {1} {6} {9} {7} {5} {4} {3}
{9} {7} {6} {5} {4} {3} {1} {8} {2}
{1} {9} {2} {7} {3} {5} {4} {6} {8}
{6} {4} {3} {2} {8} {1} {9} {5} {7}
{7} {5} {8} {4} {6} {9} {3} {2} {1}
{2} {1} {7} {8} {5} {4} {6} {3} {9}
{5} {8} {9} {3} {1} {6} {2} {7} {4}
{3} {6} {4} {9} {7} {2} {8} {1} {5}

R9C7 = 6
{4} {3} {5} {1} {2} {8} {7} {9} {6}
{8} {2} {1} {6} {9} {7} {3} {4} {5}
{9} {6} {7} {5} {4} {3} {1} {8} {2}
{137} {79} {39} {27} {8} {5} {4} {6} {13}
{6} {4} {2} {} {3} {9} {8} {5} {7}
{37} {5} {8} {47} {6} {1} {9} {2} {3}
{2} {1} {6} {8} {7} {4} {5} {3} {9}
{5} {8} {39} {39} {1} {6} {2} {7} {4}
{37} {79} {4} {39} {5} {2} {6} {1} {8}

Combine these three chains together, you will get the solution as well. People may find out the relationship between forcing chain and "try and error". However, global "try and error" seems always better than global "forcing chain".

[udosuk]

Thanks Addlan, that was very smart. When I thought about branching I always thought of branching out a cell's possible values, but never about trying a certain digit across a certain row/column/box. So, just wondering would it be useful to apply this technique to a solver program... maybe somebody already is using it?

However, I was trying to focus on the point that "R7C7 is the key cell in this puzzle" because if you put the correct digit in it the whole puzzle can be solved easily... I don't think there is another case?

Another simple 3-way branch is 6 on R7C7/R9C7/R9C9. Unfortunately the 2-way branch of 6 on R7C3/R7C7 can't do it... so I think there is no 2-way branch for this puzzle, unless somebody shows some magic here...

So if the minimum branching complexity is a good measure for difficulty, is there a puzzle that can beat this one, i.e. having a minimum branch of 4 ways or more?

[Addlan]

When I thought about branching I always thought of branching out a cell's possible values, but never about trying a certain digit across a certain row/column/box.

It should have more choices and better chance if trying a certain digit.

BTW, dealing with these hard puzzles, I have almost given in to "try and error". I have thought about various methods for a few weeks, including transformation, fixing the invalid Sudoku, chains etc. I don't think the first two will work and the third won't work better than "try and error" ("proof by contradiction"). Hope people have some good ideas about it, otherwise, I won't feel shame to use "try and error" to solve hard Sudoku (Happy to become a supporter for "try and error").

[udosuk]

It should be called "trial and error", or abbreviated as "T & E"...

When I mentioned "minimum branching complexity", or "minimum width of branching" if you like, of course I need to define what are the valid logic techniques to apply before you branch out...

IMHO, the following are the truly logical techniques (ones that don't "look ahead"):
Hidden 1s, Naked pairs/triples/quads..., entries locked in rows/columns within a box, x-wings, swordfish. (Terms named by angusj...)

The ones that "look ahead" (not to say they're invalid to use but they already has some minor T & E implied):
Colours, forcing chains, turbot fish...

I'm pretty sure I've missed out something/made mistakes (I haven't fully understand all the techniques anyways and there could be new techniques I haven't heard). Anybody is welcomed to correct me...

And like Addlan, I support T & E if one really got stuck...

[darq]

For the puzzle discussed here, there are 3 other key fields:

Code: Select all

  proof #1 (1 step(s) / 0 chained):
    <6:(9,2)> proved by (any of) set(s) of contradiction(s):
        ----
        <6:(9,7)> <6:(9,9)> lead(s) to dead end(s)
        ----
        <6:(1,2)> <6:(3,2)> lead(s) to dead end(s)
        ----
        <3:(9,2)> <7:(9,2)> <8:(9,2)> <9:(9,2)> lead(s) to dead end(s)
        ----
  proof #2 (1 step(s) / 0 chained):
    <6:(7,7)> proved by (any of) set(s) of contradiction(s):
        ----
        <6:(3,7)> <6:(9,7)> lead(s) to dead end(s)
        ----
        <6:(9,7)> <6:(9,9)> lead(s) to dead end(s)
        ----
  proof #3 (1 step(s) / 0 chained):
    <7:(7,3)> proved by (any of) set(s) of contradiction(s):
        ----
        <7:(2,3)> <7:(3,3)> <7:(4,3)> lead(s) to dead end(s)
        ----
  proof #4 (1 step(s) / 0 chained):
    <6:(3,3)> proved by (any of) set(s) of contradiction(s):
        ----
        <6:(3,2)> <6:(3,7)> lead(s) to dead end(s)
        ----
        <6:(1,2)> <6:(1,3)> <6:(3,2)> lead(s) to dead end(s)
        ----

But there exist puzzles with more branched proofs, so that finding only one key field is not sufficient. We need to repeat this step at some point in future. E.g. this puzzle

Code: Select all

 . . 1 | 2 . . | . 6 .
 . . 9 | . . 8 | . 4 .
 . 5 . | . 4 . | 9 . .
-------+-------+------
 7 3 . | . 8 . | . . .
 . . 5 | . 3 . | 1 . .
 . . . | . 6 . | . 3 4
-------+-------+------
 . . 3 | . 2 . | . 9 .
 . 2 . | 8 . . | 5 . .
 . 9 . | . . 1 | 4 . .

requires 2 guessing levels, with first level having 6 branches, one of which leads to another need for guessing. Then there are 3 branches, one of them gives a solution. X Wing must be employed to find a proof by contradiction, or there will be 3 levels of guessing!

[udosuk]

Can't believe I missed those other 3 key cells. Got lazy and didn't try enough guesses I "guess"... ^_^

So, the puzzle you posted could surely reign the title of "hardest puzzle" now? Man, surely takes an effort to solve... Thanks! Now I wonder is there any puzzle that requires 3 levels of guessing... (and then 4... and then 5...) ^_^

Edit: Just discovered that a 6 in R7C2 will lead to the solution directly... so unless there is a mistake this is only a 1-guessing-level puzzle! Or is it impossible to have guessing levels of 2 or more? Now that might be an interesting mathematical questions for the experts here to think about...

[darq]

I forgot to mention explicitly I only consider guesses which have a proof (so you can be sure it's a single-solution sudoku). In this case a proof by contradiction, but there are also proofs by lookahead, probably giving slightly better results. Still some problems require 2 proved guesses for any of the two methods. Like another puzzle from tilps:

Code: Select all

 . . . | . 7 . | . 9 .
 . . . | . . 8 | . . 4
 . 4 2 | . . 1 | . 7 .
-------+-------+-------
 . . 4 | . . . | . . 8
 8 . . | 2 . 5 | . . 9
 5 . . | . . . | 7 . .
-------+-------+-------
 . 7 . | 6 . . | 1 3 .
 2 . . | 8 . . | . . .
 . 6 . | . 3 . | . . .

At sudoku programmers forum some discussed a table algorithm that supposedly can solve every sudoku without a single guess! But it's not easy to follow by humans, as tables for hard problems get big.

[Addlan]

But there exist puzzles with more branched proofs, so that finding only one key field is not sufficient.

After study these hard puzzles, they convince me that the basic rules for solving Sudoku are naked single, hidden single, and proof by contradiction (trial and error), and all other rules are derived from these rules. Though Sudoku itself is strikingly beautiful, the possible number matrix is quite irregular and complex.

[Addlan]

But there exist puzzles with more branched proofs, so that finding only one key field is not sufficient. We need to repeat this step at some point in future. E.g. this puzzle

Code: Select all

 . . 1 | 2 . . | . 6 .
 . . 9 | . . 8 | . 4 .
 . 5 . | . 4 . | 9 . .
-------+-------+------
 7 3 . | . 8 . | . . .
 . . 5 | . 3 . | 1 . .
 . . . | . 6 . | . 3 4
-------+-------+------
 . . 3 | . 2 . | . 9 .
 . 2 . | 8 . . | 5 . .
 . 9 . | . . 1 | 4 . .

requires 2 guessing levels, with first level having 6 branches, one of which leads to another need for guessing. Then there are 3 branches, one of them gives a solution. X Wing must be employed to find a proof by contradiction, or there will be 3 levels of guessing!

I have a stupid but interesting idea to complete this puzzle. If you look at row 3 for digit '6' and '7', try all combinations between '6' and '7', you will find the solution. There are lots of combinations, but fortunately some of them lead to dead end quite quickly.

[Addlan]

But there exist puzzles with more branched proofs, so that finding only one key field is not sufficient. We need to repeat this step at some point in future. E.g. this puzzle

Code: Select all

 . . 1 | 2 . . | . 6 .
 . . 9 | . . 8 | . 4 .
 . 5 . | . 4 . | 9 . .
-------+-------+------
 7 3 . | . 8 . | . . .
 . . 5 | . 3 . | 1 . .
 . . . | . 6 . | . 3 4
-------+-------+------
 . . 3 | . 2 . | . 9 .
 . 2 . | 8 . . | 5 . .
 . 9 . | . . 1 | 4 . .

requires 2 guessing levels, with first level having 6 branches, one of which leads to another need for guessing. Then there are 3 branches, one of them gives a solution. X Wing must be employed to find a proof by contradiction, or there will be 3 levels of guessing!

I have a stupid but interesting idea to complete this puzzle. If you look at row 3 for digit '6' and '7', try all combinations between '6' and '7', you will find the solution. There are lots of combinations, but fortunately some of them lead to dead end quite quickly.

Sorry, the combinations don't work. I miss out some combinations.

[udosuk]

Sorry, I was too excited at finding the "key cell" of the first puzzle posted by darq... of course it should be 2 guessing levels for that one. I just wonder if there's a puzzle that takes 2 or more levels of guessing until you can hit the unique solution (i.e. no key cell)...

Unfortunately darq's 2nd puzzle has a key cell in R2C4 too.

Still waiting to see "the puzzle with no key cell"...

[Edit: sorry, just realised the R2C4 key cell in the 2nd puzzle has to work with "colors" technique to solve it out... (the solver program I use is too powerful). So some implicit guessing is still needed. Maybe that's "the puzzle with no key cell" I was looking for. Need to check more...]

[Big Blue]

@udosuk: I am awfully sorry for causing this confusion - maybe I am missing something about the notation - so let me explain in detail, I hope we are talking about the same Sudoku

column 7 is the one which has as clues (008650070), from top to bottom - right?

in row 7 there is an initial 7, if I count from top to bottom, whereas in row 2, after filling in the obvious and hidden ones, there are three possibilities: 1,3 and 4

now, reading your message I suppose that I am either using the wrong notation for rows and columns (if that is the case, please let me know the "standard notation"), or that we are talking about different sudokus

I was talking about

000100700
020690000
900003082
000000460
640000057
058000000
210800009
000016070
004002000

[darq]

Addlan,

many share your view of sudoku rules, but you can also see it this way: all rules up to jellyfish are different incarnations of one general rule: when you have a crossmatrix of 'value' and 'position' for some constant 'area', and set of N 'values' fits within N 'positions', all remaining 'values' at these 'positions' can be removed. Where 'value', 'position' and 'area' are any of: box id, column id, row id, cell value, position in a box (and position in a row or column, but these come down to column id and row id). Not all combinations make sense, but these which make - produce "standard" rules. The matrix dimension is 9x9 or 3x3, N is in range 2-4 (or only 2 for 3x3 matrix, where box id crosses with column/row id).
(hope I explained it clearly, but may have a language problem)
And what's interesting: a degenerated case, where N=1, comes down to naked/hidden single rules.

And, besides proofs by contradiction, many appreciate the power and elegance of lookaheads. Though personally I also prefer contradictions.


udosuk,

I'm yet to implement swordfish and jellyfish, but without them I couldn't find key cells for these sudokus:

Code: Select all

 . . 9 | . . 1 | . 8 7
 . . . | . . . | 4 . .
 . . 1 | . 8 . | . 6 .
-------+-------+-------
 . . . | 8 3 6 | . 2 .
 . . 6 | . . . | . . .
 4 5 . | . . 7 | . . 6
-------+-------+-------
 5 . . | . . 8 | . . 9
 . 1 . | . 6 . | . . 2
 . . . | 4 2 . | . . .

Code: Select all

 . 6 . | . . . | . 7 .
 9 . . | . 8 . | . . 6
 . . 3 | . . 9 | 1 . .
-------+-------+-------
 . . 8 | . 9 5 | . . .
 . 2 . | 4 . 8 | . 6 .
 . . . | 2 1 . | 8 . .
-------+-------+-------
 . . 5 | 9 . . | 6 . .
 3 . . | . 4 . | . . 8
 . 4 . | . . . | . 2 .

Second of them was also resistent to ubranched proofs by contradiction (unbranched == having more than the first obvious branch with several cells for one value or several values for one cell).

[Addlan]

many share your view of sudoku rules, but you can also see it this way: all rules up to jellyfish are different incarnations of one general rule: when you have a crossmatrix of 'value' and 'position' for some constant 'area', and set of N 'values' fits within N 'positions', all remaining 'values' at these 'positions' can be removed. Where 'value', 'position' and 'area' are any of: box id, column id, row id, cell value, position in a box (and position in a row or column, but these come down to column id and row id). Not all combinations make sense, but these which make - produce "standard" rules. The matrix dimension is 9x9 or 3x3, N is in range 2-4 (or only 2 for 3x3 matrix, where box id crosses with column/row id).
(hope I explained it clearly, but may have a language problem)
And what's interesting: a degenerated case, where N=1, comes down to naked/hidden single rules.

And, besides proofs by contradiction, many appreciate the power and elegance of lookaheads. Though personally I also prefer contradictions.

Right, generalization is often dangerous. I like X-wing, etc, and try to generalise them. Something like swordfish and jellyfish are very hard to be achieved by normal 'proof by contradiction'. Normal 'Proof by contradiction' is often effective in a binary way, and will be more effective if looking for the weak points.

[udosuk]

For the puzzle:

Code: Select all

. . 9 . . 1 . 8 7
. . . . . . 4 . .
. . 1 . 8 . . 6 .
. . . 8 3 6 . 2 .
. . 6 . . . . . .
4 5 . . . 7 . . 6
5 . . . . 8 . . 9
. 1 . . 6 . . . 2
. . . 4 2 . . . .

key cells are: R2C4=9, R3C2=2, R5C1=2, R8C8=7

For this:

Code: Select all

. 6 . . . . . 7 .
9 . . . 8 . . . 6
. . 3 . . 9 1 . .
. . 8 . 9 5 . . .
. 2 . 4 . 8 . 6 .
. . . 2 1 . 8 . .
. . 5 9 . . 6 . .
3 . . . 4 . . . 8
. 4 . . . . . 2 .

key cells are: R1C6=1, R5C3=1, R8C2=7

However, they all required "colors" or "multicolors" to solve out... so maybe the "colors" techniques are too powerful for a puzzle to have no key cells?