Sudoku Solving(norvig.com)
norvig.com
Sudoku Solving
http://norvig.com/sudoku.html
16 comments
I remember doing something very similar in college. My first cut used a hideous object model, but my second go at it used a 3 dimensional matrix to track all of the data and was much faster and space efficient.
The "Why?" at the end of the article pretty much sums up why I can't play most board games and puzzles. Once you 'solve' sudoku, chess, connect 6, ect. it really takes the fun out of it, even if your brain doesn't calculate the solution as quick as your code.
The "Why?" at the end of the article pretty much sums up why I can't play most board games and puzzles. Once you 'solve' sudoku, chess, connect 6, ect. it really takes the fun out of it, even if your brain doesn't calculate the solution as quick as your code.
Doesn't apply to chess imho. I still keep discovering different views of the game on occasional plays. The standard algorithm takes too much time, so you have to find out how to see what's important.
I played chess for a while in a chess club. But to become any good you need to memorize a lot of positions to be able to efficiently recognize good moves. Playing creatively to have fun almost always leads to defeat.
I think you're being a bit unfair to chess, but anyway you can still play Go. I think it's far from "solved" as amateurs beat computer programs very often, as I understand.
Norvig tries to test his program against the hardest puzzle he can find, but only tries to find this hard puzzle by generating random ones. The program Sudoku Susser (http://www.madoverlord.com/projects/sudoku.t) actually comes with “the hardest sudoku in the world”, which I think the author of that program has proven somehow, so Norvig should try his program on that.
Sudoku Susser can solve sudoku puzzles not only the brute-force way shown in the article, but also using “human” reasoning, and show you all the steps.
Sudoku Susser can solve sudoku puzzles not only the brute-force way shown in the article, but also using “human” reasoning, and show you all the steps.
I wouldn't call constraint propagation "brute-force". It isn't enumerating every combination of values and backtracking (as either a non-contstraint Prolog program or a C program with up to 81 nested for-loops would). Rather, it's removing every possibility that has already been canceled out (constraint propagation), then saving undo information, making one guess, and seeing if that sets off another chain reaction or reaches a solution.
He acknowledges the possibility of using more "reasoning" in the article, but dismisses it:
"We could try to code more sophisticated strategies. For example, the naked twins strategy looks for two squares in the same unit that both have the same two possible digits. [...] Coding up strategies like this is a possible route, but would require hundreds of lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle."
If you want to read more about constraint programming, there is an excellent overview chapter in CTM (http://www.info.ucl.ac.be/~pvr/book.html). "The Art of the Propagator" (http://dspace.mit.edu/handle/1721.1/44215) is also good, though it focuses more on arithmetic value propagation than set propagation problems like sudoku. For more advanced material, look at the clp(FD) papers by Danial Diaz (http://cri-dist.univ-paris1.fr/diaz/publications/cv-short.ht...); familiarity with Prolog terminology will be helpful.
He acknowledges the possibility of using more "reasoning" in the article, but dismisses it:
"We could try to code more sophisticated strategies. For example, the naked twins strategy looks for two squares in the same unit that both have the same two possible digits. [...] Coding up strategies like this is a possible route, but would require hundreds of lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle."
If you want to read more about constraint programming, there is an excellent overview chapter in CTM (http://www.info.ucl.ac.be/~pvr/book.html). "The Art of the Propagator" (http://dspace.mit.edu/handle/1721.1/44215) is also good, though it focuses more on arithmetic value propagation than set propagation problems like sudoku. For more advanced material, look at the clp(FD) papers by Danial Diaz (http://cri-dist.univ-paris1.fr/diaz/publications/cv-short.ht...); familiarity with Prolog terminology will be helpful.
He could have used Mechanical Turk to solve them. ;)
Growing up, we had a favorite game. That is until my sister solved it in that going first you could always win. It wasn't as fun after that.
Growing up, we had a favorite game. That is until my sister solved it in that going first you could always win. It wasn't as fun after that.
I like that one.
Ours was a different game: Mühle. Also Mill or Nine Men's Morris.
I just discovered that Ralph Gasser solved it in 1996 using retrograde analysis and an 18-ply alpha- beta search. [1] Becoming "the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods."
[1] http://library.msri.org/books/Book29/files/gasser.pdf
Ours was a different game: Mühle. Also Mill or Nine Men's Morris.
I just discovered that Ralph Gasser solved it in 1996 using retrograde analysis and an 18-ply alpha- beta search. [1] Becoming "the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods."
[1] http://library.msri.org/books/Book29/files/gasser.pdf
Would be interesting to see how this fares performance-wise in comparison:
http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-c...
It's a sudoku solver based on Cryptol, which is "... a language tailored for cryptographic algorithms." built on top of Haskell. The amazing this is that all you need to define is a function that checks whether a given board is solved. Cryptol does the searching for you!
http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-c...
It's a sudoku solver based on Cryptol, which is "... a language tailored for cryptographic algorithms." built on top of Haskell. The amazing this is that all you need to define is a function that checks whether a given board is solved. Cryptol does the searching for you!
I find that calculating the sequence of stereo pairs for an MP3 file is much simpler and more accurate if I dispense with the human listener.
For instance, I just rendered "In the Year 2525" 593 times faster than a human can listen to it on a single thread of a core i3.
For instance, I just rendered "In the Year 2525" 593 times faster than a human can listen to it on a single thread of a core i3.
Can someone explain the Ben Laurie quote? I know what Sudoku is, and I know what a DOS attack is. I don't see the connection between the two.
Sudoku has a human using their mind to solve things which don't need to be solved. A denial of service attack leaves a computer trying to handle things which don't need to be handled. So they have something trying to deal with things that don't need to be dealt with.
Thank you.
If you really want speed, then I would recommend using a good implementation of Dancing Links for solving constraint satisfaction problems. Don Knuth proposes a doubly linked list structure to speed up recursive state space exploration: www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz.
Mentioned this below as well, but got a pretty straight forward ruby implementation of Knuths Dancing Links up at:
https://github.com/biilmann/Ruby-DLX-Sudoku-Solver
It's not hyper-fast (for speed I actually implemented it as a c-extention to ruby, but it's a long time ago and I don't think I have the code around by now) but being ruby it's fairly easy to read.
Can really recommend reading the paper on Dancing Links and playing around with the algorithm, its such a great feeling once you start visualizing how the linked list trick works :)
https://github.com/biilmann/Ruby-DLX-Sudoku-Solver
It's not hyper-fast (for speed I actually implemented it as a c-extention to ruby, but it's a long time ago and I don't think I have the code around by now) but being ruby it's fairly easy to read.
Can really recommend reading the paper on Dancing Links and playing around with the algorithm, its such a great feeling once you start visualizing how the linked list trick works :)
Dancing Links is definitely a fun algorithm to implement. I wrote one in Python a while back and included an option to generate graphs as it went through the recursion tree. I put up a quick page at http://cavernum.net/dlsudoku/ demonstrating them.
I wrote one in JavaScript a long time ago, again using a simple backtracking algorithm.
http://www.amrittuladhar.com/projects/sudokusolver/
EDIT: Just realized the "load puzzle" feature doesn't seem to work on Chrome, but it does in other browsers.
http://www.amrittuladhar.com/projects/sudokusolver/
EDIT: Just realized the "load puzzle" feature doesn't seem to work on Chrome, but it does in other browsers.
Sadly it is a backtracking algorithm which is not proper Sudoku solving technique. (Opinions vary on the topic.)
I'm curious... what would be the 'proper' technique?
solving without trial and error at all.
It really depends on why you want to solve them.
In some cases you might want the algorithm that solves them to also give you some kinda hint on how hard it would be for a human to solve it.
The most efficient algorithm I know of to solve these kind of problems is Knuth's Dancing Links X algorithm. It's beautiful and very fun to implement.
I have a simple ruby implementation of it geared to solve sudokus online on github: https://github.com/biilmann/Ruby-DLX-Sudoku-Solver
In some cases you might want the algorithm that solves them to also give you some kinda hint on how hard it would be for a human to solve it.
The most efficient algorithm I know of to solve these kind of problems is Knuth's Dancing Links X algorithm. It's beautiful and very fun to implement.
I have a simple ruby implementation of it geared to solve sudokus online on github: https://github.com/biilmann/Ruby-DLX-Sudoku-Solver
That strikes me as extremely unlikely.
I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
Glenn Flower has written an (open source) program that solves using constraint propagation only. It does solve some of the hardest Sudoku's.
He discusses the strategies used here: http://www2.research.att.com/~gsf/sudoku/
He discusses the strategies used here: http://www2.research.att.com/~gsf/sudoku/
From the first paragraph of your link:
> The solver uses depth first and/or breadth first with constraint propagation to prune the search
That would be backtracking.
Further, the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them. The article itself states that for solving, backtracking with fewer constraints performs better.
> The solver uses depth first and/or breadth first with constraint propagation to prune the search
That would be backtracking.
Further, the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them. The article itself states that for solving, backtracking with fewer constraints performs better.
You are right that "the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them"
I shared the link because I found his sudoku generator and the constraint methods interesting.
> That would be backtracking.
Let me quote the first para in full:
I shared the link because I found his sudoku generator and the constraint methods interesting.
> That would be backtracking.
Let me quote the first para in full:
The solver uses depth first and/or breadth first tree search
with constraint propagation to prune the search for the next
best move (forms of forward checking.) There are space/time
tradeoffs between depth/breadth first search and the constraints
used; sudoku(1) has options to control the combinations.
The common characteristic for all constraints, here and elsewhere,
is that they avoid trial and error. Its fine for a computer
to guess and backtrack but a definite breach of puzzle manners
to require a human to do so.
The constraint-finding is for generating puzzles that are easy, hence the comment about puzzle manners.
I usually solve them by hand without guess and check, though occasionally, you get down to where there are pairs of values where you have no choice but to try one and see what works (or maybe I just need to figure out more constraints to use).
[deleted]
Sudoku are designed so that there is always a correct move that does not require guesswork.
That is not true.
They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move.
However, finding that correct move is exactly as hard, in the computational sense, as finding the solution to the entire puzzle.
> . . . | . . . | . 1 2
> . . . | . . . | . . 3
> . . 2 | 3 . . | 4 . .
> ------+-------+------
> . . 1 | 8 . . | . . 5
> . 6 . | . 7 . | 8 . .
> . . . | . . 9 | . . .
> ------+-------+------
> . . 8 | 5 . . | . . .
> 9 . . | . 4 . | 5 . .
> 4 7 . | . . 6 | . . .
There should only be one solution. Enjoy yourself, and remember: No guessing! (Source: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptio...)
They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move.
However, finding that correct move is exactly as hard, in the computational sense, as finding the solution to the entire puzzle.
> . . . | . . . | . 1 2
> . . . | . . . | . . 3
> . . 2 | 3 . . | 4 . .
> ------+-------+------
> . . 1 | 8 . . | . . 5
> . 6 . | . 7 . | 8 . .
> . . . | . . 9 | . . .
> ------+-------+------
> . . 8 | 5 . . | . . .
> 9 . . | . 4 . | 5 . .
> 4 7 . | . . 6 | . . .
There should only be one solution. Enjoy yourself, and remember: No guessing! (Source: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptio...)
Well, an ambiguous Sudoku is like a 12 line sonnet...
It isn't computationally relevant but even if trial and error were a simpler approach I feel like that is not in the spirit of the game. Sudoku is a number maze, the goal is to backtrack.
Also I refuse to attempt something that is supposedly too difficult for humans to solve, I'm incapable of quitting puzzles and don't relish spending the next X hours proving it can be done :)
It isn't computationally relevant but even if trial and error were a simpler approach I feel like that is not in the spirit of the game. Sudoku is a number maze, the goal is to backtrack.
Also I refuse to attempt something that is supposedly too difficult for humans to solve, I'm incapable of quitting puzzles and don't relish spending the next X hours proving it can be done :)
I believe the above puzzle has only one valid solution.
9x9 grid of digits with an ambiguous solution is not a Sudoku. It is part of the definition.
Within the set of initial grids that have unambiguous solutions there are ones which require guessing or backtracking, these are generally not considered proper Sudokus and are not presented to humans to solve.
A Sudoku is not a destination, it is a journey.
Within the set of initial grids that have unambiguous solutions there are ones which require guessing or backtracking, these are generally not considered proper Sudokus and are not presented to humans to solve.
A Sudoku is not a destination, it is a journey.
If a Sudoku has one and only one solution, then it is always solvable without guessing or backtracking. It just might not be within the scope of the human brain. There exist (many) configurations where every cell is influenced by every other, so to solve any one cell essentially requires a simultaneous solve of the entire puzzle. There's no theoretical reason a human couldn't do that too; it's a problem simply of computational capacity not fundamental approach.
How would you structure a program to solve such a puzzle without having it generate and test potential solutions along the way?
If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones).
I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).
I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).
That would be a big database. (10^21 entries,roughly.) http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerati...
That's why I called it pathologic... ;)
Edit: using the symmetries described in the same Wikipedia article, the size of the database could be reduced significantly to roughly 5*10^9, which is quite manageable.
Edit: using the symmetries described in the same Wikipedia article, the size of the database could be reduced significantly to roughly 5*10^9, which is quite manageable.
> I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like.
You might be interested in the article linked to by this post.
You might be interested in the article linked to by this post.
The code in the post is based on depth-first search, which basically is a trial and error approach. A well implemented and effective one thanks to constraint propagation, but it is still trial and error. And there are cases, in which backtracking (trial and error) is necessary - at least one of them is documented in the post (the puzzle "hard1" that took 188 seconds).
There is no meaningful difference between trial and error and without trial and error. It makes this no less of an algorithm.
If you get down to trial and error at all, your best odds are 50/50. If it's easy enough to guarantee the right guess, it's not a guess.
There is no meaningful difference between trial and error and without trial and error.
[deleted]
I wrote one in C# a while ago:
http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...
http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...
I did the same, need to dig into my back up hard drive to find it.
Maybe i'm going to expose a REST api for generating sudokus. Do you think this might be interesting?
"Did you know that in order to generate a sudoku you need first to solve it?"
"Did you know that in order to generate a sudoku you need first to solve it?"
[deleted]
The answer is just 3 words: depth first search. I don't get why such a tedious article was written for such a simple, common, and obvious solution.
http://news.ycombinator.com/item?id=2374763
another php version
another php version
Very true.