22
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ To whoever close voted here, please explain why? $\endgroup$
    – durron597
    Commented May 19, 2014 at 14:18
  • 1
    $\begingroup$ To be fair, there is a question, right at the beginning of the post: "Solve this Sudoku. Post how you did it in your answer." While it's true that neither of those sentences ends in a question mark, I believe it can be easily assumed that the question is "How can you solve this puzzle"? The question then talks about how some solvers can't solve it, which is just background information. $\endgroup$
    – Xynariz
    Commented May 20, 2014 at 21:08
  • 6
    $\begingroup$ For this to be a good question, it should include why we would want to solve this Sudoku, out of the bazillion possible Sudokus. It could use a clearer introduction that explains that it was specifically designed to be hard to solve. $\endgroup$
    – SQB
    Commented May 21, 2014 at 19:28
  • 2
    $\begingroup$ I disagree with "too broad" as the reason to VtC. If it is a proper Sudoku, it should have only one possible answer. $\endgroup$
    – SQB
    Commented May 21, 2014 at 19:29
  • 2
    $\begingroup$ Looking at this question nearly a year later, we've decided as a community that questions about solving specific questions are on-topic. $\endgroup$
    – Kevin
    Commented Mar 29, 2015 at 23:59

4 Answers 4

Reset to default
19
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/… $\endgroup$
    – Simon Streicher
    Commented Apr 10, 2017 at 18:42
  • $\begingroup$ @SimonStreicher The 17-clue sudoku, you are citing is hard, but not among the hardest sudokus in the context of my algorithm. Generally, there is no correlation beween the number of clues and the hardness of a sudoku. I have put up some statistics about the sudokus I have analyzed. $\endgroup$
    – wolfmanx
    Commented Apr 11, 2017 at 23:05
  • $\begingroup$ @SimonStreicher I have analyzed the list of top 95 sudokus (namely the 95 Hard Puzzles). There are 5 sudukos with level hard (2 levels of Hypotheses are necessary), which is still 2 levels below the 101 hardest sudokus I have found. $\endgroup$
    – wolfmanx
    Commented Apr 12, 2017 at 15:04
  • $\begingroup$ Thanks for the info, I'm still trying to make sense of this all, luckily your website is quite thorough. $\endgroup$
    – Simon Streicher
    Commented Apr 12, 2017 at 20:42
  • $\begingroup$ @SimonStreicher The core of it is about reducing the search space from activating single values to easily recognizable patterns (pairs) which are used to generate binary decisions with increased elimination of possibilities. E.g. cell1 allows for 2 possible values v1 and v2, cell2 allows for the same possible values, but additionally one or more other possibilities v3, v4, v5. Therefore, cell1 and cell2 are either a pair (both contain v1 and v2) or cell 2 can only be one of v3, v4, v5. This hypothesis is then checked. $\endgroup$
    – wolfmanx
    Commented Apr 13, 2017 at 22:13
13
$\begingroup$

For this puzzle, while it has one and only one solution, no known patterns work on it, other than a slightly more intelligent guess-and-check. The number of steps one has to look ahead in order to reduce away clues is the metric here, and this puzzle needs nine sequential guesses to reach a solvable state.

The solver on SudokuWiki can't get it because it would simply take too long to do in Javascript, and it's not programmed to guess numbers.

The solution requires one to assume the values of squares, and then reduce the puzzle to see if you need more assumptions - if you do, make another one and continue. It is a depth-first-search of the possible solutions, in essence. The solver on sudoku-solutions does come up with the solution to this puzzle, but when asked to provide the steps, declares:

This solver could not solve the puzzle completely by logic, this does not mean there is not a logical solution.

and then promptly fails to list any of the steps it used to solve it. This only happens when the solver must use brute-force branching guessing to find the solution.

As a result, there is no way I myself could reasonably provide a "how to solve this puzzle" answer, since doing so would involve finding these specific chains and explaining why the other vast quantity of chains don't work.

But that's how you do it: assume a square is a number, then another, then another, and keep checking until you've come to a sequence that still makes sense and allows you to solve the puzzle, or you've come to a contradiction and need to back up and try again. I'm afraid I think this is the best answer you can get to this question.

Since you did ask for a solution to the puzzle, however, I can provide it (mouseover the spoiler block):

