前端「N皇后」递归回溯经典问题图解

June 18, 2020 • ☕️☕️ 8 min read

前言

在我的上一篇文章《前端电商 sku 的全排列算法很难吗？学会这个套路，彻底掌握排列组合。》中详细的讲解了排列组合的递归回溯解法，相信看过的小伙伴们对这个套路已经有了一定程度的掌握（没看过的同学快回头学习~）。

昨晚正好在看字节跳动的招聘直播，弹幕里有一些同学提到了面试时候考到了「N 皇后」问题，他没有答出来。这是一道 LeetCode 上难度为 hard 的题目。

听起来很吓人，但是看过我上一篇文章的同学应该还记得我有提到过，我解决电商 sku 问题用的是排列组合的万能模板，这个万能模板能否用来解决这个经典的计算机问题「N 皇后」呢？答案是肯定的。

问题

先来看问题，其实问题不难理解：

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

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

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

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

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

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

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自百度百科 - 皇后）

LeetCode 原题地址

思路

乍一看这种选出全部方案的问题有点难找到头绪，但是其实仔细看一下，题目已经限定了皇后之间不能互相攻击，转化成代码思维的语言其实就是说每一行只能有一个皇后，每条对角线上也只能有一个皇后，

也就是说：

在一列上，错。
```
[
'Q', 0
'Q', 0
]
```
在左上 -> 右下的对角线上，错。
```
[
'Q', 0
0, 'Q'
]
```
在左下 -> 右上的对角线上，错。
```
[
0, 'Q'
'Q', 0
]
```

那么以这个思路为基准，我们就可以把这个问题转化成一个「逐行放置皇后」的问题，思考一下递归函数应该怎么设计？

对于 n皇后 的求解，我们可以设计一个接受如下参数的函数：

rowIndex 参数，代表当前正在尝试第几行放置皇后。
prev 参数，代表之前的行已经放置的皇后位置，比如 [1, 3] 就代表第 0 行（数组下标）的皇后放置在位置 1，第 1 行的皇后放置在位置 3。

当 rowIndex === n 即说明这个递归成功的放置了 n 个皇后，一路畅通无阻的到达了终点，每次的放置都顺利的通过了我们的限制条件，那么就把这次的 prev 做为一个结果放置到一个全局的 res 结果数组中。

树状图

这里我尝试用工具画出了 4皇后 的其中的一个解递归的树状图，第一行我直接选择了以把皇后放在2为起点，省略了以 放在1、放在3、放在4 为起点的树状图，否则递归树太大了图片根本放不下。

注意这里的 放在x，为了方便理解，这个 x 并不是数组下标，而是从 1 开始的计数。

在这次递归之后，就求出了一个结果：[1, 3, 0, 2]。

你可以在纸上按照我的这种方式继续画一画尝试以其他起点开始的解法，来看看这个算法的具体流程。

实现

理想总是美好的，虽然目前为止我们的思路很清晰了，但是具体的编码还是会遇到几个头疼的问题的。

当前一行已经落下一个皇后之后，下一行需要判断三个条件：

在这一列上，之前不能摆放过皇后。
在对角线 1，也就是「左下 -> 右上」这条对角线上，之前不能摆放过皇后。
在对角线 2，也就是「右上 -> 左下」这条对角线上，之前不能摆放过皇后。

难点在于判断对角线上是否摆放过皇后了，其实找到规律后也不难了，看图：

对角线1：

直接通过这个点的横纵坐标 rowIndex + columnIndex 相加，相等的话就在同在对角线 1 上：

对角线2：

直接通过这个点的横纵坐标 rowIndex - columnIndex 相减，相等的话就在同在对角线 2 上：

所以：

用 columns 数组记录摆放过的列下标，摆放过后直接标记为 true 即可。
用 dia1 数组记录摆放过的对角线 1下标，摆放过后直接把下标 rowIndex + columnIndex标记为 true 即可。
用 dia2 数组记录摆放过的对角线 2下标，摆放过后直接把下标 rowIndex - columnIndex标记为 true 即可。
递归函数的参数 prev 代表每一行中皇后放置的列数，比如 prev[0] = 3 代表第 0 行皇后放在第 3 列，以此类推。
每次进入递归函数前，先把当前项所对应的列、对角线 1、对角线 2的下标标记为 true，带着标记后的状态进入递归函数。并且在退出本次递归后，需要把这些状态重置为 false ，再进入下一轮循环。

