Java——N皇后问题

news/2024/10/30 9:24:51/

题目链接

leetcode在线oj题——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”]]

题目提示

  • 1 <= n <= 9

解题思路

使用深度搜索的方法,按照先行后列的顺序,查看每一个位置是否满足条件

先从第一行第一列开始,使这个位置占一个皇后,显然第一行和第一列,与其所在斜线都无法再放皇后了
在这里插入图片描述
然后按照顺序将第二个皇后放在第二行第三列
显然这种放法只能支持三个皇后
在这里插入图片描述
那么回退到上一个状态(第一个皇后在第一行第一列),按照顺序将第二个皇后放在第二行第四列
在这里插入图片描述
显然这种放法也是只能放三个,那么再次回退到上一个状态,按照顺序将第二个皇后放在第三行第二个(这时和放在第二行第三列是对称的,因此结果一致),显然也只能放四个皇后,状态回溯到上一个状态

再将第二个皇后放在第三行第四列,显然这种情况也是只能最多放三个
在这里插入图片描述
其他两个位置也和上面的位置是对称的,因此将第一个皇后放在第一行第一列的情况是没有结果的,状态回溯到没有放皇后的状态

按照顺序,我们将第一个皇后放在第一行第二位
在这里插入图片描述
再按照顺序将第二个皇后放在第二行第四列
在这里插入图片描述
按照顺序将第三个皇后放在第三行第一列上,可以发现这种情况可以放到第四个皇后,状态再次回溯到第一个状态(第一个皇后放在第一行第二列上)
在这里插入图片描述
按照顺序,将皇后放在第三行第一列,可以发现最终产生的结果和上一次的结果一样,因此状态再次退回到没有一个皇后的状态

按照顺序,将第一个皇后放在第一行第三列上
在这里插入图片描述
然后按照顺序,将第二个皇后放在第二行第一列上
在这里插入图片描述
按照顺序,第三个皇后放在第三行第四列上,可以发现最终也可以得到最终的结果
在这里插入图片描述
事实上,把第一个皇后放在第一行第三列上和放在第一行第二列上是对称的情况,因此得到的结果也是对称的

而将第一个皇后放在第一行第四列上和放在第一行第一列上是对称的情况,因此也得不到最后的结果

按照上面的思想,可以写出下面的代码

代码

class Solution {static class Pair{public int x;public int y;public Pair(int x, int y){this.x = x;this.y = y;}}static void DFS(List<List<Pair>> result, List<Pair> curRet,int curRow, int n){//每一行都有元素,当前结果是可行的if(curRow == n){result.add(new ArrayList<>(curRet));return;}//遍历每一列for (int i = 0; i < n; i++) {if(isValidPos(curRet, curRow, i)){curRet.add(new Pair(curRow, i));//处理下一行DFS(result, curRet, curRow + 1, n);//回溯curRet.remove(curRet.size() - 1);}}}/*** 判断当前位置是否有效* @param curRet* @param row* @param col* @return*/private static boolean isValidPos(List<Pair> curRet, int row, int col) {//查看每一个已经存储的点与该点是否有冲突for (int i = 0; i < curRet.size(); i++) {Pair pair = curRet.get(i);if(pair.y == col || pair.x + pair.y == row + col ||pair.x - pair.y == row - col){return false;}}return true;}private static List<List<String>> transResult(List<List<Pair>> result, int n){List<List<String>> finalResult = new ArrayList<>();for (int i = 0; i < result.size(); i++) {//一种方案List<Pair> curRet = result.get(i);List<StringBuffer> stringList = new ArrayList<>();//先将所有位置都设置为.for (int j = 0; j < n; j++) {StringBuffer stringBuffer = new StringBuffer();for (int k = 0; k < n; k++) {stringBuffer.append(".");}stringList.add(stringBuffer);}for (int j = 0; j < curRet.size(); j++) {//一种方案中的位置Pair pair = curRet.get(j);//再将对应位置设置为QstringList.get(pair.x).setCharAt(pair.y, 'Q');}//重新创建一个ret,存储StringList中StringBuffer.toString后的字符串List<String> ret = new ArrayList<>();for (int j = 0; j < stringList.size(); j++) {ret.add(stringList.get(j).toString());}finalResult.add(ret);}return finalResult;}public static List<List<String>> solveNQueens(int n) {List<List<Pair>> result = new ArrayList<>();List<Pair> curRet = new ArrayList<>();DFS(result, curRet, 0, n);return transResult(result, n);}
}

http://www.ppmy.cn/news/29892.html

相关文章

Microsoft designer 使用教程

继各种ai绘图软件诞生之后 dell 2 playground.... 微软自己研发的重量级产品 Microsoft designer 上线了 Microsoft Designer 是微软公司推出的一款设计工具&#xff0c;主要用于快速创建Web和移动应用程序的原型设计。它提供了一系列的工具和模板&#xff0c;可以帮助用户…

三天Golang快速入门—面向对象

面向对象Golang接口的定义go中类空接口空接口作为函数的参数切片实现空接口map的值实现空接口类型断言值接收者和指针接收者值接收者指针接收者接口嵌套Golang接口的定义 接口interface是一种抽象的类型。接口定义了一个对象的行为规范&#xff0c;只定义规范不实现&#xff0…

梯度提升算法决策过程的逐步可视化

梯度提升算法是最常用的集成机器学习技术之一&#xff0c;该模型使用弱决策树序列来构建强学习器。这也是XGBoost和LightGBM模型的理论基础&#xff0c;所以在这篇文章中&#xff0c;我们将从头开始构建一个梯度增强模型并将其可视化。 梯度提升算法介绍 梯度提升算法&#x…

代码随想录中:回溯算法的基础

回溯算法是一种暴力的搜索方式&#xff1b;回溯法一般与递归同时存在。 回溯法&#xff0c;一般可以解决如下几种问题&#xff1a; 组合问题&#xff1a;N个数里面按一定规则找出k个数的集合切割问题&#xff1a;一个字符串按一定规则有几种切割方式子集问题&#xff1a;一个…

LeetCode 236.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是它自己的祖…

大型三甲医院云HIS系统源码 强大的电子病历+完整文档

医院HIS系统源码云HIS系统&#xff1a;SaaS运维平台多医院入驻强大的电子病历完整文档 有源码&#xff0c;有演示 一、系统概述 采用主流成熟技术&#xff0c;软件结构简洁、代码规范易阅读&#xff0c;SaaS应用&#xff0c;全浏览器访问前后端分离&#xff0c;多服务协同&am…

刷题记录:牛客NC13950 Alliances 到树上联通点集的最短距离

传送门:牛客 题目描述: 题目较长,此处省略 输入: 7 1 2 1 3 2 4 2 5 3 6 3 7 2 2 6 7 1 4 3 5 1 2 1 1 1 5 2 1 2 输出: 2 1 1一道比较复杂的树题.需要一些复杂的讨论以及LCA知识 对于LCA,可以使用树链剖分进行解决 然后我们看一下题目,我们会发现有这样一个简单的结论,那就…

华为OD机试Golang解题 - 火星文计算 2 | 包含思路

华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典文章目录 华为Od必看系列使用说明本期题目…