A Comprehensive Guide on Backtracking Algorithm

Introduction

The backtracking algorithm is a next step in the problem solving algorithm to solve those problems incrementally and it is one of the most used methods in the computer science. It looks for a solution in a step by step manner with all available avenues explored before any strategy is thrown to the bin since it is bound to fail. This approach is most suitable when formulating puzzles, finding paths, or even dealing with the constraint satisfaction type of problems. That is why knowing the principles of backtracking can fully open in terms of effective problem-solving, abilities.

Learning Outcomes

• Understand the basic concept of the backtracking algorithm.
• Learn how backtracking is used to solve combinatorial problems.
• Identify real-world applications of backtracking.
• Implement backtracking solutions in coding problems.
• Recognize the limitations and challenges of using backtracking.

What is Backtracking?

Backtracking is an analyzing algorithm which constructs the candidates progressively in order to solve a problem. It works on one approach and if it realizes that the current candidate does not lead towards a valid solution then it gets back to the last component that was added and take another path. It goes on in this manner until a proper or acceptable solution is generated or until all possibilities have been tried out.

How Backtracking Works?

Backtracking is an algorithmic approach to decision making for problems in which various possibilities are mapped and decisions that take the problem solver to a negative state are reversed. It is an application of depth first search where the algorithm construct a solution step by step and backtracks if a given step is inapplicable to the problem at hand.

Recursive Exploration

The backtracking algorithm begins from a given state and goes through each step, selection or decision and performs backtracking. At each node, the algorithm explores the possibility of adding a new element in the current solution and move to the next.

Decision Making

At each step of its calculation the algorithm arrives at a decision from a number of potential alternatives. This could be simply entering a number in a Sudoku puzzle, picking an item in case of the knapsack problem or picking a move in the game. This also adds the choice to the solution at the present implementation.

Constraint Checking

After making a choice, the algorithm checks if the current solution satisfies the problem’s constraints. If it does, the algorithm continues exploring further. If not, it backtracks by removing the last choice and tries the next option.

Backtracking

When the algorithm encounters a constraint violation or a dead end, it undoes the last choice and returns to the previous state. This process of undoing and trying different options is known as backtracking. It ensures that all possible solutions are explored without getting stuck in invalid paths.

Solution Validation

Once a complete solution that meets all constraints is found, the algorithm records or outputs the solution. If no valid solution exists, the algorithm continues exploring other options until all possibilities have been exhausted.

Termination

The algorithm terminates when all options have been explored, and a solution is found or confirmed to be impossible. In some cases, the algorithm may stop early if it discovers a solution that meets specific criteria or optimizes a given objective.

Also Read: What is the Water Jug Problem in AI?

Implementing Backtracking in Code

Here’s a simple implementation of backtracking for solving the N-Queens problem in Python:

def is_safe(board, row, col):
    # Check for queen conflicts in the column, left diagonal, and right diagonal
    for i in range(row):
        if board[i][col] == 'Q' or (col-i-1 >= 0 and board[row-i-1][col-i-1] == 'Q') or (col+i+1 < len(board) and board[row-i-1][col+i+1] == 'Q'):
            return False
    return True

def solve_n_queens(board, row):
    if row == len(board):
        return True
    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 'Q'
            if solve_n_queens(board, row + 1):
                return True
            board[row][col] = '.'
    return False

