16. Backtracking

Overview of Backtracking

Backtracking is a depth‑first search technique that incrementally builds candidates to a solution and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The general template consists of three components:

1. Choice – decide the next element to add to the partial solution.
2. Constraints – prune branches that violate problem rules.
3. Goal test – verify whether the current partial solution is a complete solution.

The recursive skeleton is:

function backtrack(state):
if is_solution(state):
output(state)
return
for each candidate in choices(state):
if is_valid(state, candidate):
add candidate to state
backtrack(state)
remove candidate from state // backtrack


Because the search space can be exponential, effective pruning is essential to reduce the average running time.

N‑Queens Problem

The N‑Queens problem asks to place n queens on an n×n chessboard so that no two queens attack each other. Queens threaten each other if they share the same row, column, or diagonal.

Representation

We store the board as a one‑dimensional array board[col] = row, meaning that in column col the queen is placed at row row. Since each column contains exactly one queen, the array length is n.

Safety Check

When trying to place a queen at position (row, col) we must ensure:

• No previous queen in the same row: board[i] != row for all i < col.
• No diagonal conflict: |board[i] - row| != col - i for all i < col.

These conditions can be tested in O(n) time, or optimized to O(1) using bitmask sets for columns, main diagonals (row - col) and anti‑diagonals (row + col).

Backtracking Algorithm

function solve(col):
if col == n:
record solution
return
for row in 0 .. n-1:
if safe(row, col):
board[col] = row
solve(col+1)


The algorithm explores each row in the current column, places a queen if safe, and recurses to the next column. When col == n a full placement has been found.

Example (n = 4)

The two distinct solutions are:

1. [1, 3, 0, 2] – queens at (0,1), (1,3), (2,0), (3,2)
2. [2, 0, 3, 1] – queens at (0,2), (1,0), (2,3), (3,1)

Running the above backtracking yields exactly these two boards.

Sudoku Solver

Sudoku consists of a 9×9 grid subdivided into nine 3×3 sub‑grids. The goal is to fill every empty cell with a digit 1‑9 such that each row, column, and sub‑grid contains each digit exactly once. Pre‑filled cells are immutable.

Backtracking Approach

1. Locate the next empty cell (r, c). If none exists, the puzzle is solved.
2. Iterate over digits d = 1 … 9.
3. Check whether placing d at (r, c) violates row, column, or 3×3 box constraints.
4. If valid, assign board[r][c] = d and recurse.
5. On backtrack, reset the cell to empty and try the next digit.

To achieve constant‑time checks we maintain three arrays of bitmasks:

• rowMask[9] – bits set for digits already present in each row.
• colMask[9] – bits set for digits already present in each column.
• boxMask[9] – bits set for digits already present in each 3×3 box (index box = (r/3)*3 + c/3).

Placing a digit d corresponds to setting bit 1 << (d-1). The safety test is:

if ((rowMask[r] & bit) == 0 && (colMask[c] & bit) == 0 && (boxMask[box] & bit) == 0) { /* safe */ }

Complexity

In the worst case the algorithm examines 9^{E} possibilities where E is the number of empty cells. With effective pruning (bitmask checks) most puzzles are solved in a fraction of a second.

Example

Consider the following partially filled grid (0 denotes empty):

The backtracking solver fills it in fewer than 10 recursive steps, producing the completed board.

Rat in a Maze

Given an N×N maze where 1 denotes an open cell and 0 a blocked cell, the task is to find a path from the top‑left corner ((0,0)) to the bottom‑right corner ((N‑1,N‑1)) moving only in allowed directions (commonly down and right, or all four directions). The path cannot step on blocked cells or outside the maze.

Backtracking Procedure

1. Mark the current cell as part of the solution path.
2. If the current cell is the destination, return success.
3. For each allowed direction (e.g., down, right, up, left):
       • Compute the next cell coordinates.
       • If the next cell is inside the maze, open (1), and not yet visited, recursively attempt to continue the path from there.
4. If none of the directions leads to a solution, unmark the current cell (backtrack) and return failure.

Pseudocode

function solveMaze(maze, x, y, sol):
if x == N-1 && y == N-1:
sol[x][y] = 1
return true
if isSafe(maze, x, y):
sol[x][y] = 1
// try down
if solveMaze(maze, x+1, y, sol) return true
// try right
if solveMaze(maze, x, y+1, sol) return true
// (optional) try up, left
sol[x][y] = 0 // backtrack
return false
return false


Example Maze (4×4)

One valid path (coordinates) is:

• (0,0) → (1,0) → (1,1) → (2,1) → (3,1) → (3,2) → (3,3)

The algorithm marks these cells with 1 in the solution matrix and leaves the rest 0.

Permutations Generation

Generating all permutations of a set of n distinct elements is a classic backtracking problem. The algorithm builds the permutation one element at a time, keeping track of which elements have already been used.

Algorithm

1. Maintain an array used[0…n‑1] (boolean) and a temporary array curr[0…n‑1] for the current permutation.
2. Recursive function permute(depth):
• If depth == n, output curr as a complete permutation.
• Otherwise, iterate over all indices i from 0 to n‑1:
• If !used[i]:
• Set used[i] = true.
• Assign curr[depth] = arr[i].
• Recurse: permute(depth+1).
• Undo: used[i] = false (backtrack).

Pseudocode

function permute(depth):
if depth == n:
output(current)
return
for i in 0 .. n-1:
if not used[i]:
used[i] = true
current[depth] = arr[i]
permute(depth+1)
used[i] = false


Complexity

The algorithm produces n! permutations. Each permutation requires O(n) time to copy or output, leading to a total time of O(n·n!). The auxiliary space is O(n) for the used and current arrays plus recursion depth.

Example (set {A, B, C})

The six permutations in lexicographic order are:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

Summary and Best Practices

Backtracking is a versatile technique applicable whenever a solution can be constructed incrementally and invalid partial constructions can be detected early. Key takeaways:

• Clearly define the choice set at each recursion level.
• Implement an efficient is_valid (or safe) test; pruning drastically reduces the search space.
• Use appropriate data structures (arrays, bitmasks, boolean flags) to achieve O(1) validity checks when possible.
• Remember to undo changes (backtrack) after the recursive call to restore the state for the next alternative.
• For problems with symmetries (e.g., N‑Queens), consider additional pruning such as placing the first queen only in the first half of the board to avoid duplicate solutions.

By mastering the template illustrated in this chapter, you can tackle a wide range of combinatorial search problems, from puzzles like Sudoku to optimization tasks such as the traveling salesperson (via branch‑and‑bound extensions).