前端算法第一三九弹-N 皇后

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 **n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

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

示例 2：

输入：n = 1
输出：[["Q"]]
复制代码

提示：

• 1 <= n <= 9

对于N皇后，是一道经典的回溯算法。皇后彼此之间不能相互攻击。

皇后的走法为横竖斜都可以移动，不限格数。所以每一个皇后之间，不能同行，同列，同斜行。

当如果有一个4行4列的棋盘。

如果第[1][2]点为皇后，则第一行，第二列都不可存在皇后。那么如何判断斜行呢。

当[1][2]为Q时，不可放置皇后的点为[3,0][2,1][0,3]和[0,1][2,3]。

通过数学计算得，与[1][2]和相同的点、与[1][2]差相同的点都不可放置。

由此可知

i+j==row+col||i-j==row-col
复制代码

的点不可放置。

由此可判断该点是否可放置皇后。

const isValid = (row, col) => {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < n; j++) {
        if (board[i][j] == 'Q' && (j == col || i + j == row + col || i - j == row - col)) return false
      }
    }
    return true
  }
复制代码

我们可以先建立一个行列为n的”.”的数组。

const board = new Array(n).fill().map(() => new Array(n).fill('.'))
复制代码

下面我们就可以进行填值，填充皇后。

我们从第0行开始。

遍历该行，判断该点是否可以放置皇后。

然后进行下一行遍历，在该点遍历完之后，重置。进行下一次遍历。

const helper = (row) => {
    if (row === n) {
      const stringsBoard = board.slice()
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join('')
      }
      res.push(stringsBoard)
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = "Q";
        helper(row + 1)
        board[row][col] = "."
      }
    }
  }
复制代码

整体代码为

var solveNQueens = function (n) {

  const board = new Array(n).fill().map(() => new Array(n).fill('.'))
  const res = []
  const isValid = (row, col) => {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < n; j++) {
        if (board[i][j] == 'Q' && (j == col || i + j == row + col || i - j == row - col)) return false
      }
    }
    return true
  }
  const helper = (row) => {
    if (row === n) {
      const stringsBoard = board.slice()
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join('')
      }
      res.push(stringsBoard)
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = "Q";
        helper(row + 1)
        board[row][col] = "."
      }
    }
  }
  helper(0)
  console.log(res);
  return res
};
复制代码