Skip to main content.

Solving a Sudoku with Backtracking

All of the methods mentioned so far work better if more numbers are given. But should you do if you are stuck?

The answer is easy: trial and error, or as a computer scientist would say: Backtracking.

When writing a computer program that solves Sudokus, like YasSS (Yet another (Simple|Stupid) Sudoku Solver), backtracking can be very useful.

It works this way: Find a cell where you don't know what values to fill in. Try the first possible value (and remember that you are not sure about it), then solve the resulting Sudoku. If you find a solution, you're happy. If not, try the next possibility.

It's rather frustrating to do this by hand since you have to revert to an earlier state rather frequently, abandoning all previous achievements.

But a computer can't become enervated, and find solutions pretty fast.

An up-to-date PC can solve several very difficult Sudokus in a second, and many more average difficult ones.

top