学习记录：js算法（九十）：N皇后

N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

图一：

示例 1：图一
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[["Q"]]

思路一

function solveNQueens(n) {
  const solutions = [];
  const board = new Array(n).fill(-1); // 初始化棋盘，-1 表示未放置皇后

  function isSafe(row, col) {
    // 检查列是否有冲突
    for (let i = 0; i < row; i++) {
      if (board[i] === col || Math.abs(board[i] - col) === row - i) {
        return false;
      }
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      // 收集解
      const solution = [];
      for (let i = 0; i < n; i++) {
        const line = '.'.repeat(board[i]) + 'Q' + '.'.repeat(n - board[i] - 1);
        solution.push(line);
      }
      solutions.push(solution);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row] = col; // 放置皇后
        backtrack(row + 1); // 递归到下一行
        board[row] = -1; // 清除该行皇后，进行回溯
      }
    }
  }

  backtrack(0); // 开始从第一行放置皇后
  return solutions;
}

讲解
N 皇后问题是一个经典的回溯问题，目标是在一个 N×N 的棋盘上放置 N 个皇后，使得没有两个皇后互相攻击。也就是说，任何两个皇后不能在同一行、同一列或同一对角线上。

1. 初始化：创建一个棋盘矩阵，可以用一个一维数组表示，其中的元素值代表该皇后所在的列，下标则代表行。
2. 递归函数：定义一个递归函数 backtrack(row)，用于尝试在第 row 行放置皇后。在这个函数中，检查每一列是否可以放置皇后，如果可以，则放置皇后并递归到下一行；如果不可以，则跳过。
3. 冲突检测：在每一步尝试放置皇后之前，需要检查是否与已放置的皇后发生冲突。这包括检查同一列和两个对角线方向。
4. 回溯：当某一行无法放置皇后时，回溯至上一层，即回退到上一行重新选择列的位置。
5. 终止条件：如果到达了最后一行并且成功放置了皇后，那么就找到了一个有效的解，将其添加到结果集中。