Pruning: Stop Early on Hopeless Paths

Don't walk into a dead end you can already see

Backtracking tries a lot of paths. Pruning means checking early: if the current partial answer already breaks a rule, stop right there – don't explore anything that grows from it.

The N-Queens puzzle

Place N queens on an N × N chessboard so no two attack each other (same row, column or diagonal). We place one queen per row, and before placing one we check that its column and diagonals are free:

public class Main {
    static int n, solutions = 0;
    static long tries = 0;
    static boolean[] colUsed, diag1, diag2;

    static void place(int row) {
        if (row == n) {
            solutions++;
            return;
        }
        for (int col = 0; col < n; col++) {
            tries++;
            if (colUsed[col] || diag1[row + col] || diag2[row - col + n - 1]) continue;   // prune
            colUsed[col] = diag1[row + col] = diag2[row - col + n - 1] = true;           // choose
            place(row + 1);                                                              // explore
            colUsed[col] = diag1[row + col] = diag2[row - col + n - 1] = false;          // undo
        }
    }

    public static void main(String[] args) {
        for (n = 4; n <= 8; n++) {
            colUsed = new boolean[n];
            diag1 = new boolean[2 * n];
            diag2 = new boolean[2 * n];
            solutions = 0;
            tries = 0;
            place(0);
            System.out.println(n + " queens: " + solutions + " solutions, " + tries + " squares tried");
        }
    }
}

Output

4 queens: 2 solutions, 60 squares tried
5 queens: 10 solutions, 220 squares tried
6 queens: 4 solutions, 894 squares tried
7 queens: 40 solutions, 3584 squares tried
8 queens: 92 solutions, 15720 squares tried

For 8 queens there are over 16 million ways to put one queen in each row, but pruning means we only try about 16,000 squares.

Tip: Every cell on the same ↘ diagonal has the same row − col; every cell on the same ↙ diagonal has the same row + col. That's how two boolean arrays track all diagonals.

Think of it like this: Doing a jigsaw: you don't finish the whole row before noticing the first piece doesn't fit – you put it back immediately.