Sudoku Solver in Python
I was recently flying down to Cancún for my winter break, and I was doing one of the Sudoku puzzles they have in the back of the in-flight magazine. I got stuck at some point, and found myself wondering if there was an easy way to write a program to solve it for me. However, I didn't want it to just solve it automatically, I wanted it to guide me through the solution, so I only really needed to use it if I got stuck.
And thus, the Sudoku Solver was born.
It has an interface so that you can quickly enter in a sudoku puzzle, and either complete to see the solution, or step through move by move. It allows you to view the grid at any time, in both a small view
9 4 8 | _ 2 _ | 7 _ 5and a (considerably) more zoomed in view that displays possible values in the corners.
_ _ 1 | _ _ 4 | 8 _ 9 _ _ 6 | _ _ _ | 1 2 4 ------|-------|------- _ _ _ | _ _ 3 | _ 1 2 1 _ _ | _ _ _ | _ 7 8 8 7 2 | 5 _ _ | _ 4 3 ------|-------|------- _ 8 7 | _ _ _ | 2 9 6 6 _ _ | 9 _ _ | 3 8 1 _ 1 9 | _ 8 _ | 4 5 7
| | # 1 3| |1 6 # |3 6|
9 | 4 | 8 # | 2 | # 7 | | 5
| | # 6 | | # | |
------------------#-------------------#------------------
2 3|2 3| # 3 6|3 5| # |3 6|
| | 1 # | | 4 # 8 | | 9
5 7|5 | # 7 |6 7| # | |
------------------#-------------------#------------------
3 5|3 5| # 3 7|3 5|5 7 # | |
| | 6 # | | # 1 | 2 | 4
7 | | # 8 |7 9|8 9 # | |
##########################################################
4 5|5 6|4 5 # 4 6|4 6| # 5 6| |
| | # | | 3 # | 1 | 2
|9 | # 7 8|7 9| # 9 | |
------------------#-------------------#------------------
|3 5|3 4 # 2 4|4 6|2 6 # 5 6| |
1 | | # | | # | 7 | 8
|6 9|5 # 6 |9 |9 # 9 | |
------------------#-------------------#------------------
| | # |1 6|1 6 # 6 9| |
8 | 7 | 2 # 5 | | # | 4 | 3
| | # |9 |9 # | |
##########################################################
3 4| | # 1 3|1 3|1 5 # | |
| 8 | 7 # | | # 2 | 9 | 6
5 | | # 4 |4 5| # | |
------------------#-------------------#------------------
|2 5|4 5 # |4 5|2 5 # | |
6 | | # 9 | | # 3 | 8 | 1
| | # |7 |7 # | |
------------------#-------------------#------------------
2 3| | # 2 3| |2 6 # | |
| 1 | 9 # | 8 | # 4 | 5 | 7
| | # 6 | | # | |
It also allows you to input row-column pairs to see the possibilities for that spot. In the above example, (9,1) would output [2,3], the available options for that square.
On the hardest Sudoku in the world it takes ~25 seconds to solve.
800000000003600000070090200050007000000045700000100030001000068008500010090000400
On a more average Sudoku, yet still hard it takes under 1/10 of a second.
940020700001004009006000120000003010100000008070500000087000200600900300009080057
The (relatively rudimentary) algorithm it uses in searching for the next move is:
- Check every square to see if there's only number that's possible. If so, make the move, print it and end.
- For every number 1-9:
a. check if there's a row that only has one spot that it can fit. If so, make the move, print it and end.
b. check if there's a column that only has one spot that it can fit. If so, make the move, print it and end.
c. check if there's a box that only has one spot that it can fit. If so, make the move, print it and end. - Guess and see if it leads to a valid solution. If it does, then make the move, print it and end.
- There is no base case.
It works relatively well, and while it could be improved so there's less reliance on the guess and check one, it's usually fine. If the hardest puzzle can be solved in under half a minute, that's a good enough algorithm in my eyes.