N-Queens II

Share

The N-Queens puzzle is placing n queens on an n×n chessboard so no two queens attack each other. Return the number of distinct solutions.

Example 1
Input: n = 4 → Output: 2
Example 2
Input: n = 1 → Output: 1

Solution Approach

Same backtracking as N-Queens but only count solutions instead of building board strings. Track occupied columns and diagonals using three boolean arrays.

  • Use three boolean arrays: cols[], diag1[] (row-col+n), diag2[] (row+col).
  • At each row, try placing a queen in each column if not under attack.
  • Mark the column and diagonals, recurse to next row, then unmark.
  • Increment counter when all n rows are filled.
Java
class Solution {
    int count = 0;

    public int totalNQueens(int n) {
        backtrack(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
        return count;
    }

    private void backtrack(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        if (row == n) { count++; return; }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n, d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            cols[col] = diag1[d1] = diag2[d2] = true;
            backtrack(n, row + 1, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
}
  • Time Complexity: O(N!) with pruning
  • Space Complexity: O(N). Boolean arrays + stack