八皇后问题的研究分析解决《Blind-Stab》

2023-10-18 18:20

本文主要是介绍八皇后问题的研究分析解决《Blind-Stab》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

如图其中一种可能性:

分析:

1,所谓八皇后,就是找可能性。8x8大小的棋盘,放8个棋子,每个棋子的横列斜三个方向都只能有它一个存在。

2,很明显我们应该定义一个二位数组模拟棋盘,初始化这个二维数组的值全部为0,刚好我们把0当作未放棋子的状态。

3,每当我们放一个棋子,我们就把放置棋子处的值变成1,代表放置了一个皇后。

4,我们写一个方法findQueen(int row,int [ ] [ ] arr),来放置棋子,参数row代表当前要放的行,二维数组代表棋盘。

5,一开始我们准备放置第一个棋子,传入该方法的参数row应该为0,代表第一行。

6,这个方法该怎么实现呢,我们准备递归调用这个方法。我们找出归的条件  if(row == 8)

7,当row == 8的时候,也就是我们准备放第9个棋子,也就是说符合条件的8个棋子都放好了,那我们打印就行了。

8,但是当row不等于或者说小于8的时候呢?也就是还没放完的情况呢,也就是每次我们该怎么放第row + 1行呢?

9,一开始传递进来的row是为0的,代表着从第一行开始放,既然我们归的条件已经写好了,我们就来写递的情况。

10,第一行,row == 0,一个棋子都还没放,我们是不是应该找位置,找可以放的地方,怎么找,行是确定的。

11,我们肯定是遍历列啊,就是第1行的哪一列可以放棋子呢,遍历,从第1列开始,到最后一列,找到了可以放的地方就直接放

12,放下去之后我们就不用管了,接下来就找第二行,那我们就直接调用findQueen(row + 1,arr),我们先假设我们第一行放的位置没有问题,让他去找第二行,同理,找到了第二行他会去找第三行,,,

13,但是,这样下去一开始没问题,但可能到了第5,或者第6行的时候,他会发现它遍历了所有列,却发现哪一列都不能放。

14,那怎么办呢?不要怕,我们写的是递归啊,它遍历完所有的列都不行那说明他的前一行放错了,应该放下一个位置试试

15,因为它一个都没有找到,他就从那个递归中出来了,因为我们下面什么都没写。他就回到了上一层

16,我们说过是它上一层放的位置不对,不对那就换,移动,上一层的for循环还在呢还没完,i++了

17,但是,在这之前,你得做一件事,你上一层放的位置不对,但是它还是放了,所以你得清空那个不对的位置。

18,而我们传递进下一行的参数一直都是row + 1,也就是说它的上一层还在原来的位置,不能放,我就先清空,arr[row][j] = 0;

19,让他重新为0,才j++,也就是下一列看看能不能放。

20,至此,这个递归调用就完整了。

 

下面来看看我的源代码:

public class EightQueenT {public static int counts = 0;public static void main(String[] args) {//定义8*8大小的二维数组模拟棋盘//初始化值皆为0int [][] arr = new int[8][8];findQueen(0,arr);}public static void findQueen(int row, int[][] arr) {//我们对当前行进行判断//row == 8说明8行皇后打印完毕,一种情况出来,直接打印if(row == 8) {counts++;//对情况进行统计,看看情况总数对不System.out.println("第" + counts + "种情况");for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length; j++) {System.out.print(arr[i][j] + " ");}System.out.println("");//换行控制格式}}else {//如果没有放完8个,我们继续找//行是确定的,我们找列,看看哪一列可以放for (int col = 0; col < arr.length; col++) {//如果此处此行此列没有危险,能放if(!Danger(row,col,arr)) {//那就放,将此处的值变为1arr[row][col] = 1;//并且递归调用方法,参数变为下一行findQueen(row + 1,arr);//但是要是这一行一个都没有//那说明我上一行的列放错了//那我就要将放错的这个位置请0arr[row][col] = 0;}}}}//此方法判断我准备放的位置有没有危险public static boolean Danger(int row, int col, int[][] arr) {//判断八个方向,但是因为是一层一层放的下面都还没放,所以下面肯定不会相同//左边不行都被我清空过,右边都还没放,所以不必判断//那我就只要判断左上,上,右上//往上//当前列不变,行从当前行-1判断至第一行for (int r = row - 1; r >= 0; r--) {//看看上方有没有==1的,也就是有没有皇后if(arr[r][col] == 1) {//有的话直接返回true,表示有危险不能放return true;}}//左上//当前位置行和列都-1开始,每次减一,但是要判断到棋盘边界则停止for (int r = row - 1,c = col - 1; r >= 0&&c >= 0; r--,c--) {//看看左上方有没有==1的,也就是有没有皇后if(arr[r][c] == 1) {//有的话直接返回true,表示有危险不能放return true;}}//右上//当前行从-1开始,列从+1开始,行每次行--,列++//行边界大于等于0,列到arr.length - 1for (int r = row - 1,c = col + 1; r >= 0&&c <= arr.length - 1; r--,c++) {//看看左上方有没有==1的,也就是有没有皇后if(arr[r][c] == 1) {//有的话直接返回true,表示有危险不能放return true;}}//如果这三种情况都没有,代表没有危险可以放返回falsereturn false;}}

运行结果如下:

总结:

其实就是判断,能放就放,不能放就下一列。当前行的所有列都不能放就回溯。

用程序来模拟思维,一定要思路清晰,想好所有情况。

 

 

 

 

 

 

 

 

 

 

这篇关于八皇后问题的研究分析解决《Blind-Stab》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/234349

相关文章

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Python中ModuleNotFoundError: No module named ‘timm’的错误解决

《Python中ModuleNotFoundError:Nomodulenamed‘timm’的错误解决》本文主要介绍了Python中ModuleNotFoundError:Nomodulen... 目录一、引言二、错误原因分析三、解决办法1.安装timm模块2. 检查python环境3. 解决安装路径问题