Count the ways to place N queens on an N by N board so that no two attack each other.

One queen per row, settled before any code

Say out loud that the board has N rows, you are placing N queens, and no two queens may share a row, so every row holds exactly one queen. That single observation turns a search over which squares to occupy into a sequence of N choices of column, and it is the difference between a search you can reason about and one you cannot.

It also fixes the shape of the recursion. You recurse on the row index; the base case is reaching row N, at which point every row already holds a legal queen and you increment the count. There is no board check at the base case. If placement was guarded on the way down, arriving at row N is itself the proof of legality.

The two diagonals are sums and differences

Rows and columns are easy. Diagonals are where implementations go wrong, because a diagonal has to be named by something you can put in a set or use as an array index.

Two squares lie on the same anti-diagonal, running top-right to bottom-left, exactly when their row and column sum to the same value. That sum runs from 0 to 2N minus 2, giving 2N minus 1 distinct anti-diagonals. Two squares lie on the same main diagonal, running top-left to bottom-right, exactly when their row minus their column is equal. That difference also takes 2N minus 1 distinct values, from the negative of N minus 1 up to N minus 1, but now it includes negatives.

Hash sets do not care about negative keys. Boolean arrays, which is what you want here, do. The difference must be shifted into range by adding N minus 1. The shortcut that looks equivalent is to index by the absolute value of the difference instead, and it is not equivalent: it merges the diagonal at plus k with the diagonal at minus k, so legal placements are rejected because some queen occupies the mirror diagonal.

What the absolute value costs you, on a 4 by 4 board

The 4 by 4 board has exactly two solutions. Written as the column each row uses, in row order, they are 1, 3, 0, 2 and 2, 0, 3, 1.

Take the first. Its queens sit at row-column pairs 0-1, 1-3, 2-0 and 3-2, so the differences are minus 1, minus 2, plus 2 and plus 1. Under an absolute value, the queen at 0-1 marks diagonal 1 as used, and the queen at 3-2 is then rejected — even though those two squares are three rows and one column apart and cannot attack one another. The second solution fails identically: its differences are minus 2, plus 1, minus 1 and plus 2.

So a solver that indexes diagonals by absolute difference returns zero for N equals 4, and zero for N equals 8, where the true count is 92. That is the useful thing about this defect in an interview: it does not produce a slightly wrong number, it collapses the answer to zero, and anyone who runs their code on N equals 4 and sees 2 has already ruled it out.

int solve(int n) {
    return place(0, n, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
}

private int place(int row, int n, boolean[] col, boolean[] sum, boolean[] diff) {
    if (row == n) return 1;                 // every row placed, so this is a solution
    int found = 0;
    for (int c = 0; c < n; c++) {
        int s = row + c;
        int d = row - c + n - 1;            // shifted, not abs: +k and -k must stay distinct
        if (col[c] || sum[s] || diff[d]) continue;
        col[c] = sum[s] = diff[d] = true;
        found += place(row + 1, n, col, sum, diff);
        col[c] = sum[s] = diff[d] = false;  // undo on the way out
    }
    return found;
}

Pruning on the way down, not checking at the leaf

A candidate who enumerates every arrangement of one queen per row and validates each completed board is doing factorial work with a quadratic check at every leaf. Guarding the placement instead means a partial board that already contains a conflict is never extended, and entire subtrees disappear. For N equals 8 that is the difference between finishing on a whiteboard and not.

The discipline that goes with it is the undo. Every mark set before the recursive call must be cleared after it, and the reliable way to get this right is to write the set and the clear as adjacent lines and then fill in the middle. Mutating three shared arrays and forgetting to restore one is the second most common defect here, and unlike the diagonal bug it yields a count that is merely too small, which is far harder to notice.

What the cost is, and what it is not

The defensible statement about complexity is that the search is bounded above by N factorial, since that is how many column assignments survive the row and column constraints alone, and the diagonal constraints cut it well below that in practice. The number of solutions has no known closed form and no algorithm is known that counts them in polynomial time. Say that, rather than inventing a bound; an interviewer asking this question knows the answer and is watching whether you will fabricate one.

Space is O(N) for the three constraint arrays plus O(N) of recursion depth, which is why the whole thing fits comfortably in cache even at board sizes where the running time is hopeless. The bitmask variant replaces the arrays with three integers and the column loop with repeatedly extracting the lowest set bit of the available mask. It is materially faster and changes nothing about the asymptotics or the correctness argument, which is exactly why it makes a good follow-up.