Sudoku Solver
July 7th, 2006
I was bored and had a bit of time this morning so I thought I’d practise Python a little and try to write a program to solve Sudoku. I find writing programs like these quite interesting and quite a nice way to learn a language, and unlike copying scripts out of books, the script you produce will be semi-useful. I decided to do it in Python as I’ve not done Python in years and it was kinda rusty.
I’m using a pretty slow and crappy algorithm:
- Load the sudoku puzzle into a multi-dimensional dictionary - the top left square is referenced by [0][0], the bottom right by [8][8].
- Loop through all the squares starting with the top left square and working across. When a blank square is found, try to solve it by:
- Firstly creating a list of all possible values (numbers between 1 and 9)
- Removing the values of known squares on the same row
- Removing the values of known squares in the same column
- Removing the values of known squares in the 3×3 square.
- If there is only one possible solution, fill it in.
- Once it has reached the end, it’ll start another pass beginning at the top left corner again. Some extra squares may be able to be solved now as additional squares have been solved making it possible to solve other squares.
- When all squares have been solved or no further squares have been solved, stop and print the result.
This algorithm is probably pretty slow and won’t always solve the puzzle - it can’t guess and there are some more complicated ways to solve Sudokus which the script doesn’t implement. But for the sake of creating a basic, working Sudoku solver, it does pretty well.
I used the following input (x denotes an unknown square):
91x7xxxxxx326×9x8xxx7×8x9xxx86×3x17x3xxxxxxx6x51×2x84xxx9×5x3xxx2×3x149xxxxxx2×61
It came back with the completed Sudoku in about a second:
918745632532619784647283915286534179394178256751926843169457328825361497473892561
If you want a copy of the source, grab it here. You’ll have to change the path in it around line 13 so it points to your sudoku.txt file. Make sure your sudoku.txt file is formatted correctly with each row of the sudoku on it’s own line and unknown squares designated by an x.
- If you want a proper Sudoku Solver which works properly, there are tons on Google.
- Programming
- Comments(8)
Yo!
Nice solver - I’ve written a few of these for fun too. You may wish to look into prolog solvers, which are absurdly cool because you define how sudoku works and the puzzle instance and it manages to do it with a screenful of code and bloody quickly to boot.
~Ed (a.k.a. shimmer - *shudder*)
Sweet, thanks for the info:)
I’ve duplicated your algorithm in PHP (It’s the language I’m most comfortable in).
Now I’ve done that I can see the limitations of it, and I’m thinking of ways to improve it. The system you’ve used is good as the start of a better solution.
The Sudoku page on Wikipedia has a small section on computer solutions which is quite interesting.
I intend to add a system whereby the script can keep track of the possibilities of all of the boxes, much like a person might do by writing little numbers in the corners of the boxes.
@ Eddie: I’ve used Prolog a little bit for my A2 Level Computing course. I found it difficult to get used to after only using procedural languages before. The most complex thing I managed to code was a family tree where you could ask what relation someone was to someone else. It’s a powerful language though for sure. And I agree; very cool
Sounds cool. I’d love to see it when it’s finished!
Looks pretty good! I wrote a Sudoku Solver too. It is written in Java and it uses a backtracking algorithm with optimized guessing (It is very fast). It also tells if the sudoku has more than one solution. It is online and it is free. You’ll need the Java plugin installed in your browser. Envoy: http://dj3.electronicbox.net/sudoku/
You should take a look at Peter Norvig’s depressingly elegant python solver here
http://www.norvig.com/sudoku.html
Both look like fantastic solvers. Thanks for the links!
Hi there, you guys have got to check out a new grid game called SHENDOKU http://www.shendoku.com. I loved the idea of playing with 2 or more friends. They’ve got a wide range of games that will keep you entertained for hours and you dont have to do it alone. Let me know how tou get on..