N-Queens II

hard backtracking bitmask

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Place one queen per row in turn. Track three bitmasks: cols (columns occupied), d1 (↘ diagonals = col − row + offset), and d2 (↙ diagonals = col + row). On row r, candidate columns are those bits not set in cols | d1 | d2. For each candidate, set its bits, recurse on row r + 1, then clear them. Increment the counter when r == n.

Inputn = 4

Output2

The two solutions for 4-queens — placements (1,0,3,2) and (2,3,0,1) reading row-by-row column.

def total_n_queens(n):
    count = 0
    def back(r, cols, d1, d2):
        nonlocal count
        if r == n:
            count += 1; return
        free = ((1 << n) - 1) & ~(cols | d1 | d2)
        while free:
            bit = free & -free
            free ^= bit
            back(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1)
    back(0, 0, 0, 0)
    return count

function totalNQueens(n) {
  let count = 0;
  function back(r, cols, d1, d2) {
    if (r === n) { count++; return; }
    let free = ((1 << n) - 1) & ~(cols | d1 | d2);
    while (free) {
      const bit = free & -free;
      free ^= bit;
      back(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
    }
  }
  back(0, 0, 0, 0);
  return count;
}

int count = 0;
public int totalNQueens(int n) {
    back(0, 0, 0, 0, n);
    return count;
}
void back(int r, int cols, int d1, int d2, int n) {
    if (r == n) { count++; return; }
    int free = ((1 << n) - 1) & ~(cols | d1 | d2);
    while (free != 0) {
        int bit = free & -free;
        free ^= bit;
        back(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n);
    }
}

int count = 0;
void back(int r, int cols, int d1, int d2, int n) {
    if (r == n) { count++; return; }
    int free = ((1 << n) - 1) & ~(cols | d1 | d2);
    while (free) {
        int bit = free & -free;
        free ^= bit;
        back(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n);
    }
}
int totalNQueens(int n) {
    back(0, 0, 0, 0, n);
    return count;
}

Explanation

We place one queen per row and just count how many complete, non-attacking arrangements exist. The fast version uses three bitmasks to track which columns and diagonals are already under attack, so each safety check is a single bit operation.

cols marks occupied columns, d1 marks the "↘" diagonals, and d2 marks the "↙" diagonals. On a given row, the safe columns are exactly the bits not set in cols | d1 | d2. The line free = ((1 << n) - 1) & ~(cols | d1 | d2) computes that set in one step.

We then pick safe columns one at a time. The idiom bit = free & -free grabs the lowest set bit (one candidate column). We recurse to the next row with the masks updated, shifting the diagonal masks ((d1 | bit) << 1 and (d2 | bit) >> 1) so they line up correctly for the new row.

When r == n every row has a safe queen, so we do count++. For n = 4 the search finds exactly 2 valid placements.

Because impossible columns are filtered out instantly by the masks, the search prunes hard and only the valid arrangements reach the bottom.

Time: O(n!) Space: O(n) recursion