Backtracking Algorithms Revision Notes for OCR A-Level Computer Science

Backtracking Algorithms

Overview

Backtracking is an algorithmic technique used for solving problems that involve searching through all possible solutions to find the correct one. It systematically explores potential solutions, and when a solution path is found to be invalid or suboptimal, it backtracks to explore other possibilities.

Backtracking is particularly useful in problems involving decision trees, combinatorial optimisation, and constraint satisfaction, such as solving mazes, puzzles, and scheduling problems.

Purpose of Backtracking

To explore all possible solutions to a problem in a structured way.
If a partial solution violates the problem's constraints, backtracking abandons it and tries a different path.
Common use cases include:
- Traversing trees and graphs.
- Solving puzzles (e.g., Sudoku, N-Queens problem).
- Finding permutations and combinations.

How Backtracking Works

Choose a Path:

Start with an initial partial solution.

Check Constraints:

Verify if the current path satisfies the problem's constraints.

Expand or Backtrack:

If valid, expand the solution by exploring the next step.
If invalid, backtrack to the previous step and try an alternative path.

Repeat Until Solution is Found:

Continue this process until a valid solution is found or all possibilities are exhausted.

infoNote

Example 1: N-Queens Problem

Problem Statement: Place N queens on an N x N chessboard so that no two queens threaten each other (no two queens can share the same row, column, or diagonal).

Backtracking Approach:

Place a queen in the first row.
Move to the next row and place a queen in a valid column.
If no valid column is found, backtrack to the previous row and move the queen to a new column.
Repeat until all queens are placed or all possibilities are explored. Pseudocode:

FUNCTION solveNQueens(board, row):
    IF row == N THEN
        PRINT board
        RETURN true
    FOR col = 0 TO N-1:
        IF isSafe(board, row, col) THEN
            board[row][col] = "Q"  # Place queen
            IF solveNQueens(board, row + 1) THEN
                RETURN true
            board[row][col] = "."  # Remove queen (backtrack)
    RETURN false

FUNCTION isSafe(board, row, col):
    CHECK for other queens in the same column or diagonal
    RETURN true IF safe, otherwise false

infoNote

Example 2: Maze Solver

Problem Statement: Find a path through a maze from the start to the end.

Backtracking Approach:

Start at the initial position.
Move in a valid direction (up, down, left, right).
If a move leads to a dead end, backtrack and try a different direction.
Continue until the exit is reached or all paths are explored. Pseudocode:

FUNCTION solveMaze(maze, x, y):
    IF x, y is the exit THEN
        RETURN true
    IF maze[x][y] is valid THEN
        maze[x][y] = "visited"
        IF solveMaze(maze, x+1, y) THEN
            RETURN true
        IF solveMaze(maze, x, y+1) THEN
            RETURN true
        IF solveMaze(maze, x-1, y) THEN
            RETURN true
        IF solveMaze(maze, x, y-1) THEN
            RETURN true
        maze[x][y] = "unvisited"  # Backtrack
    RETURN false

Tracing Backtracking Algorithms

lightbulbExample

Example: Let's trace the N-Queens problem for N=4:

Start with an empty 4x4 board.
Place a queen in the first row (column 1).
Move to the second row, and check the valid columns:

Place in column 3.

Move to the third row, and check the valid columns:

No valid positions; backtrack to row 2.

Move the queen in row 2 to column 4.
Continue this process until all queens are placed or no solution is possible.

Benefits of Backtracking

Systematic Search: Explores all possibilities in an organised manner.
Pruning Invalid Paths: Quickly eliminates paths that do not meet the problem's constraints.
Simple Implementation: Relatively easy to implement using recursion.

Drawbacks of Backtracking

Inefficient for Large Problems:

May require exploring many possibilities, leading to high time complexity.
Example: $O(2^n)$ in the worst case for certain problems.

Recursive Overhead:

Relies on recursion, which can lead to stack overflow for very deep recursive calls.

Note Summary

infoNote

Common Mistakes

Incorrect Base Case: Failing to define or implement the base case correctly can cause infinite recursion.
Not Restoring State: Forgetting to undo changes when backtracking can lead to incorrect solutions.
Ignoring Constraints: If constraints are not checked at each step, invalid solutions may be generated.

infoNote

Key Takeaways

Backtracking systematically explores all potential solutions by trying, validating, and discarding paths as necessary.
It is particularly useful for solving combinatorial and constraint satisfaction problems.
Understanding the recursive nature of backtracking and properly handling state changes are essential for implementing these algorithms effectively.
While powerful, backtracking may be computationally expensive for large or complex problems.

Backtracking Algorithms (OCR A-Level Computer Science): Revision Notes