enter image description here

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Good old recursion. $\endgroup$
    – Xynariz
    Commented May 28, 2014 at 0:13
  • $\begingroup$ I managed to solve it with recursion depth of 2 guesses at most. The "Naked Singles" strategy ran a total of 61812 times (after some caching done at a higher level, without that the run count is in the millions), the "Hidden Singles" strategy 32892 times (plus another 28920 which were served from a cache) and a search with depth only 1 was run 256 times and served from cache another 15 times (at each point only one guess was done, although I believe most of these runs actually happened within the next one), and the two-level search (where you'd do 2 guesses) only ran once and got it. $\endgroup$
    – Paul Stelian
    Commented Oct 6, 2019 at 19:26
  • $\begingroup$ (also this is the only puzzle that didn't crack with my program with only ONE level of guessing) $\endgroup$
    – Paul Stelian
    Commented Oct 6, 2019 at 19:27
1
$\begingroup$

Download the prime minister of Singapore's Sudoku solver and feed it this puzzle (ONLY if you're REALLY stuck). Believe it or not, that prime minister made a pretty robust program, and although it looks like it gets stuck for a while there, it eventually comes out with the following solution:

862 || 751 || 349
943 || 628 || 157
571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

Apparently it is possible to solve with logic, though, according to the guy who invented this puzzle. It just took the solvers 24 hours to do it.

Note: This puzzle has the 1 on the 7th line in a different position as the question's. This puzzle has multiple solutions.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I doubt this original puzzle has multiple solutions (if that is whats implied). Your input to the PM's solver is probably wrong: row 3, column 7 is given as input as "1", not "7" (one of the observes). Given the correct input to the exe, it outputs the known solution. $\endgroup$
    – Simon Streicher
    Commented Apr 7, 2017 at 15:36
  • 1
    $\begingroup$ @SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1 $\endgroup$
    – depperm
    Commented Aug 9, 2017 at 17:53
  • $\begingroup$ Does it get stuck for more than 5 seconds? My very simple solver manages to get it in about that amount of time. $\endgroup$
    – Paul Stelian
    Commented Oct 6, 2019 at 19:27
0
$\begingroup$

Just to add another computer-based solution, then using the MiniZinc modelling language you can write the following program:

int: n;
array[1..n, 1..n] of 0..n: initial_grid;
int: reg;
array[1..n, 1..n] of 1..reg: regions;

array[1..n, 1..n] of var 1..n: final_grid;

include "alldifferent.mzn";

constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]);
constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ]));
constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ]));

constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ]));

solve satisfy;

output [ show_int(1, final_grid[r, c]) ++
         if c = n then
           ("\n"
           ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n"  else "" endif
           )
         elseif c mod 3 = 0 then " | "
         else " "
         endif
       | r, c in 1..n ];

Along with the appropriate data file:

n = 9;
reg = 9;

regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]);

initial_grid = 
[| 8, 0, 0, 0, 0, 0, 0, 0, 0,
 | 0, 0, 3, 6, 0, 0, 0, 0, 0,
 | 0, 7, 0, 0, 9, 0, 2, 0, 0,
 | 0, 5, 0, 0, 0, 7, 0, 0, 0,
 | 0, 0, 0, 0, 4, 5, 7, 0, 0,
 | 0, 0, 0, 1, 0, 0, 0, 3, 0,
 | 0, 0, 1, 0, 0, 0, 0, 6, 8,
 | 0, 0, 8, 5, 0, 0, 0, 1, 0,
 | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] 
;

And using the default solver on a fairly standard laptop the solution comes out in 100ms, which does beat PM Lee's C++ implementation by a considerable margin.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this algorithm based on linear programming? $\endgroup$
    – Beni Bogosel
    Commented Oct 14, 2016 at 22:40
  • $\begingroup$ It's in the same realm - the solver is a constraint programming solver, which works well since the problem isn't really linear but it is a bunch of constraints. It uses a combination of heuristics to reduce the space of possible solutions with some fairly basic search methods. $\endgroup$
    – ConMan
    Commented Oct 31, 2016 at 5:30
  • $\begingroup$ I'm impressed. My manual, very simple solver in Kotlin beats it in about 5 seconds on my laptop, using a search depth of maximum 2. $\endgroup$
    – Paul Stelian
    Commented Oct 6, 2019 at 19:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.