Backtracking is a powerful technique used to solve certain types of problems. It is a type of recursion and can be used to solve complex problems by exploring different paths from a given starting point. In this article, we will discuss the basics of backtracking and how it can be used to solve data structures and algorithms problems with Python.
What is Backtracking?
Backtracking is a type of algorithm that is used to find all solutions to a given problem. It involves searching through all possible solutions and then discarding those that do not meet the given criteria. It is a form of trial and error, and is often used when an exact solution is not known. Backtracking algorithms can be used to find solutions to problems such as the traveling salesman problem, the knapsack problem, and the 8-queens problem.
Backtracking algorithms start by exploring a possible solution and then backtracking or undoing the steps if the solution does not lead to a satisfactory outcome. This process is repeated until a solution is found or all possible solutions have been explored. The backtracking algorithm can be thought of as a tree with multiple branches that are explored.
Python Code for Backtracking
Backtracking can be implemented in Python using the following code:
def backtrack(solution, partial):
if is_solution(partial):
solution.append(partial)
else:
for c in generate_candidates(partial):
partial.append(c)
backtrack(solution, partial)
partial.pop()
The code begins by defining a function “backtrack” that takes two parameters: “solution” and “partial”. The “solution” parameter will contain the list of all solutions that are found by the algorithm. The “partial” parameter will contain a partial solution.
The code then checks if the partial solution is a valid solution. If it is, then the partial solution is added to the list of solutions. If not, the code generates possible candidates for the partial solution and adds them to the list. The code then recursively calls itself with the new partial solution. This process is repeated until all possible solutions have been explored.
Applications of Backtracking
Backtracking algorithms can be used to solve a variety of problems. One of the most common applications of backtracking is in the field of combinatorial optimization. It can be used to solve problems such as the traveling salesman problem, the knapsack problem, and the 8-queens problem.
Backtracking is also used in constraint satisfaction problems. These are problems where a set of variables must be assigned values such that certain constraints are satisfied. Examples of constraint satisfaction problems include Sudoku, scheduling, and map coloring problems.
Backtracking can also be used for graph problems. It can be used to find a Hamiltonian cycle in a graph, which is a path that visits each vertex exactly once. It can also be used to find a minimum spanning tree, which is a tree that connects all the vertices in a graph with the minimum possible total weight.
Backtracking can also be used to solve problems related to game theory, such as finding a Nash equilibrium in a two-player game. It can also be used for pattern matching, such as finding a substring in a string.
Conclusion
Backtracking is a powerful technique used to solve certain types of problems. It is a type of recursion and can be used to solve complex problems by exploring different paths from a given starting point. It is used to solve problems such as the traveling salesman problem, the knapsack problem, and the 8-queens problem. It can also be used for graph problems, constraint satisfaction problems, game theory, and pattern matching.
Exercises
Write a program to solve the 8-queens problem using backtracking.
def is_valid_position(board, row, col):
# Check if there is a queen in the same column
for i in range(row):
if board[i][col] == 1:
return False
# Check diagonal
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
i, j = row - 1, col + 1
while i >= 0 and j < len(board):
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_queens(board, row):
# Base case
if row == len(board):
return True
# Try all columns for current row
for col in range(len(board)):
if is_valid_position(board, row, col):
board[row][col] = 1
if solve_queens(board, row+1):
return True
board[row][col] = 0
return False
Write a program to solve the knapsack problem using backtracking.
def knapsack(items, max_weight):
knapsack_items = []
knapsack_value = 0
def backtrack(i, weight, value):
nonlocal knapsack_items, knapsack_value
if i == len(items) or weight == max_weight:
if value > knapsack_value:
knapsack_items = knapsack_items[:i]
knapsack_value = value
return
# Don't take the item
backtrack(i + 1, weight, value)
# Take the item if there is room
if weight + items[i][1] <= max_weight:
knapsack_items.append(items[i])
backtrack(i + 1, weight + items[i][1], value + items[i][0])
knapsack_items.pop()
backtrack(0, 0, 0)
return knapsack_items, knapsack_value
Write a program to solve the traveling salesman problem using backtracking.
def tsp(graph):
# Set up initial state
n = len(graph)
visited = [False] * n
visited[0] = True
current_path = [0]
best_path = None
best_cost = float('inf')
def backtrack(i, visited, current_path, current_cost):
nonlocal best_path, best_cost
# Base case, all cities visited
if all(visited):
if current_cost < best_cost:
best_cost = current_cost
best_path = current_path[:]
return
# Try all cities that have not yet been visited
for j in range(n):
if not visited[j]:
visited[j] = True
current_path.append(j)
backtrack(j, visited, current_path, current_cost + graph[i][j])
visited[j] = False
current_path.pop()
backtrack(0, visited, current_path, 0)
return best_path, best_cost
Write a program to solve a Sudoku puzzle using backtracking.
def solve_sudoku(board):
def is_valid_position(board, row, col):
# Check if there is a duplicate in the same row
for i in range(9):
if board[row][i] == board[row][col] and i != col:
return False
# Check if there is a duplicate in the same column
for i in range(9):
if board[i][col] == board[row][col] and i != row:
return False
# Check 3x3 grid
row_start = (row // 3) * 3
col_start = (col // 3) * 3
for i in range(row_start, row_start + 3):
for j in range(col_start, col_start + 3):
if board[i][j] == board[row][col] and (i,j) != (row,col):
return False
return True
def backtrack(board, row, col):
if row == 9:
return True
# Next cell
if col == 8:
return backtrack(board, row + 1, 0)
else:
return backtrack(board, row, col + 1)
# Check if cell is empty
if board[row][col] == 0:
# Try all numbers
for num in range(1, 10):
board[row][col] = num
if is_valid_position(board, row, col):
if backtrack(board, row, col):
return True
# Reset on backtrack
board[row][col] = 0
return False
backtrack(board, 0, 0)
Write a program to find a Hamiltonian cycle in a graph using backtracking.
def hamiltonian_cycle(graph):
# Set up initial state
n = len(graph)
visited = [False] * n
current_path = [0]
best_path = None
def backtrack(i):
nonlocal best_path
if i == n:
if graph[current_path[-1]][0]:
best_path = current_path[:]
return
# Try all vertices that have not yet been visited
for j in range(n):
if not visited[j] and graph[current_path[-1]][j]:
visited[j] = True
current_path.append(j)
backtrack(i + 1)
visited[j] = False
current_path.pop()
backtrack(1)
return best_path