八皇后问题Java
2022/1/27 1:04:37
本文主要是介绍八皇后问题Java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
思路分析: 把第一个皇后放到第一行第一列
(1)把第二个皇后放到第二行第一列,进行判断,如果不行,放在第二列,进行判断,如果不行,放在 第三列,进行判断,一次把所有列进行尝试,直至找到合适位置
(2)把第三个皇后放到第三行第一列,同步骤2
(3)........
(4)直至第8个皇后也能放到合适位置,此时第一个符合要求摆法便找到。
(5)当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯。把第一个皇后在第一行第一列的所 有解都找到
(6)继续把第一个皇后放到第一行第二列,继续执行上述步骤
结果表示:用一个数组来表示摆法,比如arr[8]={0,4,5,7,6,1,2,3},下标对应的是第几行, 数值对应的是第几列。
arr[i]=j 第i+1个皇后,放在了第i+1行第j+1列
代码实现:
public class Queen { //定义一个max,表示一下共有多少个皇后,同理可求n个皇后 int max = 8; //定义一个数组,报错皇后放置的位置 int[] array = new int[max]; //定义一个变量,保存共有多少中摆法 static int count = 0; public static void main(String[] args) { Queen queen=new Queen(); queen.queen8(0); System.out.println("共有"+count+"种摆法"); } //放置n个皇后,递归 private void queen8(int n) { //递归终止条件 if (n == max) {//8个皇后放好了 print(); return; } //依次放入皇后,判断是否冲突 for (int i = 0; i < max; i++) { //把当前这个皇后,放到该行的第1列 array[n] = i; if (judge(n)) { //如果不冲突,放下一个皇后 queen8(n + 1); } //如果冲突,放下一列 } } private void print(){ count++; for (int i = 0; i <array.length ; i++) { System.out.print(array[i]+" "); } System.out.println(); } //判断是否冲突 private boolean judge(int n) { //判断当前皇后与前面的n-1个是否冲突 for (int i = 0; i < n; i++) { //任意两个皇后都不能处于同一行,同一列或者同一写线上 //判断是否在同一行 没有必要n++ //判断是否同一列 array[i]==array[n] //是否同一斜线 Math.abs(n-i)==Math.abs(array[n]-array[i] if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return false; } } return true; } }
这篇关于八皇后问题Java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南