Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
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.

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.

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?
[Corion]: marto: Ouch - I would've thought that kids adapt much better, but that's obviously not the case...
[marto]: well, their mother let them sleep till 15:00 & 12:00 last week, which didn't help them adjust :P
[Corion]: I was "productive" over the weekend in the sense that I revived my old "Perlmonks on SQLite" code, which likely means I can get a test instance back up running on my webhost. Small steps :)
[Corion]: marto: Ow, no, that doesn't help at all :)
[choroba]: Related to the new release, anyone could explain this or this tester report?
[Discipulus]: hello crew! marto thanks for the message: but I how can I help? i'm testing cpan Padre atm problem with Client::Debug
[choroba]: I don't happen to have 5.10.0 nor 5.8.5 handy...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (11)
As of 2018-06-25 08:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?



    Results (126 votes). Check out past polls.

    Notices?