3 ms·
While genetic algorithms are useful for solving certain problems, Sudoku puzzles exhibit a strong combinatorial structure that can be exploited by other approac
by merraksh 16y ago
While genetic algorithms are useful for solving certain problems, Sudoku puzzles exhibit a strong combinatorial structure that can be exploited by other approaches (Constraint Programming above all, I think).
When modeled as feasibility problems, for instance, their solution can be found very quickly -- it took 0.2 seconds to solve that instance on my laptop.
- daivd 16y agoIt is the refusal to exploit any specific properties that makes it fun :). Real Sudoku solvers have been around for ages.
- merraksh 16y agoGenetic algorithms usually do exploit the structure of the problem in order to make crossover/mutation more efficient. This is indeed what the OP says: For more difficult Sudoku puzzles, I would definitely go with the permutation genome
- mzl 16y agoConstraint programming is definitly the technology of choice for solving Sudoku puzzles. There is a nice article by Helmut Simonis (http://www.4c.ucc.ie/~hsimonis/shikaku.pdf http://www.4c.ucc.ie/~hsimonis/shikaku.pdf) that shows how good various propagation strengths and model variants are for solving 9 times 9 Sudokus (short answer, full propagation on individual rows/columns/squares plus shaving never needs search). For 25 times 25 Sudokus on the other hand, propagation alone is in my experience not enough, and a lot of search is needed.