Backtracking: The Matrix of Sudoku & N-Queens

The Quest Begins (The "Why")

I still remember the first time I tried to solve a Sudoku puzzle in an interview. The interviewer slid a partially filled grid across the table and said, “Just fill it in.” I stared at the empty cells, started guessing numbers, and quickly realized I was wandering in circles—guess a 5 here, later discover it breaks the column, erase, try a 6, repeat. After twenty minutes of erasing and re‑guessing, I felt like I was stuck in a boss fight where every attack just bounced off the shield.

That frustration is exactly why backtracking exists. It’s not a magic wand; it’s a disciplined way to explore possibilities, undoing choices the moment they lead to a dead end. If you’ve ever felt like you’re playing a game where you can save, try a path, and reload when you hit a wall, you already intuitively get the idea.

The Revelation (The Insight)

The core insight is simple: instead of committing to a guess forever, treat each guess as a temporary hypothesis.

1. Choose an empty cell.
2. Try a candidate value that doesn’t violate any constraints right now (row, column, box for Sudoku; no two queens share a row, column, or diagonal for N‑Queens).
3. Recurse – move to the next empty cell and repeat.
4. If you hit a cell where no candidate works, undo the last choice (backtrack) and try the next alternative.

Why does this work? Because the moment a partial assignment violates a rule, no completion of that assignment can ever be valid. Pruning that branch early saves us from exploring an exponential number of futile leaves. The algorithm is essentially a depth‑first search with a safety net: every step is reversible, and we only go deeper when the current prefix is still promising.

That’s why backtracking shines for constraint‑heavy problems like Sudoku and N‑Queens: the constraints are cheap to check, and they cut off huge swaths of the search space early.

Wielding the Power (Code & Examples)

Before: The Naïve Brute‑Force Struggle

def solve_sudoku_bruteforce(board):
    # Fill empties with 1‑9 and check at the end
    empties = [(r, c) for r in range(9) for c in range(9) if board[r][c] == 0]
    for combo in product(range(1, 10), repeat=len(empties)):
        for (r, c), val in zip(empties, combo):
            board[r][c] = val
        if is_valid(board):          # O(9*9) check each time
            return True
        # reset board for next combo
        for r, c in empties:
            board[r][c] = 0
    return False

What’s wrong?

• We generate 9ⁿ possibilities where n is the number of empty cells (up to 81).
• We only validate after filling the entire board, wasting huge amounts of work on clearly invalid prefixes.

After: Backtracking with Early Pruning

def solve_sudoku(board):
    def backtrack():
        # find next empty cell
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    # try each digit
                    for d in range(1, 10):
                        if safe(board, r, c, d):
                            board[r][c] = d
                            if backtrack():
                                return True
                            board[r][c] = 0          # undo (backtrack)
                    return False                     # no digit works → backtrack
        return True                                 # board full

    def safe(b, r, c, d):
        # row & column
        if d in b[r] or d in [b[i][c] for i in range(9)]:
            return False
        # 3×3 box
        br, bc = 3 * (r // 3), 3 * (c // 3)
        for i in range(br, br + 3):
            for j in range(bc, bc + 3):
                if b[i][j] == d:
                    return False
        return True

    return backtrack()

Why this feels like a victory:

• The safe check is O(1) for a fixed‑size board (constant 9).
• As soon as a digit conflicts, we skip the entire subtree that would have started with that digit.
• The recursion depth is at most the number of empty cells (≤81), so the call stack stays tiny.

Real‑World Interview Variant: N‑Queens

The same pattern solves the classic N‑Queens problem: place N queens on an N×N board so none attack each other.

def solve_n_queens(n):
    def backtrack(row, cols, diag1, diag2):
        if row == n:
            return True                     # all queens placed
        for col in range(n):
            d1 = row - col
            d2 = row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue                    # conflict → prune
            # place queen
            cols.add(col); diag1.add(d1); diag2.add(d2)
            if backtrack(row + 1, cols, diag1, diag2):
                return True
            # undo placement
            cols.remove(col); diag1.remove(d1); diag2.remove(d2)
        return False

    return backtrack(0, set(), set(), set())

Explanation:

• cols, diag1, diag2 track occupied columns and the two diagonal families.
• Each placement test is O(1); the recursion explores at most N! leaves in the worst case, but pruning cuts the search dramatically—often to a fraction of that for modest N (e.g., N=8 yields 92 solutions instantly).

Complexity Talk

For Sudoku (fixed 9×9), each recursive call does a constant‑time safety check, so the work per node is O(1). The total time is O(b^d) where b ≤ 9 (branching factor) and d is the number of empty cells. In practice, constraint pruning reduces b drastically, making puzzles solve in milliseconds.

For N‑Queens, each call does O(1) checks using the three sets, giving the same O(b^d) shape with b = N. The algorithm is exponential in the worst case (as the problem itself is), but the pruning makes it feasible for N up to ~15 on a laptop—far better than naïve generate‑and‑test which would be O(N! ).

Why This New Power Matters

Mastering backtracking gives you a reusable toolkit for any interview problem that asks you to “find a configuration that satisfies constraints”:

• Sudoku solvers (classic)
• N‑Queens, word search, crossword filling
• Maze pathfinding with obstacles
• Configuring feature toggles, scheduling tasks, even certain parsing tasks

When you see a problem where you can make a local choice, test it instantly, and undo it cleanly, you’ve spotted a backtracking opportunity. The ability to prune early turns an impossible brute force into an elegant, fast solution.

Your Turn

Grab a piece of paper (or your favorite IDE) and try this: write a solver for KenKen puzzles using the same pattern—track row/column uniqueness and the cage arithmetic constraints. When you get it working, you’ll have leveled up from “guess‑and‑check” to “strategic quest‑master.”

What’s the first constraint‑heavy problem you’ll tackle with backtracking? Drop a comment or tweet your solution—I can’t wait to see what you build! 🚀