Backtracking

Backtracking is recursion with one extra discipline: at each step you make a choice, recurse to see where that choice leads, and if it leads nowhere useful, you undo the choice and try the next option. It's how you actually solve "generate all ___" and "find an arrangement that satisfies these constraints" problems — permutations, combinations, subsets, Sudoku, and the classic interview problem this lesson works through end to end: N-Queens.

The Try, Check, Undo Pattern

Every backtracking solution follows the same three-step shape at each level of recursion:

• Try: make a choice — place a queen, pick a number, include an element.
• Check: recurse into the rest of the problem with that choice in place. If the recursive call finds a full valid solution, record it (or return, depending on whether you want one answer or all of them).
• Undo: before trying the next choice at this level, remove the choice you just made, restoring the state to what it was before you tried it. This is the step people forget, and it's the one that makes backtracking work — without it, choices from an abandoned branch leak into the next branch you try.

Worked Example: N-Queens

The problem: place N queens on an N x N chessboard so that no two queens attack each other — no two queens share a row, a column, or a diagonal. We'll place one queen per row, working row by row from the top, and at each row try every column until one doesn't conflict with any queen already placed above it.

import java.util.ArrayList;
import java.util.List;

public class NQueens {

    // cols[row] = column index of the queen placed in that row (-1 = not placed yet)
    public static List<int[]> solve(int n) {
        List<int[]> solutions = new ArrayList<>();
        int[] cols = new int[n];
        place(0, n, cols, solutions);
        return solutions;
    }

    private static void place(int row, int n, int[] cols, List<int[]> solutions) {
        if (row == n) {
            solutions.add(cols.clone());  // base case: every row has a queen -> full solution
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, cols)) {
                cols[row] = col;                  // TRY: place the queen
                place(row + 1, n, cols, solutions); // CHECK: recurse to the next row
                cols[row] = -1;                   // UNDO: remove it before trying the next column
            }
        }
    }

    // A new queen at (row, col) is safe if no earlier-placed queen shares
    // its column, or either diagonal.
    private static boolean isSafe(int row, int col, int[] cols) {
        for (int r = 0; r < row; r++) {
            int c = cols[r];
            if (c == col) {
                return false;                 // same column
            }
            if (Math.abs(c - col) == Math.abs(r - row)) {
                return false;                 // same diagonal (row diff == col diff)
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<int[]> solutions = solve(4);
        System.out.println(solutions.size()); // 2 solutions for a 4x4 board
    }
}

Tracing solve(4): the search tries queen at (0,0), then looks for a safe column in row 1. Columns 0 and 1 conflict (column/diagonal), so it tries (1,2). Now row 2 has no safe column at all (every column conflicts with one of the two placed queens) — the for loop in place(2, ...) finds nothing safe and simply returns without recursing further. Control unwinds back to row 1, which undoes (1,2) and tries (1,3) instead. That eventually leads to the first full solution, [1, 3, 0, 2] (queen in row 0 at column 1, row 1 at column 3, row 2 at column 0, row 3 at column 2). The loop in row 0 then also undoes its own choice and tries column 1, which — by symmetry — finds the second solution, [2, 0, 3, 1].

Time complexity: O(N!) in the worst case — the first queen has N column choices, the second has at most N−1 remaining, and so on, before pruning is even considered; pruning cuts this enormously in practice but the bound without deeper analysis (like the closed-form counting used in optimized solvers) is still factorial. Space complexity: O(N) — the cols array and the recursion depth are both bounded by the number of rows.

Pruning: The Reason Backtracking Is Usable At All

Look again at isSafe() — it's called before placing a queen, not after finishing the whole board. That's pruning: reject a bad choice the moment it's known to be bad, instead of continuing to build on it and discovering the failure much later (or never, if you forgot to check at all and just generated every full arrangement and filtered afterward).

The Same Pattern, More Generally

N-Queens is one instance of a shape that covers a large family of interview problems: