is a versatile technique for exploring the solution space of various types of data science problems and incrementally constructing candidate solutions – a bit like navigating a maze. In this article, we will briefly go over the concept of backtracking before diving into a couple of intuitive, hands-on examples coded in Python.
Note: All example code snippets in the following sections have been created by the author of this article.
Contents
Conceptual Overview
At a high level, the backtracking technique involves a step-by-step exploration of the solution space of a computational problem (usually a problem that can be framed as one of constraint satisfaction or combinatorial optimization). At each step in the exploration, we proceed along different paths, checking that the problem constraints are satisfied as we go along.
If we hit upon a valid solution during our exploration, we make a note of it. At this point, we can end the search if our problem only requires us to find one valid solution. If the problem calls for finding multiple (or all) possible solutions, we can continue to explore extensions of the previously discovered solution.
However, if at any point the problem constraints are violated, we backtrack; this means going back to the last point in our search where a partial solution had been constructed (and where valid solutions still seemed possible), and continuing our search along a different path from there. This forward-and-backward process of exploration can be continued as needed until the entire solution space is explored and all valid solutions are explored.
Hands-On Examples
Solving a Sudoku
A Sudoku puzzle is a classic example of a constraint satisfaction problem with practical applications in diverse fields ranging from operations research to cryptography. The standard version of the puzzle consists of a 9-by-9 grid, made of nine non-overlapping 3-by-3 sub-grids (or blocks). In the starting configuration of the puzzle, some of the 81 cells in the grid are prefilled with digits ranging from 1 to 9. To complete the puzzle, the remaining cells must be filled with digits from 1 to 9 while adhering to the following constraints: no row, column, or 3-by-3 block may contain a duplicate digit.
The Python code below shows how to implement a Sudoku solver using backtracking, along with a convenience function for pretty-printing the grid. Note that the solver expects empty cells to be denoted (or initialized) with zeros.
from copy import deepcopy
def is_valid(board, row, col, num):
# Check if num is not in the current row or column
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
# Check if num is not in the 3-by-3 block
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
def find_empty_cell(board):
# Find the next empty cell (denoted by 0)
# Return (row, col) or None if puzzle is complete
for row in range(9):
for col in range(9):
if board[row][col] == 0:
return row, col
return None
def solve_board(board):
empty = find_empty_cell(board)
if not empty:
return True # Solved
row, col = empty
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_board(board):
return True
board[row][col] = 0 # Backtrack
return False
def solve_sudoku(start_state):
board_copy = deepcopy(start_state) # Avoid overwriting original puzzle
if solve_board(board_copy):
return board_copy
else:
raise ValueError("No solution exists for the given Sudoku puzzle")
def print_board(board):
for i, row in enumerate(board):
if i > 0 and i % 3 == 0:
print("-" * 21)
for j, num in enumerate(row):
if j > 0 and j % 3 == 0:
print("|", end=" ")
print(num if num != 0 else ".", end=" ")
print()Now, suppose we input a Sudoku puzzle, initializing empty cells with zeros, and run the solver as follows:
puzzle = [
[5, 0, 0, 0, 3, 0, 0, 0, 7],
[0, 0, 0, 4, 2, 7, 0, 0, 0],
[0, 2, 0, 0, 6, 0, 0, 4, 0],
[0, 1, 0, 0, 9, 0, 0, 2, 0],
[0, 7, 0, 0, 0, 0, 0, 5, 0],
[4, 0, 6, 0, 0, 0, 7, 0, 1],
[0, 4, 2, 0, 7, 0, 6, 1, 0],
[0, 0, 0, 0, 4, 0, 0, 0, 0],
[7, 0, 0, 9, 5, 6, 0, 0, 2],
]
solution = solve_sudoku(puzzle)
print_board(solution)The solver will produce the following solution within milliseconds:
5 6 4 | 1 3 9 | 2 8 7
1 9 8 | 4 2 7 | 5 6 3
3 2 7 | 8 6 5 | 1 4 9
---------------------
8 1 5 | 7 9 4 | 3 2 6
2 7 9 | 6 1 3 | 8 5 4
4 3 6 | 5 8 2 | 7 9 1
---------------------
9 4 2 | 3 7 8 | 6 1 5
6 5 3 | 2 4 1 | 9 7 8
7 8 1 | 9 5 6 | 4 3 2Cracking a Math Olympiad Problem
Math Olympiads are competitions for pre-university students and consist of tough math problems that must be solved under timed conditions without the use of calculators. Since systematically exploring the full solution space for such problems is typically not feasible, successful solution approaches tend to rely on analytical reasoning and mathematical ingenuity, exploiting explicit and implicit constraints gleaned from the problem statement to streamline the search of the solution space. Some problems have to do with constraint satisfaction and combinatorial optimization, which we also come across in data science problems in industry (e.g., checking whether a path to a given destination exists, finding all possible paths to a destination, finding the shortest path to a destination). Thus, even if a clever mathematical solution approach exists for a specific Olympiad problem, it can be instructive to investigate other generalizable approaches (like backtracking) that exploit the power of today’s computers and can be used to solve a broad range of similar problems in practice.
For example, consider the following problem that appeared in Round 1 of the British Mathematical Olympiad in November 2018: “A list of five two-digit positive integers is written in increasing order on a blackboard. Each of the five integers is a multiple of 3, and each digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 appears exactly once on the blackboard. In how many ways can this be done? Note that a two-digit number cannot begin with the digit 0.”
As it happens, the solution to the above problem is 288. The video below explains a solution approach that cleverly exploits some key explicit and implicit features of the specific problem statement (e.g., the solution must be presented as an ordered list, and a number is a multiple of 3 if the sum of its digits is also a multiple of 3).
The Python code below shows how backtracking can be used to solve the problem:
def is_valid_combination(numbers):
# Checks if each digit from 0-9 appears exactly once in a list of numbers
digits = set()
for number in numbers:
digits.update(str(number))
return len(digits) == 10
def find_combinations():
multiples_of_3 = [i for i in range(12, 100)
if i % 3 == 0 and '0' not in str(i)[0]]
valid_combinations = []
def backtrack(start, path):
if len(path) == 5:
if is_valid_combination(path):
valid_combinations.append(tuple(path))
return
for i in range(start, len(multiples_of_3)):
backtrack(i + 1, path + [multiples_of_3[i]])
backtrack(0, [])
return valid_combinations
print(f"Solution: {len(find_combinations())} ways")The function is_valid_combination() specifies the key constraint that must hold for each valid 5-number list discovered during the exploration of the search space. The list multiples_of_3 features the candidate numbers that may appear in a valid 5-number list. The function find_combinations() applies backtracking to efficiently try out all unique 5-number combinations from multiples_of_3.
The function is_valid_combination() and the list comprehension used to generate multiples_of_3 can be modified to solve a broad range of similar problems.
Beyond Backtracking
As we have seen, backtracking is a simple yet powerful technique for solving different types of constraint satisfaction and combinatorial optimization problems. Yet, other techniques such as depth-first search (DFS) and dynamic programming (DP) also exist and may look similar on the surface – so when does it make sense to use backtracking instead of these other techniques?
Backtracking can be thought of as a more strategic form of DFS, in which constraint checking is a core feature of each decision step, and invalid paths can be abandoned early. Meanwhile, DP may be used for problems that exhibit two properties: overlapping subproblems and an optimal substructure. A problem has overlapping subproblems if the same subproblems need to be solved multiple times while solving the larger problem; storing and reusing the results of the recurring subproblems (e.g., using memoization) is a key feature of DP. Furthermore, a problem has an optimal substructure if an optimal solution to the problem can be constructed by building on optimal solutions to its subproblems.
Now, consider the N-Queens Problem, which looks at how to place N queens on an N-by-N chessboard, such that no two queens can attack each other; this is a classic problem that has applications in several real-world scenarios where finding solutions without conflicts is crucial (e.g., resource allocation, scheduling, circuit design, and path planning for robots). The N-Queens problem does not inherently exhibit overlapping subproblems or an optimal substructure, since subproblems may not necessarily need to be solved repeatedly to solve the overall problem, and the placement of queens in one part of the board does not guarantee an optimal placement for the entire board. The inherent complexity of the N-Queens Problem thus makes it less suitable for exploiting the strengths of DP, while backtracking aligns more naturally with the problem’s structure.