Backtracking: N-Queens, Sudoku Solver and Subsets in Python

Backtracking

Backtracking is a systematic way to search through all possible solutions — try a choice, recurse, and if it leads to a dead end, undo the choice and try the next. It prunes the search space by abandoning invalid branches early.

# N-Queens: place N queens on NxN board so none attack each other
def solve_n_queens(n):
    solutions = []
    board     = [-1] * n  # board[row] = column of queen

    def is_valid(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            if prev_col == col: return False  # same column
            if abs(prev_col - col) == abs(prev_row - row): return False  # diagonal
        return True

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_valid(row, col):
                board[row] = col
                backtrack(row + 1)   # recurse
                board[row] = -1      # undo (backtrack)

    backtrack(0)
    return len(solutions)

print(solve_n_queens(8))  # 92 solutions for 8x8 board

Generate All Subsets

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])  # record current subset
        for i in range(start, len(nums)):
            current.append(nums[i])     # choose
            backtrack(i+1, current)     # explore
            current.pop()               # unchoose (backtrack)

    backtrack(0, [])
    return result

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

# Sudoku Solver
def solve_sudoku(board):
    empty = find_empty(board)
    if not empty: return True  # no empty cell — solved!
    row, col = empty

    for num in range(1, 10):
        if is_valid_sudoku(board, row, col, num):
            board[row][col] = num       # place number
            if solve_sudoku(board): return True  # recurse
            board[row][col] = 0         # backtrack

    return False  # trigger backtrack in caller