N ферзей

1function solveNQueens(n: number): number[][] {
2  const solutions: number[][] = []
3  const queens: number[] = [] // queens[row] = column
4 
5  function place(row: number): void {
6    if (row === n) {
7      solutions.push([...queens])
8      return
9    }
10    for (let col = 0; col < n; col++) {
11      if (isSafe(row, col)) {
12        queens[row] = col
13        place(row + 1)
14        queens.pop() // откат
15      }
16    }
17  }
18 
19  function isSafe(row: number, col: number): boolean {
20    for (let r = 0; r < row; r++) {
21      if (queens[r] === col) return false                    // столбец
22      if (Math.abs(queens[r]! - col) === row - r) return false // диагональ
23    }
24    return true
25  }
26 
27  place(0)
28  return solutions
29}