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.
I 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:
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.
In 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.
7 comments
[ 3.0 ms ] story [ 29.0 ms ] threadAlthough 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.
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-...
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.
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.
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.