You can check out the slides here (direct PDF link):
What is Backtracking?
Backtracking is a general approach, i.e. a variant of a depth-first search algorithm, suited for solving constraint satisfaction problems.
???? Idea: Backtracking incrementally validates candidates, tests the solutions, and backtracks from a candidate value if it determines that the final solution is not valid while containing the candidate value.
What is the Purpose of Backtracking?
Backtracking is commonly used in solving crosswords, verbal arithmetic, and similar puzzles.
It is the most appropriate method for parsing, i.e. analyzing a string of symbols, solving a knapsack problem, and other combinatorial optimization problems.
Backtracking is also the basis for some logic programming languages, such as Prolog.
How Does Backtracking Work?
A backtracking-based algorithm, in our case implemented as a Sudoku game, works by starting in the top left corner and searching for the empty positions in the puzzle by going from left to right.
When the algorithm finds an empty position, it will rotate a series of candidate values, ranging from 0 to 9, and check if there is a value that satisfies the basic rules of Sudoku: uniqueness in its row, its column, and its group.
- If the value matches the rules, the algorithm will recursively proceed to the next free position, retry the same series of values, and repeat the same steps until it reaches the end.
- If no value from the series matches the rules, the algorithm will backtrack to the previously filled position, try the next rule-matching value from the series, and resume searching for the next free position, recursively repeating the process.
Once the last free position has been filled with the rule-matching value, the algorithm will yield the solution and end.
If the algorithm encounters a free position that cannot be filled with a rule-matching value, it will eventually exhaust the series of values for the first free position and there will be no solution found, i.e. the puzzle will be left unsolved.
Backtracking functionality is achieved by recursively checking, i.e. descending lower in the search space by using the depth-first search algorithm.
The algorithm is implemented implicitly and the graph vertex is conceptually represented by the current state of the puzzle.
All previous states along the current search path are preserved in their corresponding function contexts.
Contrary to other graph algorithms, this algorithm did not require us to explicitly generate the search space, usually represented by a graph, because it would have enormous requirements in both terms of space (memory) and time (duration). Furthermore, most parts of the generated graph would remain unexplored.
What are Backtracking Properties?
One of the significant properties of the backtracking approach is that the solution discovery is guaranteed for valid puzzles, i.e. the ones that have a solution.
The second important property is the simplicity and flexibility of approach implementation, which makes it a good general approach for testing the existence of a solution.
On the downside, depending on a specific problem, solution finding by applying a backtracking approach can be inferior to stochastic search or other optimization methods.
How is Backtracking Implemented?
An example of our backtracking algorithm is implemented in a form of a Sudoku solution finder.
The program is very simple, self-contained, and has only three functions: backtrack_sudoku(), next_position(), and test_candidate().
The main function, backtrack_sudoku() takes two parameters:
- the
puzzleparameter as an initialized 2D list object (a list of lists), and - the optional
print_stepsparameter, which enables us to see the steps which our algorithm took before reaching the final solution (if there is one). It defaults toFalsebut can be activated if we call the main function in the following way:backtrack_sudoku(puzzle, True).
The utility function, next_position() takes only one parameter, puzzle, representing our puzzle, and calculating the next free position on the puzzle board.
If we imagine traversing the puzzle board row-by-row, i.e. by starting on the top-left position, scanning the entire row, and then progressing to the leftmost position in the next row, the first empty position not containing a value is considered to be free.
The function test_candidate() takes three parameters:
puzzle, representing our puzzle, then- the
candidate_value, and - a
position.
The function tests different candidate values, looping from 0 to 9, and tries to find the candidate value that is unique in the current row, column, and its group.
For a better understanding of the algorithm and its implementation, each step is precisely described in the code below.
The entire algorithm listing follows:
dimension = 3
iterations = 0
# An anonymous placeholder object.
class Object:
def __init__(self):
self.row = None
self.column = None
pass
def next_position(puzzle):
# Loops through the search space by rows and then by columns.
for i in range(len(puzzle)):
for j in range(len(puzzle[0])):
if puzzle[i][j] is None:
position = Object()
position.row = i
position.column = j
return position
return None
def test_candidate(puzzle, candidate_value, position):
# Searches the row for duplicate values of the 'candidate_value'.
for i in range(len(puzzle[0])):
# Prevents detecting the 'candidate_value' as a duplicate.
if puzzle[position.row][i] == candidate_value and position.column != i:
return False
# Searches the column for duplicate values of the 'candidate_value'.
for i in range(len(puzzle)):
# Prevents detecting the 'candidate_value' as a duplicate.
if puzzle[i][position.column] == candidate_value and position.row != i:
return False
# Forms and searches the groups for duplicate values of the 'candidate_value'.
group = Object()
# Determines the group by integer division of the position coordinates.
group.column = position.column // dimension
group.row = position.row // dimension
# Performs the group search inside a group, by rows and columns.
for i in range(group.row * dimension, (group.row + 1) * dimension):
for j in range(group.column * dimension, (group.column + 1) * dimension):
if puzzle[i][j] == candidate_value and (i, j) != position:
return False
return True
def backtrack_sudoku(puzzle, print_steps=False):
# Counts the total number of iterations until the solution is found.
global iterations
iterations += 1
# Finds the next free position.
position = next_position(puzzle)
if not position:
return True
# Tries out every possible value at the given (free) position.
for i in range(1, dimension * dimension + 1):
# Tests if the value matches the general rules,
# i.e. value uniqueness in the row, column and group.
if test_candidate(puzzle, i, position):
puzzle[position.row][position.column] = i
if print_steps:
print(f'\n\n*** Iteration: {iterations} ***\n')
print_puzzle(puzzle)
# Proceeds with the search by going one level deeper in the
# search tree, effectively doing the depth-first search algorithm.
if backtrack_sudoku(puzzle, print_steps):
return True
# Marks the position as empty if none of the values match the rules.
puzzle[position.row][position.column] = None
return False
def print_puzzle(puzzle):
for i in range(len(puzzle)):
if i % dimension == 0 and i != 0:
print('')
for j in range(len(puzzle[0])):
if j % dimension == 0 and j != 0:
print(' ', end='')
print(str(puzzle[i][j] or '_'), end=' ')
if j % (dimension * dimension - 1) == 0 and j != 0:
print('')
Now that we have prepared everything, we can test backtrack_sudoku() and see how it works.
We have three readily available puzzles, arranged by their difficulty, as easy, medium, and hard.
easy = [
[None, None, None, None, None, None, None, None, None],
[None, 7, 6, None, None, None, 8, 4, None],
[1, 8, None, None, None, 4, None, 7, 5],
[None, None, None, 2, 5, None, None, None, 6],
[None, None, 1, 4, None, 7, 3, None, None],
[6, None, None, None, 3, 8, None, None, None],
[3, 5, None, None, None, 9, None, 8, 1],
[None, 1, 4, None, None, None, 2, 5, None],
[None, None, None, None, None, None, None, None, None]
]
medium = [
[None, None, None, 4, None, None, None, 8, None],
[None, 4, None, None, None, 3, None, None, None],
[8, None, None, None, None, None, 1, 3, None],
[None, None, None, 6, None, None, None, None, None],
[None, None, 8, 2, 1, None, None, None, 7],
[5, None, None, None, None, 4, None, None, None],
[7, None, None, 3, None, None, 5, None, 9],
[9, None, None, None, 8, None, 2, None, None],
[None, None, 6, None, 5, None, 3, None, None]
]
hard = [
[None, 2, None, None, None, None, None, 9, None],
[None, None, None, None, 7, 4, 8, None, None],
[4, 3, None, None, None, 1, None, None, None],
[5, None, 6, 7, None, None, None, None, None],
[None, None, None, None, 2, None, None, None, None],
[None, None, None, None, None, 9, None, None, 3],
[None, None, 3, None, None, None, None, 8, None],
[None, 1, None, 9, 5, None, 6, None, None],
[None, 5, None, None, None, None, None, 7, None]
]
Here is the part of the code that runs the algorithm, shows the puzzle we chose to solve, and the final solution, depending on if it exists:
solve_for_puzzle = easy
print_puzzle(solve_for_puzzle)
print('\nLooking for the solution...\n')
backtrack_sudoku(solve_for_puzzle)
print('\n *** THE SOLUTION ***')
print(f'Iterations required: {iterations}\n')
print_puzzle(solve_for_puzzle)
We have the following output for our easy puzzle:
_ _ _ _ _ _ _ _ _ _ 7 6 _ _ _ 8 4 _ 1 8 _ _ _ 4 _ 7 5 _ _ _ 2 5 _ _ _ 6 _ _ 1 4 _ 7 3 _ _ 6 _ _ _ 3 8 _ _ _ 3 5 _ _ _ 9 _ 8 1 _ 1 4 _ _ _ 2 5 _ _ _ _ _ _ _ _ _ _ Looking for the solution... *** THE SOLUTION *** Iterations required: 21644 9 4 5 8 7 3 1 6 2 2 7 6 1 9 5 8 4 3 1 8 3 6 2 4 9 7 5 4 3 8 2 5 1 7 9 6 5 9 1 4 6 7 3 2 8 6 2 7 9 3 8 5 1 4 3 5 2 7 4 9 6 8 1 7 1 4 3 8 6 2 5 9 8 6 9 5 1 2 4 3 7
If we rerun the algorithm, we have the following output for our medium puzzle:
solve_for_puzzle = medium _ _ _ 4 _ _ _ 8 _ _ 4 _ _ _ 3 _ _ _ 8 _ _ _ _ _ 1 3 _ _ _ _ 6 _ _ _ _ _ _ _ 8 2 1 _ _ _ 7 5 _ _ _ _ 4 _ _ _ 7 _ _ 3 _ _ 5 _ 9 9 _ _ _ 8 _ 2 _ _ _ _ 6 _ 5 _ 3 _ _ Looking for the solution... *** THE SOLUTION *** Iterations required: 261512 6 3 9 4 2 1 7 8 5 1 4 5 8 7 3 6 9 2 8 2 7 5 6 9 1 3 4 2 7 4 6 3 8 9 5 1 3 9 8 2 1 5 4 6 7 5 6 1 7 9 4 8 2 3 7 8 2 3 4 6 5 1 9 9 5 3 1 8 7 2 4 6 4 1 6 9 5 2 3 7 8
On our last rerun of the algorithm, we have the following output for our hard puzzle:
solve_for_puzzle = hard _ 2 _ _ _ _ _ 9 _ _ _ _ _ 7 4 8 _ _ 4 3 _ _ _ 1 _ _ _ 5 _ 6 7 _ _ _ _ _ _ _ _ _ 2 _ _ _ _ _ _ _ _ _ 9 _ _ 3 _ _ 3 _ _ _ _ 8 _ _ 1 _ 9 5 _ 6 _ _ _ 5 _ _ _ _ _ 7 _ Looking for the solution... *** THE SOLUTION *** Iterations required: 321814 7 2 1 3 8 5 4 9 6 9 6 5 2 7 4 8 3 1 4 3 8 6 9 1 2 5 7 5 4 6 7 3 8 9 1 2 3 7 9 1 2 6 5 4 8 1 8 2 5 4 9 7 6 3 2 9 3 4 6 7 1 8 5 8 1 7 9 5 3 6 2 4 6 5 4 8 1 2 3 7 9
Efficiency analysis
After comparing the number of iterations the algorithm took to find the solution for different puzzle difficulties, we noticed a stunning increase of 1100% in the number of iterations between easy and medium difficulty puzzles.
Furthermore, we noticed an additional 23% increase in the number of iterations between medium and hard difficulty puzzles.
Based on our results, we can conclude that, depending on the specific problem, the backtracking approach may be appropriate if it manages to intelligently reduce the search space and solve the problem in finite time.
However, its efficiency can vary greatly with the problem complexity and the backtracking approach is not applicable in just every case.
Conclusion
In this article, we learned about backtracking in search algorithms.
- First, we explained what backtracking in search algorithms is.
- Second, we took a look at what are its common purposes and applications.
- Third, we went through an explanation of how the approach works.
- Fourth, we examined the main properties of this approach.
- Fifth, we went through an example implementation of backtracking in Sudoku-solving algorithm, which is based on simple three functions,
backtrack_sudoku(),next_position(), andtest_candidate(). - We also tested the algorithm by calling its main function,
backtrack_sudoku(), and analyzed its steps of execution for three puzzles of different difficulties. - Sixth, we analyzed the algorithm efficiency.
To conclude, the algorithm efficiency is much better than its main alternative in the form of a pure brute-force method, based on trial-and-error. However, the algorithm efficiency varies with the structure of a puzzle, i.e. the composition of the problem.
Depending on the specific problem, the backtracking approach may be found appropriate if it manages to consistently reduce the search space and solve the problem in a finite time.
However, it is not generally considered the best approach for every problem of this kind. In such cases, if it proves to be practically inefficient, an alternative approach should be taken into consideration.