51-N皇后.md

题目描述

N皇后

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

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

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

皇后可以攻击处于同一条横行、纵行或斜线上的棋子。

分类

困难 回溯

思路

回溯

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  // 列不能冲突，规则 [...已经占有的列index]
  let existColumn = []
  // 左上--右下对角线， 规则 column - row === 定值 === true时 代表不能进行放置
  let diagonalLT = []
  // 左下--右上对角线， 规则 column + row === 定值 === true时 代表不能进行放置
  let diagonalLB = []
  // 储存结果
  let res = []

        
  /**
  * 目的是确定当前行 能够进行插入的列
  * @param {*} n 棋盘阶数，如果函数定义到solveNQueens中就不用该参数
  * @param {*} rowIndex 当前需要检索的行数，如果rowIndex === n 则说明已经结束了
  * @param {*} row 累计的row [1,2,3] 同queenColumn
  */
  function whichColumnToInsert (rowIndex, row) {
    // 结束
    if (rowIndex === n) {
        res.push(format(row))
        return
    }
    // 对每列进行遍历，贪心找出结果
    for (let i = 0; i < n; i++) {
        // 成立
        if (existColumn.indexOf(i) === -1 && diagonalLT.indexOf(i - rowIndex) === -1 && diagonalLB.indexOf(i + rowIndex) === -1) {
          row[rowIndex] = i
          existColumn.push(i)
          diagonalLT.push(i - rowIndex)
          diagonalLB.push(i + rowIndex)
          whichColumnToInsert(rowIndex + 1, row)
          row.splice(rowIndex, 1)
          existColumn.pop()
          diagonalLT.pop()
          diagonalLB.pop()
        }
    }
  }

  function format (arr) {
    const strArr = []
    for (let i = 0; i< arr.length; i++) {
        strArr[i] = '.'.repeat(arr.length)
        const _strArr = strArr[i].split('')
        _strArr[arr[i]] = 'Q'
        strArr[i] = _strArr.join('')
    }
    return strArr
  }


  whichColumnToInsert(0, [])
  return res
};

• 问题拆解

  • 找出所有放置方案，通过某种方式进行表示

    • 要找到所有的放置方案，我们先进行一种放置方案的求解，再来看能不能用同样的思路求解其余的方案。
    • 根据皇后的☠️猎杀规则，每个行、每个列都只可能有一个皇后棋子。那么将n个皇后放到n x n 的棋盘上，肯定是每行、每列都有且仅有一颗皇后。
    • 基于上面的分析，我们可以对棋盘的每一行进行遍历，将棋子安排到当前行中的某一列。
    • 例如在第一行，我们选择了第一列进行放置。在第二行时，我们需要去判断应当插入到那一列(whichColumnToInsert)，这里需要找出什么样的规则是能够判断当前列是能够满足放置条件的。
      • 不能处于同一行 --> 因为我们目前就是在确定每行中的棋子应该放到哪一列，所以这个已经是前置条件。
      • 不能处于同一列 --> 全局声明变量existColumn:Array，储存已经使用了的列号。
      • 不能处于同一斜线(坐标如下)
        • 左上-右下斜线 --> 容易得出[x,y]的y-x为定值，全局声明变量diagonalLT:Array将该定值储存起来，下次使用y-x进行比较，若diagonalLT中存在则说明该斜线已经存在棋子。
        • 左下-右上斜线 --> [x, y]的x+y为定值，使用diagonalLB储存

        [0, 0] [0, 1] [0, 2]

        [1, 0] [1, 1] [1, 2]

        [2, 0] [2, 1] [2, 2]

    • 如果顺利的话，每次能在一行得到一个答案，通过对所有行的遍历后，能够得到一个最终的答案。但是如果在某一行无法找到任何的列满足需求呢？我们需要进行回退，回退到上一列。再退一步回到题目中，我们是要找到所有的位置，所以不仅是找不到答案的时候我们需要回退，如果找到了答案，我们也要回退到上一行去找更多的答案。这就是回溯。
    • 这里我先抛出一个模版，再根据这个模版去看代码。whichColumnToInsert就是这里的backTrack函数

      // 回溯模板
      backTrack(路径, 当前可选) {
        if (满足条件) return
        for (遍历当前可选) {
          // todo 进行选择
          backTrack(路径, 当前可选)
          // todo 取消选择
        }
      }

      • 第一个参数路径是指目前进行到了哪一步，这里问题中是指已经进行到了哪一行。
      • 第二个参数是当前可选，我们这里实际上没有用到这个参数，因为在我们这个问题中当前还可以选择的路径是该行的所有列，如果该问题中，上一行用过的列不能继续使用（这里我们实际是在遍历可选中进行了判断），这个参数就是有必要的了。写到这里我发现whichColumnToInsert的第二个参数是不需要的，可以全局定义一个变量去做这个累计的结果的储存。
      • 满足条件， 这里只要我们储存单次结果的数组长度和n - 1相等了就说明满足了，这里因为如果已经有结果了，仍然会再递归调用了一次，所以就在下一次的调用中进行了判断rowIndex === n
      • 进行选择， 这里就是对可选进行条件的筛选，如果是可行的，就选择（这里是增加基于该位置的限制条件），就基于当前选择(rowIndex + 1)递归到下一次选择中。如果这里的递归函数结束了，说明基于当前列的选择的，后续行的选择结束了，需要将该列的选择取消（对当前选择判断条件的解除），再进行下一列的寻找。
    • 在第一次的回溯函数的调用中，我们从0行开始，所以第一个参数传入0即可。

  • 将所有放置方案的表示转化为最终的“Q.”的形式

    • 放置方案的表示方式是list:[1, 3, 0, 4]说明第index行棋子在第list[index]列，例如第0行棋子在第1列。
    • 所以我们先对list进行遍历，因为是n x n的棋盘，每次遍历(i)中都先声明一个长为list.length的填充为'.'的字符串，再根据list[i]的值将字符串中list[i]位置的字符替换为‘Q’，每次遍历生成的字符串按序存入一个数组即可。