Backtracking: The Sudoku & N-Queens Quest (Like a Jedi)

The Quest Begins (The "Why")

I still remember the first time I tried to write a Sudoku solver in college. I thought, “Hey, I’ll just loop through every empty cell, drop a number in, and see if it works.” Sounds simple, right? After a few hours of watching my program churn through billions of possibilities, I realized I was basically trying to brute‑force the entire search tree. My laptop fan sounded like a jet taking off, and the answer never came. I felt stuck in a loop that had no exit—like I was trying to solve a Rubik’s cube by shaking it violently.

That frustration led me to ask: Is there a smarter way to explore possibilities without trying every single combination? The answer turned out to be backtracking, a technique that feels like having a map that tells you when you’ve hit a dead end so you can turn back immediately. Once I grasped it, the solver went from “never finishing” to “solved in milliseconds.” It was like finding a secret shortcut in a maze.

The Revelation (The Insight)

Backtracking isn’t just a fancy term for recursion; it’s a principled way to prune the search space as soon as you know a partial solution can’t possibly lead to a valid answer. Think of building a solution piece by piece. After each placement, you check the constraints that matter right now. If any constraint is violated, you undo the last step and try a different option. If none work, you backtrack further up the chain.

Why does this work? Because every valid complete solution must pass every constraint at every prefix. If a prefix already fails, no amount of later filling can fix it. So we can safely discard that entire subtree of possibilities. The algorithm explores the tree depth‑first, but it never wastes time on branches that are doomed from the start.

The beauty is that the same pattern applies to many constraint‑satisfaction puzzles: Sudoku, N‑Queens, graph coloring, even scheduling problems. You only need to define:

1. What constitutes a placement (a number in a cell, a queen on a row).
2. How to test if a placement is still valid given the current board.
3. How to undo a placement when you retreat.

Once those three pieces are clear, the recursive skeleton is almost identical across problems.

Wielding the Power (Code & Examples)

Let’s see the pattern in action. First, a naïve Sudoku attempt that loops over all possibilities (spoiler: it’s painfully slow).

# Naïve brute force – DO NOT USE
def solve_bruteforce(board):
    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(board):
            return True
        # reset board for next combo (omitted for brevity)
    return False

product from itertools creates 9^empty_cells combinations—astronomical even for a modest puzzle. The check is_valid_board scans the whole board each time, making it even worse.

Now the backtracking version. Notice how we validate as we go and undo immediately when we hit a wall.

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:
                    for num in range(1, 10):
                        if safe(board, r, c, num):
                            board[r][c] = num          # place
                            if backtrack():
                                return True            # solved!
                            board[r][c] = 0            # undo (backtrack)
                    return False                      # trigger backtracking
        return True  # no empty cells → solved

    def safe(board, r, c, num):
        # row & column
        for i in range(9):
            if board[r][i] == num or board[i][c] == num:
                return False
        # 3×3 subgrid
        sr, sc = 3 * (r // 9), 3 * (c // 9)
        for i in range(sr, sr + 3):
            for j in range(sc, sc + 3):
                if board[i][j] == num:
                    return False
        return True

    return backtrack()

What changed?

• We pick the next empty cell instead of iterating over a pre‑built list.
• For each candidate num, we call safe which checks only the row, column, and local box—constant‑time work.
• If safe fails, we skip that number entirely; we never go deeper.
• After placing a number we recurse. If the deeper call returns False, we undo the placement (board[r][c] = 0) and try the next number.
• When we run out of numbers for a cell, we return False to force the caller to backtrack further up.

The same skeleton solves N‑Queens with only a tweak to the safety check.

def solve_nqueens(n):
    board = [-1] * n          # board[row] = column of queen in that row

    def backtrack(row):
        if row == n:
            return True       # all queens placed
        for col in range(n):
            if is_safe(row, col, board):
                board[row] = col
                if backtrack(row + 1):
                    return True
                board[row] = -1   # undo
        return False

    def is_safe(r, c, b):
        # check previous rows for column or diagonal conflicts
        for prow in range(r):
            pcol = b[prow]
            if pcol == c or abs(prow - r) == abs(pcol - c):
                return False
        return True

    return backtrack(0) and board

Common Traps (the “gotchas” on the quest)

1. Forgetting to undo – If you don’t reset the cell after a failed recursive call, the board stays polluted and you’ll miss valid solutions.
2. Checking validity too late – Validating only after placing all numbers (as in the brute force version) wastes huge amounts of time.
3. Using mutable globals carelessly – Passing the board around by reference is fine, but you must manually revert changes; otherwise you’ll get bizarre, non‑deterministic results.

Both snippets avoid these pitfalls by keeping the undo step right after the recursive call.

Why This New Power Matters

Armed with backtracking, you can tackle a whole class of interview questions that look intimidating at first glance:

• “Write a Sudoku solver.” – Now you can implement it in under 30 lines and watch it solve even the hardest puzzles instantly.
• “Place N queens on an N×N board so none attack each other.” – The same pattern scales; you’ll see the solution emerge as the recursion unwinds.
• “Given a set of words, find a word square.” – Again, place a word, check row/column prefixes, backtrack when they diverge.

The asymptotic worst case is still exponential (Sudoku: O(9^k) where k is empty cells; N‑Queens: O(N!)), but the pruning cuts the search dramatically. In practice, the algorithm runs fast enough for typical interview constraints (N ≤ 12 for queens, standard 9×9 Sudoku). More importantly, you’ve learned a mindset: whenever you see a problem that asks you to “find a configuration that satisfies a set of constraints,” think backtracking first.

Your Turn

Pick a puzzle you’ve always found tedious—maybe a Kakuro grid, a Hamiltonian path in a small graph, or even a word‑search builder. Write the three pieces (placement test, validity check, undo) and let backtracking do the heavy lifting. When it finally clicks, you’ll feel like you’ve unlocked a cheat code for combinatorial chaos.

What’s the first constraint‑satisfaction problem you’ll conquer with your new backtracking superpower? Share your solution or a stub in the comments—I’d love to see how you put this quest into action! 🚀