演算法

1function solveNQueens(n: number): number[] | null {
2  const cols: number[] = [];   // cols[r] = column of the queen in row r
3 
4  function safe(row: number, col: number): boolean {
5    for (let r = 0; r < row; r++) {
6      const c = cols[r];
7      if (c === col || Math.abs(c - col) === row - r) {
8        return false;
9      }
10    }
11    return true;
12  }
13 
14  function place(row: number): boolean {
15    if (row === n) return true;
16    for (let col = 0; col < n; col++) {
17      if (!safe(row, col)) continue;
18      cols.push(col);
19      if (place(row + 1)) return true;
20      cols.pop();
21    }
22    return false;
23  }
24 
25  return place(0) ? cols : null;
26}