The brute-force Backtracking algorithm is the major solving algorithm in this Sudoku solver. The solver works alongside a supporting algorithm that helps remove singles from the graph.
The backtracking algorithm for solving Sudoku puzzles employs a trial and error strategy in which it fills up every single blank cell in a systematic order (left to right, top to bottom). First, the algorithm chooses the logical candidate number for the current empty cell. If the chosen number complies with all the Sudoku rules, the algorithm moves to the next cell recursively and does the same. If the chosen number does not comply with the Sudoku rules or no number can be placed in the current cell, then it proceeds with a process known as backtracking. Here, it goes back to the previous cell and changes the previously selected number. The process continues until all the cells are filled with the correct numbers or until it's established that no solution exists for the given puzzle.
Singles removal is one of the effective strategies used to optimize the backtracking algorithm while solving the Sudoku puzzles.
Before filling a number into a cell, the algorithm first checks all the filled numbers in the current row, column, and 3x3 grid. If a single possible candidate number is found for the current empty cell, it is filled directly without guessing.
This process of filling definite single candidates is executed before the backtracking starts to reduce the search size and speed up the algorithm.
The singles removal optimization pre-processes the Sudoku grid by eliminating all the known possibilities before the backtracking algorithm is employed. This significantly reduces the number of possibilities and computations to be checked, leading to improved performance and faster solutions.
In a nutshell, the more filled cells in the starting puzzle, the less work for the backtracking algorithm.
Consider the following graph:
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 Sudoku puzzle can be solved completely without the Backtracking algorithm. This is because there are squares where there is only one possible answer possible. For example, in the top-left grid, the top empty cell has to be 9 because no other possibilities exist.
Every row, column, and 3x3 regions must have every number 1 through 9 inclusive. With this, we can work out the only possible value by examining the row, column and the square of the cell in any order, however, we will start with the region first:
2
3
8
1
6
We can remove the numbers present in the current region of the cell and are left with numbers 4, 5, 7 and 9 after removing 1, 2, 3, 6 and 8 from the possible set.
2
3
4
1
5
6
8
We can now look at the row of the cell and remove numbers 4 and 5 from our list of numbers. This leaves us with the possibilities: 7 and 9.
7
8
6
2
By looking at the column of the cell, we can remove the 7 from our list of numbers, leaving us with only 9.
Here's a representation of all the cells we checked to get here:
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
Since 9 is the only number, we can be certain that only 9 should go into the cell so we write 9 into the cell. We can keep iterating this process until all the squares are filled in:
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
However, this doesn’t guarantee that you will find a solution to every possible Sudoku using this method. This is where you have to use backtracking.
The following example cannot be solved using the previous method but can be solved using Backtracking:
8
1
2
9
5
9
7
2
6
4
2
6
5
7
8
1
6
9
5
2
5
9
4
1
This is the solution to the above using my Sudoku solver:
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