Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

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.

Comment on SuDoKu solver
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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://415623]
Approved by herveus
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (9)
As of 2014-10-01 12:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (18 votes), past polls