Leetcode - N-Queens Solution

The N-Queens puzzle is a classic backtracking problem where we need to find all possible ways to place n queens on an n x n chessboard so that no two queens attack each other. What makes this interesting is that we need to return the actual board configurations, not just count them.

The challenge is finding an elegant way to track queen positions, validate placements, and construct the output boards efficiently.

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 any piece in the same row, column, or diagonal.

Given an integer n, we need to return all distinct solutions to the puzzle. Each solution should be a board configuration where:

• 'Q' represents a queen
• '.' represents an empty space

Here are the constraints:

• 1 <= n <= 9
• We must return all distinct solutions

Example 1:

• Input: n = 4
• Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
• Explanation: There are exactly two distinct solutions for a 4x4 board

Example 2:

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

A Clean, Elegant Solution

Here's a beautifully simple approach that hits the sweet spot between clarity and efficiency:

function solveNQueens(n) {
  const result = [];
  const queens = new Array(n).fill(0);

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      // Check if same column or same diagonal
      if (
        queens[r] === col ||
        Math.abs(queens[r] - col) === Math.abs(r - row)
      ) {
        return false;
      }
    }
    return true;
  }

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        queens[row] = col;
        backtrack(row + 1);
        queens[row] = 0; // Backtrack
      }
    }
  }

  backtrack(0);
  return result;
}

// Example usage:
console.log(solveNQueens(4));
// Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

This solution is clean, efficient, and easy to understand. For n <= 9, this is absolutely production-ready.

How It Works

Let me trace through n = 4 to show how we build the first solution:

Starting with row 0:

• Try col 0: isSafe returns true (no previous queens)
• queens = [0, 0, 0, 0] with queens[0] = 0

Move to row 1:

• Try col 0: Not safe (same column as row 0)
• Try col 1: Not safe (diagonal: |0-1| = |0-1| is true)
• Try col 2: Safe!
• queens = [0, 2, 0, 0]

Move to row 2:

• Try col 0: Not safe (same column as row 0)
• Try col 1: Not safe (diagonal with row 1: |2-1| = |1-2| is true)
• Try col 2: Not safe (same column as row 1)
• Try col 3: Not safe (diagonal with row 1: |2-1| = |3-2| is true)
• Backtrack to row 1

Continue this process until we find all valid configurations.

When we complete a solution with queens = [1, 3, 0, 2], we convert it to:

[".Q..", "...Q", "Q...", "..Q."]

The Set Optimization Approach

If we want to optimize the validation from O(n) to O(1), we can use sets to track occupied columns and diagonals:

function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const posDiag = new Set(); // row + col
  const negDiag = new Set(); // row - col
  const queens = [];

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
        continue;
      }

      // Place queen
      queens.push(col);
      cols.add(col);
      posDiag.add(row + col);
      negDiag.add(row - col);

      backtrack(row + 1);

      // Backtrack
      queens.pop();
      cols.delete(col);
      posDiag.delete(row + col);
      negDiag.delete(row - col);
    }
  }

  backtrack(0);
  return result;
}

This approach trades some code complexity for O(1) validation checks instead of O(n).

The Ultimate Optimization: Bitmasking

For maximum performance, we can use bitmasking. This combines ultra-fast validation with efficient board construction:

function solveNQueensBitmasking(n) {
  const result = [];
  const queens = [];

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row, cols, posDiag, negDiag) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    // Find available positions using bitwise operations
    let availablePositions = ((1 << n) - 1) & ~(cols | posDiag | negDiag);

    while (availablePositions) {
      // Extract rightmost available position
      const position = availablePositions & -availablePositions;
      availablePositions -= position;

      // Convert bit position to column index
      const col = Math.log2(position);
      queens.push(col);

      backtrack(
        row + 1,
        cols | position,
        (posDiag | position) << 1,
        (negDiag | position) >> 1
      );

      queens.pop();
    }
  }

  backtrack(0, 0, 0, 0);
  return result;
}

Performance Comparison

Approach	Validation	Code Clarity	Best For
Clean array-based	O(n) per check	Highest	Interviews, production
Set-based	O(1) per check	High	Performance-focused code
Bitmasking	O(1) per check	Medium	Competitive programming

My recommendation: The clean array-based solution is perfect for most cases. It's easy to understand, easy to explain in interviews, and fast enough for n <= 9.

Common Pitfalls

When implementing this solution, watch out for:

1. Board format: Remember that each row is a string, not an array of characters. The output is an array of strings.

2. Deep copying: When adding a solution to results, make sure to create a new board. Calling buildBoard() creates new strings each time.

3. Backtracking cleanup: Always undo all changes when backtracking. For the array approach, reset queens[row] = 0. For the set approach, remove from all sets.

4. Diagonal validation: The formula Math.abs(queens[r] - col) === Math.abs(r - row) checks both diagonals in one condition.

5. Off-by-one errors: When building strings with .repeat(), make sure the math is correct: .repeat(col) + 'Q' + .repeat(n - col - 1) gives exactly n characters.

Key Takeaways

• The array-based approach with isSafe is clean, simple, and perfect for interviews
• Using queens[row] = col to track positions is more memory-efficient than a 2D board
• The diagonal check formula Math.abs(row1 - row2) === Math.abs(col1 - col2) is elegant
• For n <= 9, code clarity should be prioritized over micro-optimizations
• Sets provide O(1) validation if you need extra performance
• Bitmasking is fastest but adds complexity, use only when necessary
• Building boards only for complete solutions is more efficient than maintaining a full board state

This problem teaches us that sometimes the simplest solution is the best solution. The clean array-based approach is easy to understand, easy to verify for correctness, and performs excellently for the given constraints.