Hacker News Reader

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.

View on HN

Constraint 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) 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.

It is the refusal to exploit any specific properties that makes it fun :). Real Sudoku solvers have been around for ages.

Genetic 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

Reply on news.ycombinator.com