N-Queens Problem

1function solveNQueens(n) {
2  const result = [];
3  const cols = new Set();
4  const diag1 = new Set(); // Major diagonal: row - col is constant
5  const diag2 = new Set(); // Anti-diagonal: row + col is constant
6 
7  function backtrack(row, currentBoard) {
8    // Base Case: All N queens safely placed
9    if (row === n) {
10      result.push([...currentBoard]);
11      return;
12    }
13 
14    for (let col = 0; col < n; col++) {
15      const d1 = row - col;
16      const d2 = row + col;
17 
18      // Skip if column or diagonals are under attack
19      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) {
20        continue;
21      }
22 
23      // 1. Choose: Place Queen
24      cols.add(col);
25      diag1.add(d1);
26      diag2.add(d2);
27      const rowStr = '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
28      currentBoard.push(rowStr);
29 
30      // 2. Explore: Recurse to next row
31      backtrack(row + 1, currentBoard);
32 
33      // 3. Un-choose (Backtrack): Undo state
34      currentBoard.pop();
35      cols.delete(col);
36      diag1.delete(d1);
37      diag2.delete(d2);
38    }
39  }
40 
41  backtrack(0, []);
42  return result;
43}
44 
45// Example usage:
46// solveNQueens(4);
47// Returns 2 distinct solutions:
48// [
49//   [".Q..", "...Q", "Q...", "..Q."],
50//   ["..Q.", "Q...", "...Q", ".Q.."]
51// ]