Backtracking is a depth-first search
algorithm which explores one branch to a possible solution before moving on to another branch. It is arguably a type of brute force method that could be very practical as an effective implementation for solving Sudoku puzzles.
As shown in the above illustration gif, it brute forces by visiting the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid. It checks if there is any violation (row, column and box contraints), then advances to the next cell.
This algorithm is relatively simple, and a solution to any valid Sudoku problem is guaranteed. However, the solving time is relatively too slow compared to other algorithms that implements deductive
method.
Two major functionalities built is: isValid()
and solve()
, where the first one would call its helper functions to check any constraints violation, and the latter contains the backtracking algorithm that heavily depends on isValid()
return value.