Backtracking Algorithms

What is Backtracking?

Backtracking is an algorithmic technique for solving problems incrementally, trying partial solutions and then abandoning them if they do not lead to a valid solution. It is often used in constraint satisfaction problems like puzzles, combinatorial problems, and pathfinding.

How Backtracking Works

• Start with an initial candidate solution.
• Attempt to extend this candidate solution step-by-step.
• If at any point the candidate solution cannot be extended further (dead end), backtrack to the previous step and try a different path.
• Continue this process until a valid solution is found or all possibilities are exhausted.

Example 1: N-Queens Problem

Place N queens on an N×N chessboard so that no two queens threaten each other.

def is_safe(board, row, col):
    for i in range(row):
        if board[i] == col or \
           abs(board[i] - col) == abs(i - row):
            return False
    return True

def solve_n_queens(n, row=0, board=None, solutions=None):
    if board is None:
        board = [-1] * n
    if solutions is None:
        solutions = []

    if row == n:
        solutions.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
        return

    for col in range(n):
        if is_safe(board, row, col):
            board[row] = col
            solve_n_queens(n, row + 1, board, solutions)
            board[row] = -1  # backtrack

# Usage example
solutions = []
solve_n_queens(4, solutions=solutions)
for sol in solutions:
    for row in sol:
        print(row)
    print()

Example 2: Maze Solving

Find a path through a maze represented by a 2D grid.

def solve_maze(maze, x, y, path):
    n = len(maze)
    if x == n - 1 and y == n - 1:
        path[x][y] = 1
        return True
    if 0 <= x < n and 0 <= y < n and maze[x][y] == 1 and path[x][y] == 0:
        path[x][y] = 1
        if solve_maze(maze, x + 1, y, path):
            return True
        if solve_maze(maze, x, y + 1, path):
            return True
        path[x][y] = 0  # backtrack
    return False

# Usage example
n = 4
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
path = [[0]*n for _ in range(n)]
if solve_maze(maze, 0, 0, path):
    for row in path:
        print(row)
else:
    print("No path found")

Applications of Backtracking

• Sudoku solver
• Permutation and combination problems
• Graph coloring
• Constraint satisfaction problems
• Pathfinding in games and robotics