Leetcode - N-Queens II Solution

The classic N Queens problem returns board configurations. N Queens II only counts valid placements, so it avoids constructing boards.

Because boards are not constructed, this version lets us compare different validation and counting strategies.

Understanding the Problem

The n queens puzzle asks us to place n queens on an n x n chessboard such that no two queens can attack each other. A queen can attack horizontally, vertically, and diagonally.

Given an integer n, we need to return the number of distinct solutions to this puzzle.

Here are the constraints:

• 1 <= n <= 9
• We only need to count the solutions, not generate them

Example 1:

• Input: n = 4
• Output: 2
• Explanation: A 4x4 board has exactly two distinct solutions

Example 2:

• Input: n = 1
• Output: 1
• Explanation: Only one way to place a single queen

My First Approach

My initial thought was: "I'll just try every possible placement and count the valid ones." A brute force search would examine arrangements of n queen positions across n² squares. This includes placements with multiple queens in one row.

Each queen must be in a different row, so I can place exactly one queen per row. The search then chooses a column for each row.

function totalNQueensNaive(n) {
  let count = 0;
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  
  function isValid(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }
    
    // Check diagonal and anti-diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }
    
    return true;
  }
  
  function backtrack(row) {
    if (row === n) {
      count++;
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.'; // Backtrack
      }
    }
  }
  
  backtrack(0);
  return count;
}

This works, but checking validity with a 2D board is slower than it needs to be.

The Set Optimization Insight

The set based approach avoids maintaining a 2D board. It tracks occupied columns and diagonals directly.

Each diagonal has a constant coordinate sum or difference:

• For a diagonal going from top left to bottom right: all positions share the same value of row - col
• For a diagonal going from top right to bottom left: all positions share the same value of row + col

By tracking these in sets, I can check if a position is valid in constant time instead of linear time.

My Solution

function totalNQueens(n) {
  let count = 0;
  
  // Track which columns and diagonals are occupied
  const cols = new Set();
  const posDiag = new Set(); // row + col is constant
  const negDiag = new Set(); // row - col is constant
  
  function backtrack(row) {
    // Base case: all queens placed successfully
    if (row === n) {
      count++;
      return;
    }
    
    // Try placing queen in each column of current row
    for (let col = 0; col < n; col++) {
      // Check if this position conflicts with any existing queens
      if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
        continue; // Skip this position
      }
      
      // Place queen: mark column and diagonals as occupied
      cols.add(col);
      posDiag.add(row + col);
      negDiag.add(row - col);
      
      // Recurse to next row
      backtrack(row + 1);
      
      // Backtrack: remove queen and free up column and diagonals
      cols.delete(col);
      posDiag.delete(row + col);
      negDiag.delete(row - col);
    }
  }
  
  backtrack(0);
  return count;
}

// Example usage:
console.log(totalNQueens(4)); // Output: 2
console.log(totalNQueens(1)); // Output: 1

How It Works

For n = 4, the backtracking proceeds as follows:

Starting with row 0:

• Try col 0: Place queen at (0, 0). Mark col 0, posDiag 0, negDiag 0
• Move to row 1: Try col 0 (occupied), col 1 (occupied by negDiag), col 2 (valid)
• Place queen at (1, 2). Mark col 2, posDiag 3, negDiag -1
• Continue this process...
• Find that no valid solution starts with (0, 0)
• Backtrack and try (0, 1) as starting position
• Continue until all starting positions are tried

The algorithm systematically explores all possibilities, using the sets to quickly determine if a position is valid without checking the entire board.

Bitmasking

Bitmasking replaces the sets with integers and bitwise operations. Each bit represents an occupied column or diagonal.

The column mask records occupied columns. The diagonal masks record attacked positions in the current row. For n = 4, occupied columns 0 and 2 give a column mask of binary 0101, or decimal 5.

AND, OR, and NOT operations check and update that state as integer masks.

