Leetcode 通过率最高的困难题 N皇后 II 【回溯解法-剪枝】

微芒不朽

发布于 2022-09-13 09:56:04

6030

发布于 2022-09-13 09:56:04

文章被收录于专栏：前端进阶-詹躲躲

题目

「n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。」

皇后走法规则

皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。

示例

示例 1：

输入：n = 4
输出：2

解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：1 <= n <= 9

思路

定义判断当前位置的检验函数，约束条件包含，不能同行，不能同列，不能同对角线（45度和135度）
定义棋盘；标准回溯处理；

使用回溯的具体做法是：依次在每一行放置一个皇后，每次新放置的皇后都不能和已经放置的皇后之间有攻击，即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上。当 NNN 个皇后都放置完毕，则找到一个可能的解，将可能的解的数量加 111。

图片来源

解题代码

var totalNQueens = function (n) {
    let count = 0; //皇后可放置的总数
    let isValid = (row, col, board, n) => {
        //所在行不用判断，每次都会下移一行
        //判断同一列的数据是否包含
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false
            }
        }
        //判断45度对角线是否包含
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') {
                return false
            }
        }
        //判断135度对角线是否包含
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) {
            if (board[i][j] === 'Q') {
                return false
            }
        }
        return true
    }

    let backTracing = (row, board) => {
        //走到最后一行，统计次数
        if (row === n) {
            count++;
            return
        }

        for (let x = 0; x < n; x++) {
            //判断该位置是否可以放置 皇后
            if (isValid(row, x, board, n)) {
                board[row][x] = 'Q'; //放置皇后
                backTracing(row + 1, board); //递归
                board[row][x] = '.'; //回溯，撤销处理结果
            }
        }
    }
    backTracing(0, board)
    let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盘
    return count
};

总结

主要运用了回溯算法；而解决一个回溯问题，实际上就是一个决策树的遍历过程。

let backtracking=(路径，选择列表) =>{
    if (满足结束条件)) {
        存放路径;
        return;
    }
    for (选择：路径，选择列表) {
        做出选择；
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

即: