N皇后算法可视化教学

1function solveNQueens(n: number) {
2  const board: number[] = Array(n).fill(-1)
3  const solutions: number[][] = []
4
5  function isSafe(row: number, col: number): boolean {
6    for (let i = 0; i < row; i++) {
7      // 检查同列
8      if (board[i] === col) return false
9      // 检查对角线
10      if (Math.abs(board[i] - col) === row - i) {
11        return false
12      }
13    }
14    return true
15  }
16
17  function backtrack(row: number) {
18    // 找到一个解
19    if (row === n) {
20      solutions.push([...board])
21      return
22    }
23
24    for (let col = 0; col < n; col++) {
25      if (isSafe(row, col)) {
26        // 放置皇后
27        board[row] = col
28        // 递归下一行
29        backtrack(row + 1)
30        // 回溯：移除皇后
31        board[row] = -1
32      }
33    }
34  }
35
36  backtrack(0)
37  return solutions
38}