function totalNQueensBitmasking(n) {
  let count = 0;
  
  function backtrack(row, cols, posDiag, negDiag) {
    // Base case: all queens placed
    if (row === n) {
      count++;
      return;
    }
    
    // Calculate available positions for this row
    // Start with all positions (all bits set to 1 for n positions)
    // Then eliminate occupied columns and diagonals using bitwise operations
    let availablePositions = ((1 << n) - 1) & ~(cols | posDiag | negDiag);
    
    // Try each available position
    while (availablePositions) {
      // Get the rightmost bit (rightmost available position)
      const position = availablePositions & -availablePositions;
      
      // Remove this position from available positions
      availablePositions -= position;
      
      // Recurse with updated state
      // cols | position: mark this column as occupied
      // (posDiag | position) << 1: shift positive diagonal left
      // (negDiag | position) >> 1: shift negative diagonal right
      backtrack(
        row + 1,
        cols | position,
        (posDiag | position) << 1,
        (negDiag | position) >> 1
      );
    }
  }
  
  backtrack(0, 0, 0, 0);
  return count;
}

// Example usage:
console.log(totalNQueensBitmasking(4)); // Output: 2
console.log(totalNQueensBitmasking(8)); // Output: 92

Bit operations and diagonal shifts

The key bitwise operations are:

1. (1 << n) - 1: Creates a mask with n bits set to 1. For n = 4, the mask is 1111 in binary (15 in decimal).

2. cols | posDiag | negDiag: Combines all occupied positions using OR. If any bit is 1 in any of these, it is 1 in the result.

3. ~(cols | posDiag | negDiag): Inverts the bits using NOT. Now 1 means available, 0 means occupied.

4. availablePositions & -availablePositions: This expression isolates the rightmost set bit. For example, if availablePositions is 1010, this gives us 0010.

5. (posDiag | position) << 1: After placing a queen, we shift the positive diagonal left because as we move down a row, the diagonal shifts left.

6. (negDiag | position) >> 1: Similarly, we shift the negative diagonal right.

For n = 4, row 0, and position 0 (bit 0001), the state changes as follows:

• Initial: cols = 0000, posDiag = 0000, negDiag = 0000
• Place queen at position 0001
• New cols = 0001
• New posDiag = 0001 shifted left = 0010
• New negDiag = 0001 shifted right = 0000
• For row 1: occupied = 0001 | 0010 | 0000 = 0011
• So positions 0 and 1 are blocked, only positions 2 and 3 are available

Performance Comparison

The three approaches compare as follows:

Why bitmasking can reduce overhead:

The set and bitmask variants keep the O(n!) search bound, while bitmasking stores the per position state in integers:

1. Compact state: The state fits in a few integers instead of multiple data structures
2. No set bookkeeping: The search does not allocate or update Set objects at each position

Space Complexity for All:

• Recursion stack: O(n) for all approaches
• State storage: O(n²) for naive, O(n) for set based and bitmasking
• Bitmasking stores the column and diagonal state in integer masks alongside the recursion stack

The search explores O(n!) placement states. The 2D board version adds an O(n) scan to each safety check, giving an O(n × n!) bound. The set and bitmask variants use O(1) conflict checks and retain the O(n!) bound.

Common Pitfalls

When implementing this solution, watch out for:

1. Diagonal formulas: Make sure you understand why row + col and row - col uniquely identify diagonals. Draw it out if needed.

2. Backtracking cleanup: Always remove the queen from sets after recursing. Forgetting this will give wrong results.

3. Base case: The base case is when row === n, not row === n - 1. We start from row 0, so reaching row n means all n queens are placed.

4. Set operations: Remember to use add() and delete() for Sets, not array operations.

5. Bitmasking bit shifts: For each new row, shift the positive diagonal mask left (<<). Shift the negative diagonal mask right (>>). Getting these backwards will give incorrect results.

6. Integer overflow: JavaScript numbers use floating point representation, but these bitwise operations use 32 bit integers. The constraint n <= 9 keeps the masks within that range.

7. Rightmost bit extraction: The trick availablePositions & -availablePositions relies on two's complement representation. In JavaScript, this works correctly, but understanding why helps avoid bugs.

Choosing a representation

• Backtracking fits constraint satisfaction problems like N Queens, and one queen per row reduces the search space
• Sets can optimize validity checking from O(n) to O(1)
• Understanding the math behind diagonals (row + col and row - col) enables efficient conflict detection
• The backtracking pattern: try a choice, recurse, then undo the choice
• Bitmasking represents the search state as integers and avoids set bookkeeping, at the cost of extra complexity