从 DFS 到回溯法，再看 N 皇后问题

作者：掘金安东尼

2022 年 9 月 27 日
广东
本文字数：1844 字
阅读完需：约 6 分钟

DFS 是深度搜索，是暴力的，是一条道走到黑的，是一次性搜到底的！那么，搜到底发现没有路了，就得回退去找另外的路，再继续莽着搜！既然要回退，就必须保存走过每个点的所有信息，包括先后顺序；这个回退的过程就叫回溯。

根据回溯思想，演进到回溯算法来解决寻找问题。看一下 wiki 对回溯法的解释：

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

简化理解：回溯算法 = 树的深度优先搜索 + 剪枝函数

什么是剪枝函数？为了提高搜索效率，在搜索过程中使用约束函数，可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，他们统称为剪枝函数。

OK，以上是概念介绍，下面来一道经典之经典之经典的回溯算法题：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"]]

复制代码

<sub>N 皇后问题很多时候作为例题出现在教科书中，可以当做理解回溯算法的例题进行学习；</sub>

以 4 皇后问题为例，递归树如下：

解题思路：

回溯算法的通用解题思路就是在递归之前做选择，在退出递归之前撤销选择；
通过恰当的方式将不符合条件的情况剪枝；

回溯三部曲:

递归函数参数；
递归终止条件；
单层搜索的逻辑；

回溯模板：

void backtracking(参数) {    if (终止条件) {        存放结果;        return;    }    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {        处理节点;        backtracking(路径，选择列表); // 递归        回溯，撤销处理结果    }}

复制代码

JavaScript 实现：

var solveNQueens = function(n) {    function isValid(row, col, chessBoard, n) {        // 检查列        for(let i = 0; i < row; i++) { // 这是一个剪枝            if(chessBoard[i][col] === 'Q') {                return false            }        }        // 检查 45度角是否有皇后        for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {            if(chessBoard[i][j] === 'Q') {                return false            }        }        // 检查 135度角是否有皇后        for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {            if(chessBoard[i][j] === 'Q') {                return false            }        }        return true    }        // 存放结果    function transformChessBoard(chessBoard) {        let chessBoardBack = []        chessBoard.forEach(row => {            let rowStr = ''            row.forEach(value => {                rowStr += value            })            chessBoardBack.push(rowStr)        })
        return chessBoardBack    }
    let result = []    // 回溯    function backtracing(row,chessBoard) {        if(row === n) { // 终止条件            result.push(transformChessBoard(chessBoard))            return        }        for(let col = 0; col < n; col++) {            if(isValid(row, col, chessBoard, n)) {                chessBoard[row][col] = 'Q' // 处理节点                backtracing(row + 1,chessBoard) // 递归                chessBoard[row][col] = '.' // 回溯，撤销处理结果            }        }    }    let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))    backtracing(0,chessBoard)    return result    };