Blind Plus 100 Visualized

#88 · Backtracking

N-Queens

Place n queens on an n × n chessboard so that no two queens attack each other, and return all distinct board configurations ("Q" for a queen, "." for an empty square).

HardLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Placement array (one column per row)

Since each row holds exactly one queen, a board is fully described by cols[r], the column of the queen in row r. This rules out row conflicts by construction and shrinks the search from n² squares to n choices per row.

Memory layout

An array of n small integers; the recursion depth is n.

OperationCost
search spaceat most n! arrangements before pruning

Column and diagonal sets

A queen at (r, c) attacks column c, the "\" diagonal r − c and the "/" diagonal r + c. Three hash sets (or boolean arrays) answer "is this square attacked?" in O(1).

Memory layout

Boolean arrays of size n, 2n − 1 and 2n − 1.

OperationCost
test / add / removeO(1)

Bitmask state

Pack each of the three sets into one integer. The free squares of a row are full & ~(colMask | diagMask | antiMask); the diagonal masks shift one bit per row, so the state passed to the next row is three integers.

Memory layout

Three machine words passed through the recursion; no allocation.

OperationCost
free squaresO(1) with bit operations
next free squareO(1) with free & −free

Why it fits

  • Backtracking fits because partial boards can be rejected as soon as two queens clash; most of the n^n raw placements are never explored.
  • Placing exactly one queen per row makes row conflicts impossible and gives a natural recursion over rows.
  • Bitmasks turn the three attack tests into word-parallel operations and let the loop visit only free squares, which is why the fastest known simple solvers use them.

Why alternatives degrade

Trying all C(n², n) placements:
For n = 8 that is about 4.4 billion boards, far too many to enumerate.
Greedy placement:
A locally safe square can lead to a dead end; without undoing earlier choices (backtracking) solutions are missed.
Constraint solver / DLX:
Correct but heavier than needed; simple backtracking with masks is already fast for n ≤ 12.

Four approaches, from naive to production

1 · beginner

Row by row, scan earlier queens

time O(n! · n)space O(n)

Place one queen per row. For each column in the row, check every earlier queen for a shared column or diagonal; if safe, place and recurse, then remove the queen (backtrack).

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> cols;
    auto isSafe = [&](int row, int col) -> bool {
        for (int r = 0; r < row; r++) {
            int c = cols[r];
            if (c == col || abs(c - col) == row - r) return false;
        }
        return true;
    };
    function<void(int)> place = [&](int row) {
        if (row == n) {
            vector<string> board;
            for (int c : cols) board.push_back(string(c, '.') + 'Q' + string(n - c - 1, '.'));
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!isSafe(row, col)) continue;
            cols.push_back(col);
            place(row + 1);
            cols.pop_back();
        }
    };
    place(0);
    return result;
}

Flaws & bottlenecks

  • Every safety test scans all earlier rows: O(n) per square.
  • Builds each board string at the leaves, which costs O(n²) per solution.
  • Exponential: n! growth bounds the pruned search.

Interviewer cross-questions

Why one queen per row?

Say: Two queens in one row attack each other, so a valid board has exactly one queen in every row; this also removes the row check from the safety test.

How do you test the diagonal?

Say: Two squares share a diagonal when |row₁ − row₂| equals |col₁ − col₂|.

How can the safety check become O(1)?

Say: Record used columns and the diagonals r − c and r + c in sets or arrays.

2 · intermediate

Column and diagonal sets

time O(n!)space O(n)

Track used columns, "\" diagonals (row − col) and "/" diagonals (row + col) in three sets. A square is safe when none of its three keys is in use; place, recurse, then release the keys.

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> cols;
    set<int> usedCol, usedDiag, usedAnti;
    function<void(int)> place = [&](int row) {
        if (row == n) {
            vector<string> board;
            for (int c : cols) board.push_back(string(c, '.') + 'Q' + string(n - c - 1, '.'));
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (usedCol.count(col) || usedDiag.count(row - col) || usedAnti.count(row + col)) continue;
            usedCol.insert(col); usedDiag.insert(row - col); usedAnti.insert(row + col);
            cols.push_back(col);
            place(row + 1);
            cols.pop_back();
            usedCol.erase(col); usedDiag.erase(row - col); usedAnti.erase(row + col);
        }
    };
    place(0);
    return result;
}

Flaws & bottlenecks

  • Still examines every column of every row, including attacked ones.
  • Hash sets add overhead; fixed boolean arrays would be faster.
  • Remember to undo all three sets on backtracking.

Interviewer cross-questions

Why do squares on a diagonal share row − col?

Say: Moving one step down-right adds 1 to both row and col, so their difference is unchanged; the other diagonal keeps row + col fixed.

How many diagonals are there?

Say: 2n − 1 in each direction, so index arrays by row − col + n − 1 and row + col.

Can you skip attacked columns without testing them?

Say: Yes: with bitmasks the free squares are computed at once and the loop touches only those.