def n_queens(n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    solve_n_queens(board, 0)
    return board

When to Use a Backtracking Algorithm

We will now look into on how to use backtracking algorithm.

Search Problems with Constraints

It is important in those problems where you want to search for all possible solutions but at the same time there are certain restrictions that must not be crossed. For example, when working through a Sudoku puzzle, then in this case, one has to place numbers in cells in a manner that each line, row, and field has only distinctive values. Backtracking is useful in a way that when a wrong value is inserted, it has to be erased and attempt the following options until there is one answer to the Objective problem.

Combinatorial Problems

Backtracking is used when one needs to generate all the permutations or all the possibilities when a thing or an object must be put in a certain order. An example is the Eight Queens problem in which there are eight queens placed on an 8×8 chessboard so that no two queens are in the same vertical or horizontal row or on the same diagonal. Backtracking can be used to try the locations of backtracking when a position of the queen is inconvenient and again start from the new position.

Optimization Problems

Back-tracking becomes useful in cases where there are many choices and where you have to select the best one because it gets rid of choices systematically and obeys constraints. For instance, the knapsack problem can involve picking the items with the specified weight and value to find out the particular value of all the items without even reaching the maximum weight. Backtracking is the process where selection of items is examined to come up with the best option.

Pathfinding and Maze Solving

Taking a step back allows one to move through the space and even when there are barriers on the way, find how they can be overcome. You could try building a maze in which a path is required to be made from the entrance to the exit avoiding blind alleys. Backtracking tries all the possibilities, goes back to the earlier state when it encounters a dead end and keeps searching to get the feasible path.

Pattern Matching and String Problems

When dealing with pattern matching or generating permutations, backtracking can systematically explore different possibilities. For example, in regular expression matching, backtracking checks different ways to match patterns against a string, ensuring all possible matches are considered.

Game Strategy and Decision Making

In game strategy or decision-making scenarios, backtracking helps explore all possible moves or strategies. For instance, in the 15-puzzle game, where you slide tiles to achieve a specific configuration, backtracking explores various tile movements and retraces steps to reach the desired arrangement.

Algorithm for Solving Sudoku with Backtracking

Sudoku is a daily puzzle game, the solution to which is an arrangement of number on an 81-cell graph board that divides into nine 3×3 sub graphs to prevent any row, column, or 3×3 subgraph from having the same number twice. The problem of solving Sudoku puzzles can be solved by backtracking algorithm.

Detailed Explanation

Here’s a detailed explanation of how backtracking can be used to solve a Sudoku puzzle, including the algorithm:

• Find the Next Empty Cell: Start by locating the first empty cell in the grid. An empty cell is one that has not been assigned a number yet.
• Try Possible Numbers: For the empty cell found, attempt to place each number from 1 to 9. After placing a number, check if the placement is valid (i.e., the number does not conflict with existing numbers in the same row, column, and 3×3 subgrid).
• Check Validity: Validate the number placement by ensuring that it does not violate Sudoku rules:
  • The number must not already exist in the same row.
  • The number must not already exist in the same column.
  • The number must not already exist in the same 3×3 subgrid.
• Recursive Call: If the number placement is valid, make a recursive call to solve the rest of the puzzle with this number in place.
• Backtrack if Necessary: If the recursive call does not lead to a solution that is, if it gets ‘stuck’ in a dead end, backtrack and eliminate the number.
• Repeat Until Solved: Do this until the puzzle is solved or all numbers have been attempted for blank cell. If none of them fits, go to the previous blank lined cell and attempt the next available number.
• Terminate: It ends either the puzzle is solved or all the possibilities are exhausted without a solution to the puzzle.

In this article, we will explain the approach of backtracking, in order to solve Sudoku, and I will divide the solution into smaller steps to be properly explained.

Checking Validity of a Number

Before placing a number in an empty cell, we need to verify that it follows Sudoku rules. This involves checking the row, column, and 3×3 subgrid.

def is_valid(board, row, col, num):
    # Check if num is not already in the current row
    if num in board[row]:
        return False

    # Check if num is not already in the current column
    for r in range(9):
        if board[r][col] == num:
            return False

    # Check if num is not already in the current 3x3 subgrid
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for r in range(start_row, start_row + 3):
        for c in range(start_col, start_col + 3):
            if board[r][c] == num:
                return False

    return True

• Row Check: Ensure that num does not already exist in the same row.
• Column Check: Ensure that num is not present in the same column.
• Subgrid Check: Verify that num is not in the 3×3 subgrid that includes the cell (row, col).

Solving the Sudoku Puzzle

This function uses backtracking to fill the Sudoku grid.

def solve_sudoku(board):
    # Find the next empty cell
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                # Try placing numbers 1 to 9
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        # Recursively attempt to solve the rest of the board
                        if solve_sudoku(board):
                            return True
                        # Backtrack if no solution is found
                        board[row][col] = 0
                return False
    return True

• Finding Empty Cells: The loop scans the board to locate the first empty cell (indicated by 0).
• Trying Numbers: For each empty cell, the algorithm tries placing numbers from 1 to 9.
• Validation and Recursion: If a number is valid, it’s placed in the cell. The algorithm then makes a recursive call to solve the rest of the board.
• Backtracking: If the recursive call does not lead to a solution, the number is removed (reset to 0) and the next number is tried.
• Completion: The process continues until the board is completely filled or all possibilities are exhausted.

Example Sudoku Board

The following is an example Sudoku board that will be solved using the solve_sudoku function:

# Example board (0s represent empty cells)
sudoku_board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

• Initial Board: This is a partially filled Sudoku puzzle with some cells empty (represented by 0).

Running the Solver

Finally, we use the solve_sudoku function to solve the puzzle and print the completed board.

# Solve the Sudoku puzzle
if solve_sudoku(sudoku_board):
    for row in sudoku_board:
        print(row)
else:
    print("No solution exists.")

• Solving and Output: If the solve_sudoku function finds a solution, the completed board is printed. If no solution exists, it outputs “No solution exists.”

This approach demonstrates how backtracking can systematically explore possible solutions to solve a Sudoku puzzle, ensuring that each number placement adheres to Sudoku rules while efficiently searching for a valid solution.

Applications of Backtracking

Let us now explore applications of back tracking below:

• Sudoku: Solves the puzzle by ensuring no repeated numbers in rows, columns, or grids.
• Crossword Puzzles: Places words in a grid while fitting with existing letters.
• 8-Queens Problem: Places 8 queens on a chessboard where no two queens threaten each other.
• Graph Coloring: Assigns colors to vertices such that no two adjacent vertices share the same color.
• Scheduling: Assigns tasks to time slots or resources without conflicts.
• Knapsack Problem: Selects items to maximize value without exceeding weight limits.
• Subset Sum Problem: Finds subsets of numbers that sum to a target value.
• Regular Expression Matching: Matches patterns against strings by exploring different configurations.
• String Permutations: Generates all possible permutations of a given string.
• Maze Solving: Finds a path through a maze from start to finish.
• Chess: Evaluates different moves to find optimal strategies.

Challenges and Limitations of Backtracking

Backtracking is generally a very flexible and effective algorithmic tool especially when you are confronted with twofold issues to solve. However, as is the case with any algorithmic technique, it has its peculiarities and drawbacks as well. Knowledge of these can assist in identifying the time when one should use backtracking and how the certain drawbacks of the method may be avoided.

Exponential Time Complexity

In backtracking, it is impossible to avoid backtrack if it has to be employed, but there are certain drawbacks associated with it such as exponential in time complexity. This means that the time that is taken can increase exponentially with increase in the size of the input.

For example, in the N-Queens problem, all the solutions which need to be generated by the algorithm are the placements of N queens on an N×N chessboard. The number of possible configuration is equals to the factorial of the number of nodes and thus it is N factorial; this shows that the total size of configurations is tremendously large. Nevertheless, applying this pruning, not all these possibilities may be required to go through to be tested before a solution is found or it is concluded that there is no solution.

This exponential growth can make backtracking impractical for large problem sizes, as the computation time can quickly become unmanageable.

Inefficient for Certain Problems

Backtracking is not always the most efficient approach, especially for problems where the search space is enormous and cannot be pruned effectively.

Some problems, like finding the shortest path in a graph (which can be done efficiently using algorithms like Dijkstra’s or A*), are better solved with other approaches. In such cases, backtracking might waste computational resources by exploring paths that more targeted algorithms would ignore.

For certain problem domains, other algorithms like dynamic programming, greedy algorithms, or branch-and-bound methods can provide more efficient solutions.

Difficulty in Pruning

The effectiveness of backtracking relies on how well the algorithm can prune the search space. This means eliminating large portions of the search tree that do not contain valid solutions. In some problems, identifying when a partial solution cannot lead to a complete solution is challenging. For example, in complex combinatorial problems or puzzles with non-obvious constraints, the algorithm may explore many dead ends. It may take time to realize that a particular path is not viable.

Poor pruning can lead to excessive exploration of the search space, drastically increasing the time required to find a solution.

Memory Consumption

Backtracking algorithms often require significant memory, particularly when they involve deep recursion or the need to store a large number of potential solutions. In a recursive backtracking algorithm, each recursive call adds a new frame to the call stack, which consumes memory. For problems with deep recursion, this can lead to stack overflow errors if the recursion depth exceeds the system’s capabilities.

High memory consumption can limit the size of the problems that can be tackled using backtracking, especially in environments with limited resources.

Lack of Parallelism

Backtracking algorithms are inherently sequential, which makes it difficult to parallelize them effectively. The algorithm typically follows one path at a time and only backtracks when it hits a dead end. While it’s theoretically possible to explore different branches of the search tree in parallel, coordinating these efforts and ensuring efficient use of resources is complex.

The lack of parallelism can be a significant limitation in modern computing environments, where parallel processing and distributed computing are often used to handle large-scale problems.

Complexity of Implementation

Implementing a backtracking algorithm can be complex, especially for problems with intricate constraints. Pruning the search space effectively often requires deep problem-specific knowledge. Writing an efficient backtracking algorithm requires a deep understanding of the problem. It also involves careful consideration of various edge cases.

This complexity can lead to bugs, inefficiencies, or difficulties in maintaining and extending the algorithm, particularly as the problem requirements evolve.

Conclusion

Backtracking is a versatile algorithmic technique that can solve a wide range of problems by exploring all potential solutions and pruning those that don’t meet the criteria. While it may not always be the most efficient, its simplicity and effectiveness in solving complex combinatorial problems make it an invaluable tool in the programmer’s toolkit. Understanding its principles and applications will enable you to tackle challenging problems with confidence.

Frequently Asked Questions

ayushi9821704 04 Sep, 2024

My name is Ayushi Trivedi. I am a B. Tech graduate. I have 3 years of experience working as an educator and content editor. I have worked with various python libraries, like numpy, pandas, seaborn, matplotlib, scikit, imblearn, linear regression and many more. I am also an author. My first book named #turning25 has been published and is available on amazon and flipkart. Here, I am technical content editor at Analytics Vidhya. I feel proud and happy to be AVian. I have a great team to work with. I love building the bridge between the technology and the learner.