Count Valid N-Queens Placements

hard backtracking bitmask

Problem

Return the number of ways to place n queens on an n × n board so that no two attack each other. Two queens attack iff they share a row, a column, or a diagonal.

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;
}

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