Backtracking

Yasin Cakal

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

Data Structures and Algorithms with Python

Participants 681