SuDoKu solver

[Brovnik]

The Times in the UK has recently added SuDoKu puzzles, and I thought Perl could solve them.

Sudoku puzzles are a 9*9 grid, with the properties that each column, row and 3*3 grid have the numbers 1..9.

The puzzle is presented as a partially filled in grid, and you have to solve the rest. So, given :

..21.64..
..93875..
7...2...8
..1...7..
.9..3..6.
..5...8..
8...6...5
..34786..
..49.13..

Where . means "unknown", solve the rest of the puzzle.

I thought - there must be a cool way to solve these, how about Quantum::Superpositions.

And indeed, there is (at least for the easier puzzles).

Edit:

The Superpositions initially hold any(1,2,3,4,5,6,7,8,9), and, as more information is found out, the possible states are reduced until there's only one eigenstate left, in which case we know the actual value.

Pseudo code :

For each cell with eigenstates > 1, $cell = $cell != all(@known_values), where @known_values are the known values from the column, row or 3*3 square.

Loop round each cell until there are no more changes.

I have added the full code at SuDoKu solver.

Enjoy.

[Brovnik]

New version 2 uploaded 28-Dec-04 SuDoKu solver, adding lots of documentation and comments, and now handles more complex puzzles.

Around 6 seconds to solve a "fiendish" puzzle.