Solving Every Sudoku Puzzle
norvig.com
Solving Every Sudoku Puzzle
1–8 of 8 posts
Re: Solving Every Sudoku Puzzle
#2Sudoku puzzles are Assignment problems (http://en.wikipedia.org/wiki/Assignment_problem), and can be cast as Graph Coloring problems as well (http://en.wikipedia.org/wiki/Graph_coloring).
Although the performances reported are more than good, the discussion on brute-force algorithms omits that some of the cutting-edge research on the topic is in the Constraint Programming community (Sudoku is the typical example of the "all-different" modeling constraint).
One of the most commonly used algorithm used in Optimization (and in feasibility problems as well) is Branch and bound (http://en.wikipedia.org/wiki/Branch_and_bound). Combinatorial problems of that size are relatively small and can be solved in fractions of a second by off-the-shelf commercial software and very little modeling work.
Re: Solving Every Sudoku Puzzle
#3If you want a "seriously hard" puzzle for optimization testing, scale up. What happens if you feed the program a 16x16 or 25x25 or 100x100 Sudoku?
Re: Solving Every Sudoku Puzzle
#4I became interested in Sudoku solving recently, and although I was aware of this essay, I wanted to study the problem first without knowing anything about constraint propagation:
http://cjauvin.blogspot.com/2011/10/journey-into-sudoku-spac...
Next I read the article, and then tried to adapt my previous, naive method with the CP ideas:
http://cjauvin.blogspot.com/2011/10/wormhole-through-sudoku-...
Re: Solving Every Sudoku Puzzle
#5Norvig has some great solutions. However I have still yet to see something that can beat a well coded dancing (http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku... http://en.wikipedia.org/wiki/Dancing_Links) links solution to Sudoku, for speed.
For my money, giving humanistic solutions for sudoku is the more interesting problem. The size of the search space is so constrained that a correctly coded solution will finish so quickly that it's no longer an interesting race. Rating puzzles for how much trouble a real person will have solving is also very interesting.
Re: Solving Every Sudoku Puzzle
#6If this is brand new to you, don't miss the TDD vs BPNDD ("Being Peter Norvig Driven Development"), recently discussed here http://news.ycombinator.com/item?id=3033446
edit btw I certainly don't mean to fan any flames of pro or anti TDD, I just think there's some interesting stuff to discuss.
Re: Solving Every Sudoku Puzzle
#7In his section talking about the brute force method of solving the puzzle, he seriously overestimates the number of possibilities for the whole puzzle.
Example: For grid2, he lists square A2 as having 4 possibilities (1679) and A3 as having 5 possibilities (12679). Which is true, if you ignore the rules of sudoku. Specifically, not all of those combinations are worth trying. If you choose a 1 for square A2, you would not choose a 1 for square A3.
Wikipedia lists there as being 10^21 unique sudoku puzzles, which is many orders of magnitude smaller than his listed 10^38 different combinations for grid2.
In short, I think a proper brute force method would be significantly faster than what he initially thought it would be.
Re: Solving Every Sudoku Puzzle
#8This one pops up from time to time; always an interesting read though.