iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Backtracking

By · Reviewed & last updated · Part of Data Structures & Algorithms

Backtracking explores a search tree of partial solutions and prunes branches that cannot succeed. It is the right tool for combinatorial problems: permutations, subsets, N-Queens, Sudoku, word search, constraint satisfaction. The structure is always the same: choose, recurse, undo. The art is in the pruning — without it, you have brute force.

Subsets, N-Queens, and Sudoku via backtracking

EXAMPLE
# 1) All subsets of [a, b, c]
def subsets(nums):
    out = []
    path = []
    def back(i):
        if i == len(nums):
            out.append(path.copy()); return
        # exclude
        back(i + 1)
        # include
        path.append(nums[i])
        back(i + 1)
        path.pop()
    back(0)
    return out

print(subsets([1, 2, 3]))   # 8 subsets including []

# 2) N-Queens — classic pruning problem
def n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    placement = []
    solutions = []
    def back(r):
        if r == n:
            solutions.append(placement.copy()); return
        for c in range(n):
            # pruning: each col and diagonal at most once
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            placement.append(c)
            back(r + 1)
            placement.pop()
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
    back(0)
    return solutions

print(f'N=8 has {len(n_queens(8))} solutions')   # 92

# 3) Sudoku — backtrack on the next empty cell
def solve_sudoku(board):                          # 9x9, 0 = empty
    def is_valid(r, c, v):
        for i in range(9):
            if board[r][i] == v or board[i][c] == v: return False
        br, bc = 3 * (r // 3), 3 * (c // 3)
        for i in range(br, br + 3):
            for j in range(bc, bc + 3):
                if board[i][j] == v: return False
        return True
    def back():
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    for v in range(1, 10):
                        if is_valid(r, c, v):
                            board[r][c] = v
                            if back(): return True
                            board[r][c] = 0          # undo
                    return False
        return True
    back()
    return board

puzzle = [
    [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],
]
print(solve_sudoku(puzzle)[0])

Why it matters

The cheap pruning checks at the top of the recursion (cols/diag sets in N-Queens, MRV ordering in Sudoku) often turn a 2^N explosion into a problem that finishes in milliseconds. Always design the prune before you write the recursion.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
function permutations(nums, path = [], out = []) {
    if (path.length === nums.length) { out.push([...path]); return out; }
    for (const n of nums) {
        if (path.includes(n)) continue;
        path.push(n);
        permutations(nums, path, out);
        path.pop();
    }
    return out;
}
Try it Yourself »

Discussion

Loading…