7.2 N-Queens & Board Puzzles

Demo: N-Queens — LC 51 (Hard — Meta/Google High)

Statement (Demo): Place n queens on an n × n chessboard so that no two attack each other. Return every distinct solution. Example: n=4 → [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] | ⚡ 1 ≤ n ≤ 9

Approach: Place one queen per row. Keep the occupied column and both diagonals in three Sets — the trick for diagonals is that row - col and row + col stay constant along them.

function solveNQueens(n) {
  const res = [];
  const board = Array.from({ length: n }, () => new Array(n).fill("."));
  const cols = new Set(),
    diag1 = new Set(),
    diag2 = new Set();
  const place = (row) => {
    if (row === n) {
      res.push(board.map((r) => r.join("")));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col))
        continue;
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      board[row][col] = "Q";
      place(row + 1);
      board[row][col] = "."; // undo
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  };
  place(0);
  return res;
}

Complexity: Time O(n!), Space O(n²)