乐趣区

关于leetcode:Leetcode-通过率最高的困难题-N皇后-II-回溯解法剪枝

jiezi

题目

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

皇后走法规则

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

示例

示例 1：

 输出：n = 4
输入：2

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

示例 2：

 输出：n = 1
输入：1

提醒：
1 <= n <= 9

思路

  1. 定义判断以后地位的检验函数，约束条件蕴含，不能同行，不能同列，不能同对角线（45 度和 135 度）
  2. 定义棋盘；规范回溯解决；

应用回溯的具体做法是：顺次在每一行搁置一个皇后，每次新搁置的皇后都不能和曾经搁置的皇后之间有攻打，即新搁置的皇后不能和任何一个曾经搁置的皇后在同一列以及同一条斜线上。当 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(门路，抉择列表); // 递归
        回溯，撤销处理结果
    }
}

即:

  1. 1. 门路：也就是曾经做出的抉择。
  2. 2. 抉择列表：也就是你以后能够做的抉择。
  3. 3. 完结条件：也就是达到决策树底层，无奈再做抉择的条件。

剪枝函数

  1. 1. 用约束条件剪除得不到的可行解的子树
  2. 2. 用指标函数剪获得不到的最优解的子树

回溯法的个别步骤：

  1. 1. 设置初始化的计划（给变量赋初始值，读入已知数据等）
  2. 2. 变换形式去试探，若全副试完侧转（7）
  3. 3. 判断此法是否胜利（通过束缚函数），不胜利则转（2）
  4. 4. 试探胜利则前进一步再试探
  5. 5. 正确计划还是未找到则转（2）
  6. 6. 以找到一种计划则记录并打印
  7. 7. 退回一步（回溯），若未退到头则转（2）
  8. 8. 已退到头则完结或打印无解

每天精进，持续加油！

退出移动版