Back in November of 2008, a conversation at a family gathering inspired me to write a (Flash) program that could solve Sudoku puzzles. A relative had been trying to write a solver himself, and it seemed like a nice challenge. The resulting Flash movie was on this blog for a couple of years, but it had two issues. It was Flash, and it would fail to solve some more difficult puzzles.
During the Christmas holidays this year, I had some time on my hands, and decided to give it a second try. I used Javascript this time, and instead of trying to find the solution using a set of rules, I wanted to use some type of brute force.
The algorithm
I could have looked up existing algorithms, and implemented them. But then it wouldn’t have been a puzzle. The idea was to create my own algorithm, and see how well it did. I’m using a timer to slow down the solving, and update the screen so you can see what the script is doing. Here’s what it does for each “step”.
- Find all empty squares
- If there are none, the puzzle is solved
- For each empty position, determine the number of possible values (a number between 0 and 9)
- Find the position with the lowest number of possible values
- If there are zero possibilities, the current solution is wrong, return to the last known correct state
- If there’s just one possibility, record that value as being correct
For nearly all puzzles except very easy ones, there will soon only be positions that have multiple possible values. This is when I switch to a second “mode”, where each step is slightly different.
- Like before, find the position with the lowest number of possible values
- Randomly fill in one of the possible values
- Since we’re now guessing, stop recording values as correct
- At some point, there’s either a square with zero possibilities, or the puzzle is solved
Since “mode 2” is essentially “brute force with educated guesses”, this is where solving slows down considerably. But, it’ll never give up, and theoretically it should be able to solve all puzzles. Might take century or two, but still…
Testing
While developing the script, I’d been using a level 4 sudoku from a puzzle book I had lying around. Not very challenging. I obviously needed to see how it would do against harder to solve puzzles.
My first test was to set the Sudoku app on my phone to difficulty level “extreme”, and copy the resulting puzzle into my solver. It solved it within seconds. Promising.
I then looked for even more difficult puzzles, and found this page, which lists four extremely hard to solve sudokus. These proved to be a proper challenge. I could see the solver resorting to “mode 2” quickly, and one even took 5 minutes to complete. But eventually it did.
This convinced me that my solver can solve any “human-solvable” sudoku puzzle. It’s not optimized for speed at all. Maybe I should try to write the same algorithm in a faster language to see how fast it can be. For now, I’m quite happy with it as it is.
The source code is available on Github. Please feel free to contribute. Thanks to Alex Goller for improving usability on mobile devices.
