N-Queens

How it works

This is the most optimized backtracking approach for the N-Queens problem.

Instead of using arrays or hash sets to track occupied columns and diagonals, we use bit masks (integers).
Each bit represents whether a column or diagonal is already occupied.

Why this works well:

• Integers allow O(1) checks using bitwise operations
• Uses very little memory
• Faster than arrays/sets in practice

For a queen placed at position (row, col):

• Column mask → bit col
• Positive diagonal (/) → bit (row + col)
• Negative diagonal (\) → bit (row - col + n)

If any of these bits are already set, placing a queen there causes a conflict.

We still place queens row by row, but conflict checks are done using bitwise AND.

Steps

1. Initialize three integers (bit masks):
   • col → tracks used columns
   • posDiag → tracks row + col
   • negDiag → tracks row - col + n
2. Initialize an empty n x n board filled with ".".
3. Start backtracking from row 0.
4. For each c (column) in the current r (row):
   • Check conflicts using bitwise AND:
     • col & (1 << c)
     • posDiag & (1 << (r + c))
     • negDiag & (1 << (r - c + n))
   • If any is set → skip
5. If safe:
   • Set bits using XOR (^=) to mark column and diagonals
   • Place "Q" at (r, c)
   • Recurse to row r + 1
6. If r == n:
   • Convert the board to string format and save it
7. Backtrack:
   • Remove the queen
   • Toggle the same bits back using XOR
8. Continue until all valid boards are generated.

Complexity

• Time complexity: O(n!)
• Space complexity: O(n ^ 2)

Things to watch for

Checking Only Columns and Forgetting Diagonals

A frequent mistake is checking only whether a column is occupied while neglecting diagonal conflicts. Queens attack along both diagonals, so you must verify the upper-left diagonal (where row - col is constant) and the upper-right diagonal (where row + col is constant). Missing either diagonal check will produce invalid board configurations.

Incorrect Diagonal Index Calculation

When using arrays to track diagonal occupancy, the negative diagonal row - col can produce negative indices. You must offset this value by adding n (i.e., use row - col + n) to ensure valid array indices. Forgetting this offset causes array index out of bounds errors or incorrect diagonal tracking.

Forgetting to Backtrack State

After recursively exploring a placement and returning, you must undo the state changes (remove the queen from sets/arrays and reset the board position to "."). Failing to properly backtrack leaves stale state that incorrectly blocks future valid placements, causing the algorithm to miss valid solutions.

Scanning Below Current Row in Safety Check

Since queens are placed row by row from top to bottom, only rows above the current row can contain previously placed queens. A common error is scanning the entire column or both diagonal directions (up and down). This is wasteful at best and can cause incorrect behavior if the board is not properly initialized. Only check upward directions: the column above, upper-left diagonal, and upper-right diagonal.

Not Creating a Deep Copy of the Board When Saving Solutions

When a valid configuration is found, you must create a copy of the board before adding it to the results. Simply appending a reference to the same board object means all stored solutions will reflect subsequent modifications during backtracking. Always convert each row to a new string and create a fresh list for each solution.

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = 0
        posDiag = 0
        negDiag = 0
        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            nonlocal col, posDiag, negDiag
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return
            for c in range(n):
                if ((col & (1 << c)) or (posDiag & (1 << (r + c)))
                    or (negDiag & (1 << (r - c + n)))):
                    continue
                col ^= (1 << c)
                posDiag ^= (1 << (r + c))
                negDiag ^= (1 << (r - c + n))
                board[r][c] = "Q"

                backtrack(r + 1)

                col ^= (1 << c)
                posDiag ^= (1 << (r + c))
                negDiag ^= (1 << (r - c + n))
                board[r][c] = "."

        backtrack(0)
        return res

class Solution {
public:
    int col = 0, posDiag = 0, negDiag = 0;
    vector<string> board;
    vector<vector<string>> res;

    vector<vector<string>> solveNQueens(int n) {
        board.resize(n, string(n, '.'));

        backtrack(0, n);
        return res;
    }

    void backtrack(int r, int n) {
        if (r == n) {
            res.push_back(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if ((col & (1 << c)) || (posDiag & (1 << (r + c)))
                 || (negDiag & (1 << (r - c + n)))) {
                continue;
            }
            col ^= (1 << c);
            posDiag ^= (1 << (r + c));
            negDiag ^= (1 << (r - c + n));
            board[r][c] = 'Q';

            backtrack(r + 1, n);

            col ^= (1 << c);
            posDiag ^= (1 << (r + c));
            negDiag ^= (1 << (r - c + n));
            board[r][c] = '.';
        }
    }
};