Loading [MathJax]/jax/input/TeX/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >穷举vs暴搜vs深搜vs回溯vs剪枝系列一>N 皇后

穷举vs暴搜vs深搜vs回溯vs剪枝系列一>N 皇后

作者头像
用户11305962
发布于 2025-01-19 05:10:19
发布于 2025-01-19 05:10:19
4900
代码可运行
举报
文章被收录于专栏:学习学习
运行总次数:0
代码可运行

题目: 


解析:

1.决策树: 


代码设计: 


根据决策树剪枝设计: 


代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    private List<List<String>> ret;
    private char[][] path;
    private boolean[] checkdig1,checkdig2,checkcol;
    int n;

    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new char[n][n];
        checkcol = new boolean[n];//判断列有没有n皇后
        checkdig1 = new boolean[2*n];//判断主对角线有没有n皇后
        checkdig2 = new boolean[2*n];//判断副对角线有没有n皇后



        for(int i = 0; i < n; i++)
            Arrays.fill(path[i],'.');    

        dfs(0);
        return ret;
    }

    private void dfs(int row){
        if(row == n){
            List<String> tmp = new ArrayList<>();  
            for(int i = 0; i < n; i++){
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        } 

        for(int col = 0; col < n; col++){

            //剪枝写法,能不能放N 皇后:
            if(checkcol[col] == false && checkdig1[col-row+n] == false && checkdig2[col+row] == false){
                path[row][col] = 'Q';
                checkcol[col] = checkdig1[col-row+n] = checkdig2[col+row] = true;
                dfs(row+1);

                //恢复现场
                path[row][col] = '.';
                checkcol[col] = checkdig1[col-row+n] = checkdig2[col+row] = false;
            }
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
N皇后!
力扣题目链接:https://leetcode-cn.com/problems/n-queens
代码随想录
2021/11/05
8040
LeetCode-51-N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
benym
2022/07/14
2390
N 皇后问题_用回溯法解N皇后问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
全栈程序员站长
2022/11/19
4320
【回溯+剪枝】优美的排列 && N皇后(含剪枝优化)
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm(下标从 1 开始),只要满足下述条件 之一 ,该数组就是一个 优美的排列 :
利刃大大
2025/02/04
750
【回溯+剪枝】优美的排列 && N皇后(含剪枝优化)
回溯法+约束编程-LeetCode51(N皇后问题与解数独问题对比)
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
算法工程师之路
2019/10/13
7980
【算法学习】递归、搜索与回溯算法(二)
https://blog.csdn.net/2301_80220607/category_12922080.html?spm=1001.2014.3001.5482
GG Bond1
2025/05/09
910
【算法学习】递归、搜索与回溯算法(二)
DFS:深搜+回溯+剪枝解决矩阵搜索问题
3、dfs的返回值不一定是void,如果该题目并不只是完全地去统计,而是涉及到我们做出的选择可能会错误的时候,这个时候我们就需要通过bool类型的返回值来帮助我们判断当前的填法是否正确。比如解数独和单词搜索问题
小陈在拼命
2024/04/10
1370
DFS:深搜+回溯+剪枝解决矩阵搜索问题
搞定大厂算法面试之leetcode精讲11剪枝&回溯
复杂度分析:时间复杂度O(2^2n*n),字符串的长度为2n,每个位置有两种选择,选择左或者右括号,验证字符串是否有效复杂度O(n),剪枝之后会优化,最坏的情况是O(2^2n*n)。空间复杂度O(n),递归次数最多2n
全栈潇晨
2021/11/30
5710
回溯:系列经典题目
对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码
鹏-程-万-里
2020/06/02
5680
【递归与回溯深度解析:经典题解精讲(中篇)】—— LeetCode
用户11286421
2025/01/17
1230
【递归与回溯深度解析:经典题解精讲(中篇)】—— LeetCode
n皇后问题java版
n皇后问题是一个典型的回溯算法的题目,就是在n*n的面板上,放n个皇后,每个皇后会攻击同一列和同一行还有两个斜边上的元素,问你放的方法,返回形式是一个List嵌套List,每个List里都是一种解决方案,每一个解决方案都是画一个面板,解决方案里的每一个元素都是每一个横行,如果没有放皇后,则以.来形容,如果放了皇后,以Q填充,在思想上肯定还是有一定难度的,先贴上java代码的实现,这里已经优化了很多,因为我们是一行一行来放的,所以在放入一行之后,这一行(执行方法isVaild时还没有往该行放Q的操作,所以此行是不可能有Q的存在的)以及这一行下面的所有行都是.,不存在有没有Q的存在,所以只需要判断现在的棋盘面板上的上方、左上方、右上方是否有Q的存在(isVaild实现)即可,这样看起来通俗易懂,当然这个思想是用了回溯算法,在每一个循环里面,先实施放Q的操作,在递归进去之后的一行代码,再将其还原,这就是回溯,因为有可能我们放到某一行之后,全部continue掉了,也就是此时遍历完当前行的所有列都没有找到一个合适的位置放皇后,相当于此路不通,所以我们要还原之前的现场,换一列重新递归,甚至这一行的所有列遍历完后,他的下一列还是无解,此时还要返回到更上面一行,这样就更有回溯的感觉了:
gzq大数据
2021/09/27
7540
穷举vs暴搜vs深搜vs回溯vs剪枝专题一>全排列II
用户11305962
2025/01/13
720
穷举vs暴搜vs深搜vs回溯vs剪枝专题一>全排列II
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>括号生成
用户11305962
2025/01/13
440
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>括号生成
回溯法求解八皇后问题
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,可以快速解决此类问题。
用户6021899
2021/04/19
1.2K0
回溯法求解八皇后问题
leetcode 面试题 08.12. 八皇后----回溯篇7
皇后的走法是:可以横直斜走,格数不限。因此要求皇后彼此之间不能相互攻击,等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
大忽悠爱学习
2021/11/15
4900
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>组合
用户11305962
2025/01/13
800
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>组合
算法:深度、广度优先搜索算法与剪枝-实战
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
营琪
2019/11/04
6670
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>组合总和
用户11305962
2025/01/13
490
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>组合总和
【经典回溯】N 皇后 / 解数独 / 黄金矿工 / 单词搜索 / 不同路径 III
_小羊_
2025/04/09
1000
【经典回溯】N 皇后 / 解数独 / 黄金矿工 / 单词搜索 / 不同路径 III
穷举vs暴搜vs深搜vs回溯vs剪枝专题一>全排列
用户11305962
2025/06/01
380
穷举vs暴搜vs深搜vs回溯vs剪枝专题一>全排列
推荐阅读
相关推荐
N皇后!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验