Jo has really been into Sudoku the past few months. Being the nerd that I am, I spent the past few weeks coding up a Sudoku solver that you can check out at http://www.ben61a.com/sudokusolver/. (If you’re not familiar with the game, read about it on its Wikipedia entry.) It has been, and continues to be, an interesting project because solving Sudoku turns out to be relatively complicated.
The first work item I completed was a fast solver. The solver first translates a Sudoku into an exact cover problem. It then uses the Dancing Links technique, originally suggested by Donald Knuth in this paper, to efficiently find all solutions to the exact cover problem. In the case of a well-formed Sudoku, there is only one solution. That exact cover solution is then translated back into a Sudoku solution grid.
Next, I used this Dancing Links solver to create a puzzle generator. This simple generator starts with a blank grid and adds a random digit to a random cell over and over. After each addition, I use the fast solver to see if there is only one solution; if so, then we have a new Sudoku. If there are no solutions, we have to backtrack because the last digit added messed up the puzzle. I used my puzzle generator to create 50,000 puzzles (it took about 8 hours or so because of the massive number of fast solves that are done).
Unfortunately, the nature of the algorithm used by the fast solver suffers two problems:
- It can’t give any clues as to how to solve a Sudoku in a stepwise, human-logic-based manner
- There is no way to judge difficulty aside from counting the number of hints given in the Sudoku
To remedy both problems, I wrote a new solver that uses human-logic-based solving techniques. Whereas the fast solver can solve any well-formed Sudoku, my new logic-based solver can only solve around 98% of puzzles since some require more advanced logic techniques that I just haven’t coded yet. These are the major solving techniques I have coded so far:
- Naked Pairs
- Locked Candidates
- Naked Triples
- Naked Quads
- Hidden Pairs
Based on the number of types of techniques a puzzle requires to be solved, I was now able to classify puzzles in an (admittedly) subjective manner:
- Easy if the only technique required is Singles
- Medium if the only techniques required are Singles, Naked Pairs, or Locked Candidates (and it’s not an Easy puzzle)
- Hard if it’s not an Easy or Medium puzzle
- Evil if my logic-based solver cannot solve it using any of its techniques
Surprisingly, 47739 of the 50000 generated puzzles (95.5%) were classified as Easy (only required Singles). That’s crazy! As for the rest, 755 were Medium, 493 were Hard, and 1013 were Evil.
Finally, I put a user interface on top of the logic-based solver and put it online as a Java applet, linked above. It’s really just a first blush at a UI, so I know there can be much improvement.
Anyway, I’d love to hear your impressions and feature ideas, so leave a comment!
- Because of the sheer size of storing 50000 puzzles even just as strings, I made a decision to only include 250 Easy, 250 Medium, and 250 Hard puzzles in the applet. This means that when you click “Easy,” you will only be given a puzzle from a pool of 250 puzzles.
- I’m thinking about porting my poker and Sudoku applets to Flash since no one uses Java =p. It looks like I’d need to buy some Adobe software to do that though (not to mention learning Flash), but it sounds fun. Look for that in the future.