Sunday 11 September 2016

How do I solve the world's hardest sudoku?


This question is posted under the guidelines Don't worry too hard about restricting or regulating anything that isn't turning into a problem yet. If you don't agree that this question is on topic, please go to that meta thread and talk about why you feel that way!*


Solve this Sudoku. Post how you did it in your answer. Enjoy!


8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..


Note: I put this program into the solver on sudokuwiki.org and it couldn't find any numbers. I then gave it cell H7 (the only cell with two possibilities) and still no luck. Then I gave it cell G7 (which became the only cell with two possibilities) and it was only able to solve one cell before it got stuck.


Here's the website of the mathematician who discovered this puzzle.



Answer



Guessing single values in a depth-first search is sub-optimal.



So, here is a reasoning chain based on a breadth-first hypothesis/disproof method (which my stepson reluctantly calls "educated guessing").


Just following the chain including contradictions requires to solve 23 variants of the sudoku, so it's best used with a computer aided solver. However, it does not require any fancy algorithms to follow it. (I use my own home grown unoptimized python program, so there is no real computing power involved either).


The notation follows spreadsheet conventions (column = letter, row = number) (or chess if you will).


STA Original Sudoku G8: 3,9
HYP # I8: 3,9
DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6
STA # I8: 3,9 + B1: 6
DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9
STA # I8: 3,9 + B1: 6 + A2: 5,9
DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8

DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7
STA I8: 2,7
HYP I8: 2,7 # G7: 5
DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8
STA I8: 2,7 # G7: 5 + G4: 1,8
DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6
STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6
DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8
DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9
STA I8: 2,7 + G7: 3,9

HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6
DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7
STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7
DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9
STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9
PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL

I have put up screen shots of the steps and a quick explanation of the method at World's Hardest Sudoku. Since I am only interested in solving hard puzzles by "educated guessing", I found that this sudoku is actually not so hard as advertised (1 level of hypothesis + 1 lookahead = 2 levels of hypotheses). In fact, I have not yet found a sudoku that requires more than 2 levels of hypotheses + one lookahead (= 3 levels of hypotheses).


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...