Write a Sudoku Solver in Python

garshol.priv.no

12 points·mace··6 comments

Peter Norvig wrote something along similar lines: http://norvig.com/sudoku.html

Highly recommended.

My instinct would be to do it with some kind of Metropolis Monte Carlo algorithm.

1. For initial conditions, distribute digits randomly throughout the 3x3 boxes. The only condition we need to apply at this stage is to not repeat a digit within a 3x3 box.

2. Calculate the number of "clashes" -- i.e. rows or colums where there's a digit repeated.

3. Make a trial move: Pick a 3x3 box at random, pick two squares within it, and swap their digits (obviously, don't pick squares with 'fixed' digits in them).

4. Recompute the new number of clashes C. If the new number of clashes is less than the old one, the move is accepted. If the new number is larger than the old one, it's not necessarily rejected, but will be accepted with a probability proportional to exp(-dC) (this gives us a small chance of moving "uphill" in clash-space so we don't get trapped in local minima).

5. If the number of clashes is still greater than zero, go back to 3.

I don't know how efficient this would be. Probably better than brute force.

Actually, I don't see that you're guaranteed that this would terminate at all. This algorithm could easily work down to a local minimum and then find that there's no route from there to the correct solution.

Which is why the algorithm provides the possibility of moving uphill.

I love Python, but ProLog kick's its ass here:

http://blog.milesbarr.com/2007/01/prolog-sudoku-solver/

A cool OCaml version:

http://www.ffconsultancy.com/ocaml/sudoku/index.html

Reply on news.ycombinator.com