Solving Sudoku with genetic algorithms | Hacker News Reader

Solving Sudoku with genetic algorithms

fakeguido.blogspot.com

41 pointsdaivd14 comments

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.

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

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.

"I think a Sudoku puzzle that is harder for humans would not be that much harder for optopus to solve, but I have not tested it."

Try it. You may be surprised. Here's a good one: zonkedyak.blogspot.com/2006/11/worlds-hardest-sudoku-puzzle-al.html

Also try a 5-based instance of the same problem (against the standard 3-base of sudoku, that is, a 5x5 matrix of 5x5 matrices containing the numbers 1-25), and compare performance of that problem to a normal solver.

I'm not going to tell you what will happen, because you won't believe me. Somebody seems to have cast a glamor on GP.

That is a nice instance, an optimization solver took 13 seconds to solve instead of the 0.2 seconds for the problem posted by the OP.

Some people in combinatorial optimization are addressing the problem of finding the hardest Sudoku problem. For an introduction of how the problem can be modeled, see:

http://diuflx71.unifr.ch/lpl/lplmodels/puzzles/sudoku.pdf

OK, I will try it. And if you had said that it would be almost impossible, because there are too many local minima, I would have believed you.

A serious try with GA would require abandoning Python for a faster fitness function in C, that does not copy dozens of lists back and forth. I estimate that just about anyone could make it more than 100 times as fast. The slow implementation will have to suffice for now.

The interesting part is of course not the absolute times, but if the complexity scales differently. If a real Sudoku solver takes about 50 times as long to solve that problem, I will consider it a victory if the GA does the same.

As a quick fix, check out Psyco. I've had success running algorithms in Python up to 6-8x faster.

Plus one for posts about Genetic Algorithms. My masters research was on Genetic Algorithms. Btw for those interested in learning more about the field my professor has a free book out on Metaheuristics (Which includes genetic algorithms) at http://cs.gmu.edu/~sean/book/metaheuristics/

That book is fantastic!

While we're at it: http://www.gp-field-guide.org.uk/

Cool! PDF version is free.

Isn't sudoku bit problematic problem for GA as there is just one correct solution and the rest are just wrong, compared to a problem that has solutions that are better or worse, but potentially no solution is absolutely correct?

A fair point (though technically sudoku can have multiple solutions, they are all equally correct; there is no range of correctness, it's just binary). However, I think something like this is useful as a proof of concept for a GA system, because it's easy to judge its solutions. Many textbook examples of GA I've seen involve evolving a best fit line for a given line, and the simple examples use functions like y = x^2+1 because its easy to judge completion.

Reply on news.ycombinator.com