N-Queens Problem

N-Queens Problem

The N-Queens problem is a classic puzzle: place N chess queens on an N×N chessboard so that no two queens threaten each other. Queens can move horizontally, vertically, and diagonally. So no two queens can be in the same row, column, or diagonal. Sounds simple, but try doing it for N=8 (standard chess board) - there are 92 different solutions!

This is the perfect example of backtracking in action. We place queens one row at a time, and if we reach a point where we can't place a queen in the current row without conflicts, we backtrack to the previous row and try a different position. It's like solving a puzzle by trial and error.

The key to solving this is efficiently checking if a position is safe. We don't need to check rows since we place one queen per row. We need to check columns and both diagonals. Using sets to track occupied columns and diagonals makes this O(1) per check.

Solving N-Queens

Start with an empty board. Place a queen in the first row, first column. Move to the next row and try each column. If a position is safe, place the queen and recurse. If we reach row N, we found a solution! If no position in a row is safe, backtrack to the previous row and move that queen.

Time complexity? O(N!) in the worst case because we're trying N columns in the first row, N-1 in the second (can't be same column), etc. But with pruning (checking safety), it's much better in practice. The space complexity is O(N²) for the board or O(N) if you use sets to track occupied positions.

function solveNQueens(n) {
  const solutions = [];
  const board = Array(n).fill(-1);
  
  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i] === col) return false;
      if (Math.abs(board[i] - col) === Math.abs(i - row)) return false;
    }
    return true;
  }
  
  function solve(row) {
    if (row === n) {
      solutions.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row] = col;
        solve(row + 1);
        board[row] = -1;
      }
    }
  }
  
  solve(0);
  return solutions;
}

const result = solveNQueens(4);
console.log(result);