八皇后问题的研究分析解决《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》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_41054844/article/details/98493481
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/234349

相关文章

SQL Server安装时候没有中文选项的解决方法

《SQLServer安装时候没有中文选项的解决方法》用户安装SQLServer时界面全英文,无中文选项,通过修改安装设置中的国家或地区为中文中国,重启安装程序后界面恢复中文,解决了问题,对SQLSe... 你是不是在安装SQL Server时候发现安装界面和别人不同,并且无论如何都没有中文选项?这个问题也

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

java内存泄漏排查过程及解决

《java内存泄漏排查过程及解决》公司某服务内存持续增长,疑似内存泄漏,未触发OOM,排查方法包括检查JVM配置、分析GC执行状态、导出堆内存快照并用IDEAProfiler工具定位大对象及代码... 目录内存泄漏内存问题排查1.查看JVM内存配置2.分析gc是否正常执行3.导出 dump 各种工具分析4.

Olingo分析和实践之EDM 辅助序列化器详解(最佳实践)

《Olingo分析和实践之EDM辅助序列化器详解(最佳实践)》EDM辅助序列化器是ApacheOlingoOData框架中无需完整EDM模型的智能序列化工具,通过运行时类型推断实现灵活数据转换,适用... 目录概念与定义什么是 EDM 辅助序列化器?核心概念设计目标核心特点1. EDM 信息可选2. 智能类

Olingo分析和实践之OData框架核心组件初始化(关键步骤)

《Olingo分析和实践之OData框架核心组件初始化(关键步骤)》ODataSpringBootService通过初始化OData实例和服务元数据,构建框架核心能力与数据模型结构,实现序列化、URI... 目录概述第一步:OData实例创建1.1 OData.newInstance() 详细分析1.1.1

Olingo分析和实践之ODataImpl详细分析(重要方法详解)

《Olingo分析和实践之ODataImpl详细分析(重要方法详解)》ODataImpl.java是ApacheOlingoOData框架的核心工厂类,负责创建序列化器、反序列化器和处理器等组件,... 目录概述主要职责类结构与继承关系核心功能分析1. 序列化器管理2. 反序列化器管理3. 处理器管理重要方

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

SpringBoot整合Dubbo+ZK注册失败的坑及解决

《SpringBoot整合Dubbo+ZK注册失败的坑及解决》使用Dubbo框架时,需在公共pom添加依赖,启动类加@EnableDubbo,实现类用@DubboService替代@Service,配... 目录1.先看下公共的pom(maven创建的pom工程)2.启动类上加@EnableDubbo3.实

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map