### SuDoKu solver

by Brovnik (Hermit)
 on Dec 17, 2004 at 13:33 UTC ( #415623=CUFP: print w/replies, xml ) Need Help??

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.

Replies are listed 'Best First'.
Re: SuDoKu solver
by Brovnik (Hermit) on Dec 28, 2004 at 14:18 UTC
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.

Create A New User
Node Status?
node history
Node Type: CUFP [id://415623]
Approved by herveus
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (12)
As of 2018-04-24 09:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (85 votes). Check out past polls.

Notices?