Leetcode - N-Queens Solution

The N Queens puzzle asks for all valid placements of n queens on an n x n chessboard. No two queens can attack each other. The result returns board configurations rather than only a count.

The challenge is tracking queen positions, validating placements, and constructing 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: A 4x4 board has exactly two distinct solutions

Example 2:

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

Array based solution

The array based approach keeps the validation logic explicit:

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 easy to inspect. For n <= 9, it fits the constraints in the problem statement.

How It Works

For n = 4, the search first tries this branch:

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).

Bitmasking

Bitmasking represents occupied columns and diagonals as bits, allowing constant time validation:

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

My recommendation: The array based solution is a practical default for n <= 9. It is easy to explain in interviews and fits the stated constraints.

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.

Choosing an implementation

• The array based approach with isSafe is simple and suitable for interviews
• Store one column per row and build boards only for complete solutions
• The diagonal formula checks both diagonals, while sets provide O(1) validation
• Bitmasking reduces bookkeeping but adds complexity, so use it only when needed

The array based approach is easy to verify and meets the given constraints.