Leetcode - N-Queens II Solution | Fajar Maulana Firdaus

In the classic N-Queens problem, we find all board configurations for placing n queens. But what if we only need to count the solutions, not build them? That's N-Queens II, a simpler variation that lets us focus purely on counting.

This problem is perfect for exploring optimization techniques because we don't need to construct boards. We can focus entirely on making the validation and counting as fast as possible.

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: There are exactly two distinct solutions for a 4x4 board

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." But with n = 8, there are 64 positions for the first queen, 63 for the second, and so on. That's way too many combinations to check.

Then I realized something important: since each queen must be in a different row, I can place exactly one queen per row. This reduces the problem significantly. Now I just need to figure out which column to place each queen in.

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

Here's where the real optimization comes in. Instead of maintaining a 2D board and checking it every time, I can use sets to track which columns and diagonals are already occupied.

The key insight is understanding how diagonals work:

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

Let me trace through n = 4 to show how the backtracking works:

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...
Eventually find that starting with (0, 0) leads to valid solutions
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.

The Ultimate Optimization: Bitmasking

Now here's where it gets really interesting. While the set-based solution is good, we can push it even further with bitmasking. Instead of using Set objects, we can use integers and bitwise operations, which are incredibly fast at the CPU level.

The insight is that we can represent columns and diagonals as binary numbers. Each bit represents whether that column or diagonal is occupied. For example, if we have n = 4 and columns 0 and 2 are occupied, we can represent this as binary 0101 or decimal 5.

Here's what clicked for me: bitwise operations like AND, OR, and NOT are lightning fast, and we can use them to check and update our state.

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

Understanding the Bitmasking Magic

Let me break down the key bitwise operations:

(1 << n) - 1: Creates a mask with n bits set to 1. For n = 4, this is 1111 in binary (15 in decimal).
cols | posDiag | negDiag: Combines all occupied positions using OR. If any bit is 1 in any of these, it's 1 in the result.
~(cols | posDiag | negDiag): Inverts the bits using NOT. Now 1 means available, 0 means occupied.
availablePositions & -availablePositions: This clever trick isolates the rightmost set bit. For example, if availablePositions is 1010, this gives us 0010.
(posDiag | position) << 1: After placing a queen, we shift the positive diagonal left because as we move down a row, the diagonal shifts left.
(negDiag | position) >> 1: Similarly, we shift the negative diagonal right.

Here's a trace for n = 4, row 0, trying position 0 (represented as bit 0001):

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

Let me compare all three approaches:

Approach	Time Complexity	Space Complexity	Practical Speed	Code Complexity
Naive (2D board)	O(n!)	O(n²)	Slowest	Low
Set-based	O(n!)	O(n)	Fast	Medium
Bitmasking	O(n!)	O(n)	Fastest	High

Why Bitmasking Is Fastest:

Even though all three have the same asymptotic time complexity of O(n!), bitmasking is significantly faster in practice because:

CPU-level operations: Bitwise operations are primitive CPU instructions, much faster than Set lookups or array access
Cache efficiency: Working with integers is more cache-friendly than Set objects
Less overhead: No hash table operations, no object allocation
Compact state: Entire state fits in a few integers instead of multiple data structures

For n = 8, bitmasking can be 2-3 times faster than the set-based approach.

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 uses the least memory overall since it only needs a few integers

The key improvement over the naive approach is using O(1) conflict checking instead of O(n) board scanning.

Common Pitfalls

When implementing this solution, watch out for:

Diagonal formulas: Make sure you understand why row + col and row - col uniquely identify diagonals. Draw it out if needed.
Backtracking cleanup: Always remove the queen from sets after recursing. Forgetting this will give wrong results.
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.
Set operations: Remember to use add() and delete() for Sets, not array operations.
Bitmasking bit shifts: When using bitmasking, remember that positive diagonals shift left (<<) and negative diagonals shift right (>>) as we move down rows. Getting these backwards will give incorrect results.
Integer overflow: For very large n (though the constraint is n <= 9), be aware that JavaScript numbers are 64-bit floats, but bitwise operations work with 32-bit integers. This isn't an issue for n <= 9.
Rightmost bit extraction: The trick availablePositions & -availablePositions relies on two's complement representation. In JavaScript, this works correctly, but understanding why helps avoid bugs.

Key Takeaways

Backtracking is perfect for constraint satisfaction problems like N-Queens
Reducing the search space is crucial: placing one queen per row eliminates many invalid states
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 takes optimization to the next level by using CPU-level operations
Same algorithmic complexity can have vastly different practical performance
For competitive programming, bitmasking is often the difference between passing and timing out
Progressive optimization: start with a working solution, then optimize based on bottlenecks
Understanding bit manipulation opens up a whole category of ultra-fast solutions

This problem really shows the beauty of optimization. We went from a simple 2D board approach to sets to bitmasking, each step improving performance while maintaining correctness. The difference between checking a 2D board, using sets, and using bitwise operations might seem small on paper, but it compounds significantly with each recursive call. For n = 8, the bitmasking solution can solve the problem in under a millisecond, while the naive approach might take several milliseconds or more.

The journey from understanding the problem to implementing the most optimized solution teaches us that there are often multiple levels of optimization possible, and knowing when to use each technique is part of becoming a better programmer.

Leetcode - N-Queens II Solution