Here I present Sudoku Buster, which is a Sudoku puzzle solver that I wrote for fun. It started out as a klunky ol' DOS program. Then I converted it to a Windows application and published it here. The latest incarnation is a web-based application. Puzzles are solved and animated right on this web page. No download required!
Click the "Load" button to load a puzzle from the database, and then press the "Solve" button to animate the solution. Note that I have a limited number of puzzles stored in the database right now. The ability to enter and (possibly) save puzzles will be coming in a future update.
Scroll down to read more about Sudoku Buster, including how it solves the puzzles.
Solution Time | # Moves | Approx. Time to Animate |
---|---|---|
-- | -- | -- |
Writing an algorithm to solve a puzzle or play a game often involves logic that is completely different from that which a human would use. When I solve Sudoku puzzles myself, I never guess, but guessing is a major factor in Sudoku Buster's algorithm.
First, Sudoku Buster assigns cells that are forced (i.e., they can contain only one value). If the puzzle is not solved after doing this, it saves the current board position, picks a cell, and guesses that the cell contains one of its two or more possible values. It then repeats the process of making forced assignments and guessing. Note that it is common in more difficult puzzles to reach several levels of guesses.
Eventually, Sudoku Buster will encounter one of the following situations:
The second situation indicates that one of the previous guesses was incorrect. Sudoku Buster will then revert the board to the state prior to the previous guess and pick another value for that cell. If there are no more possible values, it indicates that an earlier guess was incorrect, and Sudoku Buster will back up again and revisit that guess.
Computer scientists call this a depth-first tree search.
The original Sudoku Buster was written in C++. To make implementing the web-based solver easier, I rewrote it in Python, so it is likely a bit slower. But I also added an interesting new feature. When guessing, the original solver would pick the cell with the fewest possible values in left to right and top to bottom order. To combat puzzles that are specifically designed to slow down such algorithms (see Wikipedia, which refers to this algorithm as "Backtracking"), the new solver will pick the cell with the fewest number of empty cells in its row, column, and 3x3 square. This reduced the solution time for the anti-backtracking puzzle shown on that linked Wikipedia page by a factor of nine!
Please feel free to contact me.