SudokuSudoku Buster LogoBuster

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.

Status
No puzzle loaded.
Solution Time # Moves Approx. Time to Animate
-- -- --
Legend
  • 1
    A fixed (starting) cell.
  • 2
    A cell that could contain only one value (after any previous guesses), and was assigned that value.
  • 3
    A cell with a value that was guessed after all possible cell assignments were made.

How does Sudoku Buster solve the puzzles?

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 board is full and thus solved (yay!).
  • The board is invalid (i.e., there is a cell with zero possible values).

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.

Some Technical Notes

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!

What if I have more questions?

Please feel free to contact me.