How do I solve the world's hardest sudoku?
$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!
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.
sudoku
edited Mar 16 '17 at 16:42
Community♦
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
$endgroup$
|
show 3 more comments
$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!
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.
sudoku
edited Mar 16 '17 at 16:42
Community♦
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
$endgroup$
2
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$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
May 20 '14 at 21:08
5
$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
May 21 '14 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
May 21 '14 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
Mar 29 '15 at 23:59
|
show 3 more comments
$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!
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.
sudoku
edited Mar 16 '17 at 16:42
Community♦
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
$endgroup$
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!
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.
sudoku
sudoku
edited Mar 16 '17 at 16:42
Community♦
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
edited Mar 16 '17 at 16:42
Community♦
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
edited Mar 16 '17 at 16:42
Community♦
1
edited Mar 16 '17 at 16:42
Community♦
1
edited Mar 16 '17 at 16:42
Community♦
1
1
asked May 19 '14 at 14:01
durron597durron597
1,43921028
asked May 19 '14 at 14:01
durron597durron597
1,43921028
asked May 19 '14 at 14:01
durron597durron597
1,43921028
1,43921028
2
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$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
May 20 '14 at 21:08
5
$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
May 21 '14 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
May 21 '14 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
Mar 29 '15 at 23:59
|
show 3 more comments
2
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$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
May 20 '14 at 21:08
5
$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
May 21 '14 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
May 21 '14 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
Mar 29 '15 at 23:59
2
2
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$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
May 20 '14 at 21:08
$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
May 20 '14 at 21:08
5
5
$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
May 21 '14 at 19:28
$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
May 21 '14 at 19:28
2
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
May 21 '14 at 19:29
$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
May 21 '14 at 19:29
2
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
Mar 29 '15 at 23:59
$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
Mar 29 '15 at 23:59
|
show 3 more comments
4 Answers
4
active
oldest
votes
$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).
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
$endgroup$
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 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
Apr 12 '17 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
Apr 12 '17 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
Apr 13 '17 at 22:13
add a comment |
$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):
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
$endgroup$
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
add a comment |
$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.
edited Aug 3 '15 at 5:04
Alex Robinson
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
$endgroup$
$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
Apr 7 '17 at 15:36
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
add a comment |
$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.
answered Aug 29 '16 at 6:59
ConManConMan
643318
$endgroup$
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
add a comment |
protected by Community♦ Aug 11 '15 at 13:03
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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).
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
$endgroup$
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 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
Apr 12 '17 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
Apr 12 '17 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
Apr 13 '17 at 22:13
add a comment |
$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).
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
$endgroup$
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 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
Apr 12 '17 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
Apr 12 '17 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
Apr 13 '17 at 22:13
add a comment |
$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).
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
$endgroup$
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).
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
answered Jan 21 '15 at 6:32
wolfmanxwolfmanx
27624
27624
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 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
Apr 12 '17 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
Apr 12 '17 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
Apr 13 '17 at 22:13
add a comment |
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 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
Apr 12 '17 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
Apr 12 '17 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
Apr 13 '17 at 22:13
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 at 18:42
$begingroup$
How well does your solver fair against sudoku's with 17 entries? Eg. theconversation.com/…
$endgroup$
– Simon Streicher
Apr 10 '17 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
Apr 11 '17 at 23:05
$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
Apr 11 '17 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
Apr 12 '17 at 15:04
$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
Apr 12 '17 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
Apr 12 '17 at 20:42
$begingroup$
Thanks for the info, I'm still trying to make sense of this all, luckily your website is quite thorough.
$endgroup$
– Simon Streicher
Apr 12 '17 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
Apr 13 '17 at 22:13
$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
Apr 13 '17 at 22:13
add a comment |
$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):
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
$endgroup$
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
add a comment |
$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):
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
$endgroup$
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
add a comment |
$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):
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
$endgroup$
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):
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
edited May 23 '14 at 2:01
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
answered May 23 '14 at 0:58
ZyerahZyerah
10.2k74788
10.2k74788
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
add a comment |
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
1
1
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
$begingroup$
Good old recursion.
$endgroup$
– Xynariz
May 28 '14 at 0:13
add a comment |
$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.
edited Aug 3 '15 at 5:04
Alex Robinson
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
$endgroup$
$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
Apr 7 '17 at 15:36
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
add a comment |
$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.
edited Aug 3 '15 at 5:04
Alex Robinson
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
$endgroup$
$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
Apr 7 '17 at 15:36
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
add a comment |
$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.
edited Aug 3 '15 at 5:04
Alex Robinson
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
$endgroup$
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.
edited Aug 3 '15 at 5:04
Alex Robinson
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
edited Aug 3 '15 at 5:04
Alex Robinson
1031
edited Aug 3 '15 at 5:04
Alex Robinson
1031
edited Aug 3 '15 at 5:04
Alex Robinson
1031
1031
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
answered May 22 '15 at 23:54
MusicrafterMusicrafter
112
112
$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
Apr 7 '17 at 15:36
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
add a comment |
$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
Apr 7 '17 at 15:36
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
$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
Apr 7 '17 at 15:36
$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
Apr 7 '17 at 15:36
1
1
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
$begingroup$
@SimonStreicher the wrong input is at row 7 column 3 where the 7 should be a 1
$endgroup$
– depperm
Aug 9 '17 at 17:53
add a comment |
$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.
answered Aug 29 '16 at 6:59
ConManConMan
643318
$endgroup$
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
add a comment |
$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.
answered Aug 29 '16 at 6:59
ConManConMan
643318
$endgroup$
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
add a comment |
$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.
answered Aug 29 '16 at 6:59
ConManConMan
643318
$endgroup$
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.
answered Aug 29 '16 at 6:59
ConManConMan
643318
answered Aug 29 '16 at 6:59
ConManConMan
643318
answered Aug 29 '16 at 6:59
ConManConMan
643318
answered Aug 29 '16 at 6:59
ConManConMan
643318
643318
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
add a comment |
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 at 22:40
$begingroup$
Is this algorithm based on linear programming?
$endgroup$
– Beni Bogosel
Oct 14 '16 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
Oct 31 '16 at 5:30
$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
Oct 31 '16 at 5:30
add a comment |
protected by Community♦ Aug 11 '15 at 13:03
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
2
$begingroup$
To whoever close voted here, please explain why?
$endgroup$
– durron597
May 19 '14 at 14:18
$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
May 20 '14 at 21:08
5
$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
May 21 '14 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
May 21 '14 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
Mar 29 '15 at 23:59