51. N-Queens

Place n queens on an n×n chessboard so that no two attack each other (same row, column or diagonal). Return every distinct board, with 'Q' for a queen and '.' for an empty square.

Every cell on a '\' diagonal shares r − c, and every cell on a '/' diagonal shares r + c. Keep three sets so the attack check is O(1).

1function solveNQueens(n: number): string[][] {
2  const res: string[][] = [], queens: number[] = [];
3  const cols = new Set<number>(), diag = new Set<number>(), anti = new Set<number>();
4  function place(r: number) {
5    if (r === n) { res.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1))); return; }
6    for (let c = 0; c < n; c++) {
7      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;
8      queens.push(c); cols.add(c); diag.add(r - c); anti.add(r + c);
9      place(r + 1);
10      queens.pop(); cols.delete(c); diag.delete(r - c); anti.delete(r + c);
11    }
12  }
13  place(0);
14  return res;
15}

solutions = 0

board

Q

used

cols = {0}r−c = {0}r+c = {0}

Place at (0, 0).

1 / 0

Space: play/pause · ←/→: step