### 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?
 [stevieb]: perldigious: video near our hq in Montreal. Here in Calgary, it's -28c... we've only got 3" of snow so far, but there are several feet in the mountains already [perldigious]: Snowshoeing time stevieb? I need to buy a pair so I can walk my German Shepherd properly through the country. [stevieb]: yeah, I snowshoe a fair amount in the mountains. I also use spikes similar to these very often as well [stevieb]: LOL you can easily replace "Helsinki" with "Alberta" [perldigious]: I used to live at the top of a very steep hill stevieb, I can relate to the video. Literally used to have to build up momentum and try to force my vehicle to make it up the hill to park in my driveway properly... didn't always make it.

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (10)
As of 2016-12-06 16:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
On a regular basis, I'm most likely to spy upon:

Results (112 votes). Check out past polls.