有了这几个辅助知识点，就可以开始编写递归函数了，在每一行，我们都不断的尝试一个坐标点，只要它和之前已有的结果都不冲突，那么就可以放入数组中作为下一次递归的开始值。

这样，如果递归函数顺利的来到了 rowIndex === n 的情况，说明之前的条件全部满足了，一个 n皇后 的解就产生了。把 prev 这个一维数组通过辅助函数恢复成题目要求的完整的「二维数组」即可。

/**
 * @param {number} n
 * @return {string[][]}
 */
let solveNQueens = function (n) {
  let res = []

  // 已摆放皇后的的列下标
  let columns = []
  // 已摆放皇后的对角线1下标 左下 -> 右上
  // 计算某个坐标是否在这个对角线的方式是「行下标 + 列下标」是否相等
  let dia1 = []
  // 已摆放皇后的对角线2下标 左上 -> 右下
  // 计算某个坐标是否在这个对角线的方式是「行下标 - 列下标」是否相等
  let dia2 = []

  // 在选择当前的格子后 记录状态
  let record = (rowIndex, columnIndex, bool) => {
    columns[columnIndex] = bool
    dia1[rowIndex + columnIndex] = bool
    dia2[rowIndex - columnIndex] = bool
  }

  // 尝试在一个n皇后问题中 摆放第index行内的皇后位置
  let putQueen = (rowIndex, prev) => {
    if (rowIndex === n) {
      res.push(generateBoard(prev))
      return
    }

    // 尝试摆第index行的皇后 尝试[0, n-1]列
    for (let columnIndex = 0; columnIndex < n; columnIndex++) {
      // 在列上不冲突
      let columnNotConflict = !columns[columnIndex]
      // 在对角线1上不冲突
      let dia1NotConflict = !dia1[rowIndex + columnIndex]
      // 在对角线2上不冲突
      let dia2NotConflict = !dia2[rowIndex - columnIndex]

      if (columnNotConflict && dia1NotConflict && dia2NotConflict) {
        // 都不冲突的话，先记录当前已选位置，进入下一轮递归
        record(rowIndex, columnIndex, true)
        putQueen(rowIndex + 1, prev.concat(columnIndex))
        // 递归出栈后，在状态中清除这个位置的记录，下一轮循环应该是一个全新的开始。
        record(rowIndex, columnIndex, false)
      }
    }
  }

  putQueen(0, [])

  return res
}

// 生成二维数组的辅助函数
function generateBoard(row) {
  let n = row.length
  let res = []
  for (let y = 0; y < n; y++) {
    let cur = ""
    for (let x = 0; x < n; x++) {
      if (x === row[y]) {
        cur += "Q"
      } else {
        cur += "."
      }
    }
    res.push(cur)
  }
  return res
}

课后练习

对递归回溯的相似 LeetCode 题型感兴趣的同学，可以去我维护的力扣题解-递归与回溯这个 Github 仓库分类下查看其它的经典相似题目，先尝试自己用我的两篇递归回溯文章中的思路求解，如果还是答不出来的话，就去看题解总结归纳，直到你能真正的自己做出类似的题型为止。

总结

至此为止，年轻前端的第一道 hard 题就解出来了，是不是有种任督二脉打通的感觉呢？

递归回溯的问题本质上就是，递归进入下一层后，如果发现不满足条件，就通过 return 等方式回溯到上一层递归，继续寻求合适的解。

掌握了这个思路以后，相信你在现实编码中遇到的很多递归难题都可以轻松的降维打击，迎刃而解了。

也祝正在筹备换工作的小伙伴们顺利通过面试笔试的厮杀，拿到理想的 offer，大家加油。

❤️ 感谢大家

1.如果本文对你有帮助，就点个赞支持下吧，你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友，我拉你进「前端进阶交流群」，大家一起共同交流和进步。