`

八皇后-位运算版

 
阅读更多


   八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。   

 

import java.util.Calendar;

public class BaHuangHou {
	public static int sum = 0, upperlimit = 1;
	/**
	 * 
	 * @param row 纵列
	 * @param ld 左斜线
	 * @param rd 右斜线
	 */
	public static void compute(int row, int ld, int rd) {
		//当row=11111111的时候,就是全部找完了。
		if (row != upperlimit) {
			//找到该列的所以可以放的位置
			int pos = upperlimit & ~(row | ld | rd);
			
			while (pos != 0)
				
			{
				//取出第一个可以放的位置,也就是最右边的1
				int p = pos & -pos;
				//去除刚取出来的位置
				pos -= p;
				//继续寻找,个个参数平移一位
				compute(row + p, (ld + p) << 1, (rd + p) >> 1);
				
			}
		} 
		else  sum++;//种数自加
	}

	public static void main(String[] args) {
		Calendar start;
		
		//输入皇后数字
		int n = 8;
		//设置开始时间
		start = Calendar.getInstance();
		//保证数字在1到32之间,避免系统溢出
		if ((n < 1) || (n > 32)) {
			System.out.println(" 只能计算1-32之间\n");
			
			return;
		}
		
		System.out.println(n + " 皇后\n");
		//结束标志 uperlimti=255 转换为二进制就是11111111
		upperlimit = (upperlimit << n) - 1;
		//从0,0,0开始
		compute(0, 0, 0);
		
		System.out.println("共有"
				+ sum
				+ "种排列, 计算时间"
				+ (Calendar.getInstance().getTimeInMillis() - start
						.getTimeInMillis()) / 1000 + "秒 \n");
		
	}

}

 

乍一看似乎完全摸不着头脑,实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟,实在没研究出来再看下面的解说。

  
    和普通算法一样,这是一个递归过程,程序一行一行地寻找可以放皇后的地方。过程带三个参数,row、ld和rd,分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例,看看程序是怎么工作的。假设现在已经递归到第四层,前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置,位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来,得到该行所有的禁位,取反后就得到所有可以放的位置(用pos来表示)。p=p = pos & -pos;其结果是取出最右边的那个1。这样,p就表示该行的某个可以放子的位置,把它从pos中移除并递归调用compute过程。注意递归调用时三个参数的变化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要平移一位。最后,如果递归到某个时候发现row=111111了,说明六个皇后全放进去了,此时程序从第1行跳到第11行,找到的解的个数加一。

 

 

分享到:
评论

相关推荐

    八皇后 的三种解法 (java编写)

    总的来说,这三份Java代码为我们提供了学习和理解八皇后问题的不同角度,包括回溯法、位运算以及可能的优化技巧。通过阅读和分析这些代码,我们可以深入理解如何用编程语言解决实际问题,同时提升我们的算法设计和...

    八皇后课程设计 源程序 流程表 运算结果

    八皇后课程设计 源程序 流程表 运算结果 八皇后课程设计 源程序 流程表 运算结果

    c++代码运用回溯与位运算算法实现N-皇后问题

    本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非...N-皇后问题是八皇后问题的拓展,要解决八皇后问题只需要将输入的值赋为8即可。

    用汇编语言编写八皇后问题并将结果显示在屏幕上

    根据给定文件的信息,本文将围绕“用汇编语言编写八皇后问题并将结果显示在屏幕上”的主题进行详细解析。首先,我们需要了解八皇后问题的基本概念及其解决思路,随后深入探讨汇编语言实现的具体细节。 ### 八皇后...

    8086汇编八皇后图形输出草稿

    在8086汇编语言中,实现八皇后问题的图形输出是一项挑战,因为它涉及到屏幕显示、内存管理和算法设计等多个方面。"8086汇编八皇后图形输出草稿"是一个项目,其目标是在640x480分辨率且支持16色的显示器上以图形方式...

    八皇后算法C语言实现

    在八皇后问题中,可以使用位操作来表示棋盘的状态,每个皇后的位置对应一个二进制位,如第i行皇后位置可以用2^(i-1)表示,通过按位与、按位或等操作可以快速检查某行、某列或对角线是否已有皇后。 2. **数组和矩阵*...

    广度优先+深度优先求解八皇后问题.zip

    在实际代码中,可能会有额外的优化措施,如使用位运算来高效地检查和设置棋盘状态,或者使用标志来跟踪已尝试过的位置,以减少不必要的计算。 总之,这个压缩包提供了使用两种不同搜索策略解决八皇后问题的Java实现...

    八皇后问题课程设计C++版

    这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。我的...

    N皇后 八皇后

    《N皇后问题与八皇后问题的C++实现》 N皇后问题和八皇后问题是计算机科学领域经典的回溯算法实例,其主要目标是在一个N×N的棋盘上放置N个皇后,使得任意两个皇后都无法在同一行、同一列或同一对角线上相互攻击。这...

    八皇后问题(留有宏定义接口 扩展到N皇后)

    八皇后问题是一个经典的问题,在棋盘上放置八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一对角线上。这个问题在计算机科学中常被用来教授回溯法和递归思想。在这个实现中,我们不仅解决...

    bahuanghou.rar_栈八皇后

    标题中的“bahuanghou.rar_栈八皇后”暗示了这是一个关于解决八皇后问题的程序,使用了栈作为数据结构,编程语言为C。八皇后问题是经典的计算机算法问题,目标是在一个8x8的棋盘上放置八个皇后,使得任何两个皇后都...

    数据结构课件 课程设计 马的遍历,八皇后问题等!

    这需要利用回溯、递归等方法来尝试所有可能的放置方案,并通过位运算或者数组来标记已放置的皇后位置,避免冲突。此问题能锻炼对冲突检测和解决方案优化的能力,是学习算法和数据结构的好例子。 在课程设计中,这些...

    八皇后问题

    总的来说,解决八皇后问题需要理解并运用回溯法、递归、数组(或位运算)表示以及问题的约束条件。通过这个题目,程序员可以锻炼逻辑思维能力,学习如何处理复杂问题的求解策略。在分析提供的压缩包文件...

    kechengsheji.rar_八皇后

    在计算机科学领域,八皇后问题是一个经典的问题,它涉及到算法设计、回溯法以及位运算等核心概念。该问题由19世纪的数学家弗里德里希·高斯提出,要求在8×8的棋盘上摆放8个皇后,使得任意两个皇后都不能在同一行、...

    八皇后问题八皇后问题

    - 为了避免重复计算,可以使用位运算来标记列和对角线的状态,提高效率。 - 使用深度优先搜索(DFS)进行回溯,因为八皇后问题的解数量相对较少,DFS通常足够高效。 7. **实际应用**: - 八皇后问题的解决思路...

    八皇后问题求解——之递归

    ### 八皇后问题求解——之递归 #### 一、八皇后问题概述 八皇后问题是由国际西洋棋棋手马克斯·贝瑟尔在1848年提出的经典问题。这个问题要求在8×8的国际象棋棋盘上放置八个皇后,使得任意两个皇后之间都不能相互...

    数据结构课程设计之八皇后求解

    总的来说,八皇后问题的求解是对数据结构和算法的实践运用,它涵盖了回溯法、递归、位运算以及基础的用户交互设计。这个课程设计有助于提升学生的逻辑思维能力和编程技巧,同时也是对经典问题的现代计算机科学解答。

    八皇后leetcode-codekata:纯娱乐

    八皇子leetcode 编码实践 ...八皇后拼图中的实现。 中实施。 参考 依赖注入 设计模式 编程语言 函数式编程 编程生活 数字用户线 敏捷 微服务架构 Java 杂项container_of(ptr,类型,成员) 人工智能 并发

Global site tag (gtag.js) - Google Analytics