3 · advanced

Bitmask backtracking

time O(n!) worst case, far less in practicespace O(n)

Keep three bitmasks of attacked squares for the current row. free = full & ~(colMask | diagMask | antiMask); take the lowest set bit as the next column, and pass shifted masks to the next row.

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> cols;
    int full = (1 << n) - 1;
    function<void(int, int, int, int)> place = [&](int row, int colMask, int diagMask, int antiMask) {
        if (row == n) {
            vector<string> board;
            for (int c : cols) board.push_back(string(c, '.') + 'Q' + string(n - c - 1, '.'));
            result.push_back(board);
            return;
        }
        int free = full & ~(colMask | diagMask | antiMask);
        while (free != 0) {
            int bit = free & -free;
            free ^= bit;
            int col = __builtin_ctz(bit);
            cols.push_back(col);
            place(row + 1, colMask | bit, ((diagMask | bit) << 1) & full, (antiMask | bit) >> 1);
            cols.pop_back();
        }
    };
    place(0, 0, 0, 0);
    return result;
}

Flaws & bottlenecks

  • Limited to n ≤ 31 or 63 by the integer width (fine, since n beyond ~15 is infeasible anyway).
  • The shifting of the diagonal masks is subtle and needs a diagram.
  • Still builds boards from the cols array when a solution is found.

Interviewer cross-questions

Why does the diagonal mask shift left and the anti-diagonal mask right?

Say: Going one row down, a "\" diagonal moves one column to the right and a "/" diagonal moves one column to the left, so the attacked bits move accordingly.

What does free & -free do?

Say: It isolates the lowest set bit (two's complement trick), giving the next free square in O(1).

If only the COUNT of solutions were needed?

Say: Drop the cols array and board building and just count leaves; this is the classic fast solver for n up to about 15.

4 · expert

Bitmasks with mirror symmetry

time O(n!) with about half the workspace O(n)

Reflect the board left to right: a solution with its first queen in the left half has a mirror twin with the first queen in the right half. Search only the left half of row 0 and emit both boards; for odd n search the middle column separately.

vector<vector<string>> solveNQueens(int n) {
    if (n <= 0) return {};
    vector<vector<string>> result;
    vector<int> cols(n, 0);
    int full = (1 << n) - 1;
    auto draw = [&](bool mirror) {
        vector<string> board;
        for (int c : cols) { int q = mirror ? n - 1 - c : c; board.push_back(string(q, '.') + 'Q' + string(n - q - 1, '.')); }
        return board;
    };
    function<void(int, int, int, int, bool)> place = [&](int row, int colMask, int diagMask, int antiMask, bool mirrored) {
        if (row == n) {
            result.push_back(draw(false));
            if (mirrored) result.push_back(draw(true));
            return;
        }
        int free = full & ~(colMask | diagMask | antiMask);
        if (row == 0) free &= (1 << (n >> 1)) - 1;
        while (free != 0) {
            int bit = free & -free;
            free ^= bit;
            cols[row] = __builtin_ctz(bit);
            place(row + 1, colMask | bit, ((diagMask | bit) << 1) & full, (antiMask | bit) >> 1, mirrored || row == 0);
        }
    };
    place(0, 0, 0, 0, false);
    if (n & 1) {
        int bit = 1 << (n >> 1);
        cols[0] = n >> 1;
        place(1, bit, (bit << 1) & full, bit >> 1, false);
    }
    return result;
}

Flaws & bottlenecks

  • More code and special cases (odd n, middle column).
  • Output order differs from the plain search (the problem allows any order).
  • Symmetry only halves the work; larger savings need rotations and reflections (up to 8×) with canonical forms.

Interviewer cross-questions

Why is the middle column handled separately for odd n?

Say: A solution with the first queen in the middle column mirrors to another board that also has it there, so you cannot assume the twin lies outside the explored half.

Is a solution ever its own mirror image?

Say: Only when the board is left-right symmetric, which is impossible for n ≥ 2 because the queen in a row would need to sit at both c and n − 1 − c; so twins are always distinct for the left half.

What are the edge cases?

Say: n = 1 returns one board ("Q"); n = 2 and n = 3 return none; n ≤ 0 returns an empty list.

Synchronized code walkthrough

Showing: Row by row, scan earlier queens — shares the player above; click any step to jump.

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> cols;
    auto isSafe = [&](int row, int col) -> bool {
        for (int r = 0; r < row; r++) {
            int c = cols[r];
            if (c == col || abs(c - col) == row - r) return false;
        }
        return true;
    };
    function<void(int)> place = [&](int row) {
        if (row == n) {
            vector<string> board;
            for (int c : cols) board.push_back(string(c, '.') + 'Q' + string(n - c - 1, '.'));
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!isSafe(row, col)) continue;
            cols.push_back(col);
            place(row + 1);
            cols.pop_back();
        }
    };
    place(0);
    return result;
}