N-Queens Problem - Complete Guide

Introduction

The N-Queens problem is one of the most famous constraint satisfaction problems in computer science and mathematics. It serves as a classic example to demonstrate the power of Backtracking algorithms. The problem asks us to place N chess queens on an N×N chessboard in such a way that no two queens can attack each other.

Problem Statement

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the queen's placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Constraints

1. No Two Queens Share a Row: Since queens attack along rows, placing more than one queen in a single row is impossible.
2. No Two Queens Share a Column: Similarly, columns must be unique.
3. No Two Queens Share a Diagonal: This is the most complex constraint. Queens attack diagonally if the absolute difference in their row indices equals the absolute difference in their column indices.

Understanding the Attack Vectors

To solve this problem, we must understand how a queen attacks:

1. Horizontal (Row): A queen attacks all squares to its left and right in the same row.
2. Vertical (Column): A queen attacks all squares above and below in the same column.
3. Diagonal: A queen attacks all squares along the two diagonals passing through its position.

Diagonal Logic

For a queen placed at position (r, c):

• Main Diagonal: The sum of row and column indices is constant (r + c). All squares on this diagonal have the same sum.
• Anti-Diagonal: The difference between row and column indices is constant (r - c). All squares on this diagonal have the same difference.

The Backtracking Strategy

Backtracking is a trial-and-error method of problem solving. In the context of N-Queens:

1. Place a Queen: We attempt to place a queen in the first row, then the second row, and so on.
2. Check Validity: After placing a queen, we check if it is under attack by any previously placed queen.
3. Recurse: If valid, we move to the next row and repeat the process.
4. Backtrack: If we reach a state where no column in the current row is safe, we remove the last placed queen (backtrack) and try a different column in the previous row.
5. Base Case: If we successfully place a queen in every row (i.e., row == n), we have found a valid solution.

Algorithm Walkthrough

Let's visualize the placement for n = 4:

1. Row 0: Place Queen at (0, 0).
2. Row 1: Check columns 0, 1, 2, 3. Only (1, 2) is safe (assuming previous placements). Place Queen at (1, 2).
3. Row 2: Check columns 0, 1, 2, 3. (2, 0) is safe. Place Queen at (2, 0).
4. Row 3: Check columns 0, 1, 2, 3. (3, 3) is safe. Place Queen at (3, 3).
5. Success: All 4 queens placed. Record solution.

If we had placed a queen at (1, 1) instead of (1, 2), we would eventually find that Row 2 has no valid spots, forcing us to remove the queen at (1, 1) and try (1, 2).

Implementation (TypeScript)

Approach 1: 2D Array with Diagonal Tracking

This approach uses a 2D array to represent the board. We maintain three sets (or arrays) to track occupied columns, main diagonals, and anti-diagonals.

function solveNQueens(n: number): string[][] {
  const solutions: string[][] = [];
  const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));

  function isSafe(row: number, col: number): boolean {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }

    // Check upper left diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }

    // Check upper right diagonal
    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: number) {
    if (row === n) {
      solutions.push(board.map(row => row.join('')));
      return;
    }

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

  backtrack(0);
  return solutions;
}

Approach 2: Optimized Diagonal Tracking (Bitmasking)

For very large n, we can optimize space and speed using bitwise operations to track diagonals.

function solveNQueensBitmask(n: number): string[][] {
  const solutions: string[][] = [];

  function backtrack(row: number, cols: number, diag1: number, diag2: number) {
    if (row === n) {
      // Convert bitmask to board representation
      const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
      for (let i = 0; i < n; i++) {
        const col = Math.log2(diag1 & (1 << i));
        board[i][col] = 'Q';
      }
      solutions.push(board.map(row => row.join('')));
      return;
    }

    const availablePositions = (~(cols | diag1 | diag2)) & ((1 << n) - 1);

    while (availablePositions) {
      const position = availablePositions & -availablePositions; // Get rightmost set bit
      const col = Math.log2(position);

      backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);

      availablePositions -= position; // Remove rightmost set bit
    }
  }

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

Complexity Analysis

Time Complexity

The worst-case time complexity is O(N!). In the worst case, we might try placing a queen in every column of every row before finding a solution or exhausting all possibilities. However, due to the constraints (no two queens in same row/col/diag), the actual number of recursive calls is significantly less than N!.

Space Complexity

• Board Storage: O(N²) to store the board configuration.
• Recursion Stack: O(N) for the depth of the recursion tree.

Variations & Extensions

1. N-Queens II: Instead of returning the board configurations, return the number of distinct solutions.
2. K-Queens: Place k queens on an n x n board. This is an NP-hard problem.
3. N-Rooks Problem: A simpler version where only rows and columns matter (no diagonals).

Common Mistakes to Avoid

1. Not Backtracking: Forgetting to reset the board cell to '.' after a recursive call fails. This leads to incorrect board states being passed down the stack.
2. Incorrect Diagonal Checks: Mixing up the logic for main diagonals (row + col) and anti-diagonals (row - col). Always verify the indices carefully.
3. Base Case Confusion: Confusing the base case for a valid solution (row === n) with the base case for a dead end (though the dead end is implicit when the loop finishes without placing a queen).

Real-World Applications

While rarely used directly in production software, the N-Queens problem is a staple in:

• Algorithm Education: Teaching recursion and backtracking.
• Constraint Satisfaction Problems (CSP): Used as a benchmark for CSP solvers.
• Parallel Computing: Used to test the efficiency of parallel algorithms due to the independent nature of finding solutions.