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

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

1.JPG

题目



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


给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。*


2.JPG


皇后走法规则



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


示例


示例 1:

3.JPG

输入:n = 4

输出:2

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

示例 2:

输入:n = 1

输出:1

提示:

1 <= n <= 9


思路



  1. 定义判断当前位置的检验函数,约束条件包含 ,不能同行,不能同列,不能同对角线(45度和135度)


  1. 定义棋盘;标准回溯处理;


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


4.JPG

图片来源


解题代码


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.已退到头则结束或打印无解


每天精进,继续加油!

相关文章
|
2月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
15 2
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
52 1
|
4月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
61 1
|
4月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
55 0
|
4月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
40 0
|
6月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
6月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
6月前
|
存储 机器学习/深度学习 算法
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
|
6月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)