Java实现八皇后问题

这篇具有很好参考价值的文章主要介绍了Java实现八皇后问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

八皇后问题说明

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

思路分析

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列,然后判断是否OK,如果不OK,继续放在第二列、第三列,依次把所有列都放完,找到一个合适的位置
  3. 继续第三个皇后,还是第一列、第二列…直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
  4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到。
  5. 然后回头继续第一个皇后放第二列,后面继续循环 1,2,3,4 的步骤

代码实现如下

public class EightQueens {

	private static final int N = 8; //棋盘大小为8x8
	private static int[] queens = new int[N];// 一维数组表示每一行皇后所在的列数
	private static int count = 0;

	//编写一个 main 方法
	public static void main(String[] args) {
		solve(0); //从第 0 行开始放置皇后
		System.out.println("最多有"+ count + "种排序");

	}

	//递归处理皇后在每行的位置并放到 queens数组中
	private static void solve(int row){
		if( row >= N ){ //所有行都放置好了皇后,找到一个解
			print();
			return;
		}

		for(int col = 0; col < N; col++){
			if (isSafe(row, col)) { // 当前位置安全,可以放置皇后
                queens[row] = col; // 在当前行,将皇后放在第col列
                solve(row + 1); // 递归放置下一行的皇后
            }
		}
	}

	//判断是否在每一行、每一列、对角线
	private static boolean isSafe(int row, int col) {
        // 检查当前位置是否安全
        for (int i = 0; i < row; i++) {
            // 检查是否同一列或者同一对角线上已经存在皇后
            if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
                return false; // 不安全
            }
        }
        return true; // 安全
    }


	//打印输出全部解
	private static void print(){
		count++;
		for(int i = 0; i < N; i++){
			System.out.print(queens[i] + " ");
		}
		System.out.println();
	}

}

执行结果

Java实现八皇后问题,数据结构与算法,java,开发语言文章来源地址https://www.toymoban.com/news/detail-629039.html

到了这里,关于Java实现八皇后问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

    🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介:CSDN内容合伙人,全栈领域优质创作者。 本文是浙大数据结构学习笔记专栏 这里我们引入一个问题,最常见的多项式,我们如何使用编程将多项式表示出来呢? 我们可以使用数组来表示,但是会随着一个问题,如下图底

    2024年01月21日
    浏览(71)
  • 【一起学数据结构与算法】Java实现双链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 打印双链表非常简单,只需要单独创一个结点

    2024年02月22日
    浏览(43)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(78)
  • 数据结构与算法中的七大排序(Java实现)

    目录 一、直接插入排序 二、希尔排序 三、直接选择排序 四、堆排序 五、冒泡排序 六、快速排序 七、归并排序               定义i下标之前的元素全部已经有序 ,遍历一遍要排序的数组,把i下标前的元素全部进行排序,当遍历玩这个数组后,就已经排好序了。        

    2024年02月06日
    浏览(58)
  • 深入理解Java线程池ThreadPoolExcutor实现原理、数据结构和算法(源码解析)

    什么是线程池?         线程池主要是为了解决执行新任务执行时,应用程序为减少为任务创建一个新线程和任务执行完毕时销毁线程所带来的开销。通过线程池,可以在项目初始化时就创建一个线程集合,然后在需要执行新任务时重用这些线程而不是每次都新建一个线

    2024年02月07日
    浏览(45)
  • 数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)

    目录 问题描述  解题思路 伪代码  总体算法 DFS算法 伪代码解读 总体算法 DFS算法 具体实现(C语言) 在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑

    2024年02月05日
    浏览(78)
  • Java 数据结构篇-实现堆的核心方法与堆的应用(实现 TOP-K 问题:最小 k 个数)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍      文章目录         1.0 堆的说明         2.0 堆的成员变量及其构造方法          3.0 实现堆的核心方法         3.1 实现堆的核心方法 - 获取堆顶元素 peek()         3.2 实现堆的核心方法 - 下潜 do

    2024年02月04日
    浏览(54)
  • 【数据结构和算法】种花问题

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 ​​​​​方法一:贪心 2.2 贪心算法一般思路 三、代码 3.1 ​​​​​方法一:贪心 四、复杂度分析 4.1 ​​​​​方法一:贪心 

    2024年01月20日
    浏览(44)
  • 数据结构与算法 -- 子序列问题

    一、子序列问题         子数组问题是连续的,而子序列问题是不连续的。比如说字符串 “I wanna keep a giraffe in my backyard” 的一种子序列就可以是 “Igbackd”。 子序列不再要求答案是一个连续的串。一个字符串的子序列,是由原字符串在不改变字符的相对顺序的情况下删

    2024年02月09日
    浏览(54)
  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

    2024年02月03日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包