My solver uses recursive backtracking to try valid numbers and revisit earlier choices when a route fails. The examples below also show how to solve cells with only one possible value, known as singles.
The solver visits empty cells from left to right, top to bottom. For each cell, it finds the numbers allowed by the current row, column and 3×3 box, then tries them one at a time.
After placing a candidate, it moves to the next empty cell. If a later cell has no valid candidates, it goes back and tries a different choice. This continues until it finds a solution or exhausts the choices.
Before guessing, you can look for cells with only one possible value. Check the numbers already present in the cell's row, column and 3×3 box. If only one candidate remains, you can fill it in without guessing.
Each number you fill in may leave another cell with a single candidate. Repeating this process can solve some puzzles or reduce the choices left for backtracking. The arrangement of the clues matters too: more filled cells do not necessarily mean a puzzle is easier.
Consider this puzzle:
2
3
4
1
5
6
8
8
2
3
6
5
1
9
1
6
9
8
7
2
3
4
3
1
7
9
4
2
5
4
5
8
1
2
6
9
7
9
2
6
5
8
3
1
5
1
2
8
4
2
9
3
5
9
2
3
7
1
4
8
6
This puzzle can be solved using singles alone, without backtracking.
For example, in the top-left box, the top empty cell must be 9. Here is how to eliminate the other candidates.
Each row, column and 3×3 box must contain every number from 1 to 9 exactly once. We can check these in any order; start with the box:
2
3
8
1
6
The box already contains 1, 2, 3, 6 and 8. Removing these leaves 4, 5, 7 and 9.
2
3
4
1
5
6
8
The row already contains 4 and 5, so the candidates are now 7 and 9.
7
8
6
2
The column contains 7, leaving only 9.
These are all the cells we checked:
2
3
4
1
5
6
8
8
2
3
6
5
1
9
1
6
9
8
7
2
3
4
3
1
7
9
4
2
5
4
5
8
1
2
6
9
7
9
2
6
5
8
3
1
5
1
2
8
4
2
9
3
5
9
2
3
7
1
4
8
6
Fill in 9, then repeat the same process for other single-candidate cells. For this puzzle, that fills the entire grid:
2
3
9
4
1
5
7
6
8
7
8
4
2
3
6
5
1
9
1
6
5
9
8
7
2
3
4
3
1
7
6
9
4
8
2
5
4
5
8
1
2
3
6
9
7
9
2
6
7
5
8
3
4
1
8
4
3
5
6
9
1
7
2
6
7
1
8
4
2
9
5
3
5
9
2
3
7
1
4
8
6
Not every Sudoku can be solved using singles alone. If several candidates remain in every empty cell, you need another technique. This solver uses backtracking.
For example, singles alone do not solve this puzzle:
8
1
2
9
5
9
7
2
6
4
2
6
5
7
8
1
6
9
5
2
5
9
4
1
My solver finds this solution using backtracking:
5
8
4
1
6
7
9
2
3
6
1
3
9
8
2
4
5
7
9
7
2
5
3
4
1
6
8
4
9
7
3
2
6
8
1
5
2
3
6
8
5
1
7
9
4
8
5
1
4
7
9
2
3
6
1
4
8
6
9
5
3
7
2
3
2
5
7
1
8
6
4
9
7
6
9
2
4
3
5
8
1