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

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"]]

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

以 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
    
};

代码作者:carlsun-2，已验证通过；

回溯算法跟 DFS 深度搜索算法都很经典，需同步理解，对比、吸收；

我是掘进安东尼，公众号同名，日拱一卒、日掘一金，再会~