李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--递归-八皇后问题(回溯法)
Leefs
2020-01-30 PM
1486℃
0条
# 数据结构学习--递归-八皇后问题(回溯法) ### 一、八皇后问题介绍 八皇后问题,是一个古老而著名的问题,是**回溯算法的典型案例**。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:**任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法**。 ![12.递归--八皇后问题01.png][1] ### 二、八皇后问题算法思路分析 (1)第一个皇后先放第一行第一列 (2)第二个皇后放在第二行第一列、然后判断是否OK,如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适的 (3)继续第三个皇后,还是第一列、第二列......直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解 (4)当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到。 (5)然后回头继续第一个皇后放第二列,后面继续循环执行1,2,3,4的步骤 **示意图:** ![12.递归--八皇后问题02.png][2] **说明:** 理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决问题。arr[8]={0,4,7,5,2,6,1,3}//对应arr下标 表示第几行,即第几个皇后,arr[i]=val,val表示第i+1个皇后,放在第i+1行的第val+1列 **代码** ```java public class Queue8 { //定义一个max表示共有多少个皇后 int max=8; //定义一个数组array,保存皇后位置的结果,比如 arr={0,4,7,5,2,6,1,3} int[] array= new int[max]; static int count = 0; static int judgeCount = 0; public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d解法",count); System.out.printf("一共判断冲突的次数%d次",judgeCount); } //编写一个方法,放置第n个皇后 //特别注意:check 是 每一次递归时,进入到check中都有 for(int i=0;i
标签:
递归
,
数据结构
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/515.html
上一篇
数据结构学习--递归-迷宫问题
下一篇
数据结构和算法学习--排序算法简介
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
随笔
Scala
JavaScript
查找
ClickHouse
VUE
Jquery
Kafka
Thymeleaf
Spring
DataWarehouse
Golang基础
排序
稀疏数组
Tomcat
Shiro
链表
Java阻塞队列
JavaSE
微服务
Filter
Nacos
Elasticsearch
Flink
数据结构和算法
Typora
Yarn
RSA加解密
栈
NIO
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