51. N皇后 | LeetCode算法题解

题目描述

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

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

上图为 8 皇后问题的一种解法。

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

示例:

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."] ]
解释: 4 皇后问题存在两个不同的解法。

来源：LeetCode

思路

八皇后问题是一个经典的深度优先搜索和回溯的问题。n皇后则是八皇后问题的一个推广。

具体的操作，是按棋盘格子一个个去尝试放置棋子，放置一个后，则它的所在行列斜线格都不能再放棋子，再寻找下一个可放置棋子的格子，依次类推。这就是深搜。

若所有棋子成功放置在棋盘上，则是一个可行解。若棋子未放置完，棋盘上已无可放置格子，则需要调整上一个棋子的位置，这就是回溯。

解法

/**
 * @param {Object} {x, y}
 * @param {string[][]} chessboard
 * @param {number} n
 * @return {boolean}
 */
const canPlace = (position, chessboard, n) => {
  const { x, y } = position;

  for (let i = 0; i < n; i++) {
    // 检查x行或y列有无其他皇后
    if (chessboard[x][i] === 'Q' || chessboard[i][y] === 'Q') {
      return false;
    }

    // 检查左上斜线有无其他皇后
    if (x - i >= 0 && y - i >= 0 && chessboard[x - i][y - i] === 'Q') {
      return false;
    }

    // 检查右上斜线有无其他皇后
    if (x - i >= 0 && y + i < n && chessboard[x - i][y + i] === 'Q') {
      return false;
    }

    // 检查左下斜线有无其他皇后
    if (x + i < n && y - i >= 0 && chessboard[x + i][y - i] === 'Q') {
      return false;
    }

    // 检查右下斜线有无其他皇后
    if (x + i < n && y + i < n && chessboard[x + i][y + i] === 'Q') {
      return false;
    }
  }

  return true;
};

/**
 * @param {number} n
 * @return {string[]}
 */
const solveNQueens = n => {
  const chessboard = Array(n).fill(Array(n).fill('.'));

  const result = [];

  /**
   * @param {row} 当前搜索到的行
   * @param {string[][]} currentChessboard 当前搜索的棋盘
   * @param {number} count 剩余棋子数
   */
  const deepSearch = (row, currentChessboard, count) => {
    if (count === 0) {
      result.push(currentChessboard.map(item => item.join('')));
      return;
    }

    for (let x = row; x < n; x++) {
      for (let y = 0; y < n; y++) {
        if (canPlace({ x, y }, currentChessboard, n)) {
          const newChessboard = currentChessboard.map(item => [...item]);
          newChessboard[x][y] = 'Q';

          deepSearch(x + 1, newChessboard, count - 1);
        }
      }
    }
  };

  deepSearch(0, chessboard, n);

  return result;
};