`
endual
  • 浏览: 3566272 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

java 回溯法求解 8皇后问题

 
阅读更多

 

package endual;

public class Queen {

	private final int size = 8;           // 棋盘的大小
	private int[] location ;              //皇后在棋盘上的每一行的列的位子
	private int[] colsOccupied ;          //皇后在棋盘上占据的列
	private int[] cross1Occuptied ;       //皇后在棋盘上占据的正对角线
	private int[] cross2Occuptied ;       //皇后在棋盘上占据的是反对角线
	private static int count ;       //解决的方法的个数
	
	
	
	private static final int STATUS_OCCUPIED = 1 ; //占据的状态
	private static final int STATUS_OCCUPY_CANCELED = 0 ; //没有占据的状态
	
	public Queen() {

		this.location = new int[this.size];
		this.colsOccupied = new int[this.size];
		this.cross1Occuptied = new int[2*this.size];
		this.cross2Occuptied = new int[2*this.size];
	}
	
	public void printLocation() {
		
		System.out.println("以下是皇后在棋盘上的第" +count+"种方式的摆放");
		for (int i=0; i <this.size; i++) {
			
			System.out.println("行:" + i + " 列:" + this.location[i]) ;
		}
	} //end 打印
	
	/*判断位子(i,j)是否被占领了*/
	private boolean isOccupied(int i, int j) {
	
		if(this.colsOccupied[j] == 1) {
			return true ;
		}
		
		if(this.cross1Occuptied[i-j+this.size-1] == 1) {
          return true ;
		}
		
		if (this.cross2Occuptied[i+j] == 1) {
			return true ;
		}
		
		return false ;
	}
	
	/**
	 * 如果flag为1,表示占领位子(i,j);
	 * 如果flag为0,表示取消占领位子(i,j) ;
	 */
	
	private void setStatus(int i, int j, int flag){
		
		this.colsOccupied[j] = flag ; //宣布占领或者是取消占领第j列
		this.cross1Occuptied[i-j+this.size-1] = flag ; //宣布占领或者取消占领正对角线
		this.cross2Occuptied[i+j] = flag ;    // 宣布占领或取消占领反对角
		

	}
	
	/**第一行开始摆放皇后**/
	public void place(int i) {
		
		for (int j=0; j < this.size; j++) { //在第i行尝试把皇后放在每一列
			
			if (!this.isOccupied(i, j)) { //判断该位子是不是已经被占领了的
				
				this.location[i] = j ; //摆放皇后,在第i行把皇后放在第j列
				this.setStatus(i, j, this.STATUS_OCCUPIED) ; //已经被占领了的
				
				if (i < this.size-1) {
					this.place(i+1) ;
					
				}else {
					this.count++ ;
					this.printLocation() ;
				}
				//回溯法
				this.setStatus(i, j, STATUS_OCCUPY_CANCELED) ;
				
			}

		}

	}

	public void start() {
		
		this.place(0) ;
	}
	
}

 

 测试的

 

package endual;

/**
 * 八皇后问题是一个古来而著名的问题,该问题是19世纪著名的数学家高斯同学提出来的。在8*8的国际象棋
 * 上摆放八个皇后,使其不能互相的攻击,也就是说,任意的两个皇后不能放在同一行或则是同一个列或者是
 * 同一个对角线上,问有多少个摆放的方法
 * @author Endual
 *
 *
 *
 */

public class MainApp {
	
	public static void main(String[] args) {
		
		Queen queen = new Queen() ;
		queen.start(); 

	}

} 

 

  要不来看下结果吧:部分的

 

 

以下是皇后在棋盘上的第1种方式的摆放
行:0 列:0
行:1 列:4
行:2 列:7
行:3 列:5
行:4 列:2
行:5 列:6
行:6 列:1
行:7 列:3
以下是皇后在棋盘上的第2种方式的摆放
行:0 列:0
行:1 列:5
行:2 列:7
行:3 列:2
行:4 列:6
行:5 列:3
行:6 列:1
行:7 列:4
以下是皇后在棋盘上的第3种方式的摆放
行:0 列:0
行:1 列:6
行:2 列:3
行:3 列:5
行:4 列:7
行:5 列:1
行:6 列:4
行:7 列:2
以下是皇后在棋盘上的第4种方式的摆放
行:0 列:0
行:1 列:6
行:2 列:4
行:3 列:7
行:4 列:1
行:5 列:3
行:6 列:5
行:7 列:2
以下是皇后在棋盘上的第5种方式的摆放
行:0 列:1
行:1 列:3
行:2 列:5
行:3 列:7
行:4 列:2
行:5 列:0
行:6 列:6
行:7 列:4
以下是皇后在棋盘上的第6种方式的摆放
行:0 列:1
行:1 列:4
行:2 列:6
行:3 列:0
行:4 列:2
行:5 列:7
行:6 列:5
行:7 列:3
以下是皇后在棋盘上的第7种方式的摆放
行:0 列:1
行:1 列:4
行:2 列:6
行:3 列:3
行:4 列:0
行:5 列:7
行:6 列:5
行:7 列:2
以下是皇后在棋盘上的第8种方式的摆放
行:0 列:1
行:1 列:5
行:2 列:0
行:3 列:6
行:4 列:3
行:5 列:7
行:6 列:2
行:7 列:4
以下是皇后在棋盘上的第9种方式的摆放
行:0 列:1
行:1 列:5
行:2 列:7
行:3 列:2
行:4 列:0
行:5 列:3
行:6 列:6
行:7 列:4
以下是皇后在棋盘上的第10种方式的摆放
行:0 列:1
行:1 列:6
行:2 列:2
行:3 列:5
行:4 列:7
行:5 列:4
行:6 列:0
行:7 列:3
以下是皇后在棋盘上的第11种方式的摆放
行:0 列:1
行:1 列:6
行:2 列:4
行:3 列:7
行:4 列:0
行:5 列:3
行:6 列:5
行:7 列:2
以下是皇后在棋盘上的第12种方式的摆放
行:0 列:1
行:1 列:7
行:2 列:5
行:3 列:0
行:4 列:2
行:5 列:4
行:6 列:6
行:7 列:3
以下是皇后在棋盘上的第13种方式的摆放
行:0 列:2
行:1 列:0
行:2 列:6
行:3 列:4
行:4 列:7
行:5 列:1
行:6 列:3
行:7 列:5
 

 

 

 

 

 

 

分享到:
评论

相关推荐

    基于回溯法求解八皇后

    回溯法求解八皇后问题。程序用java实现

    n后问题回溯算法 java

    总结起来,n皇后问题通过回溯算法在Java中的实现,不仅锻炼了我们的逻辑思维能力,也让我们更好地理解了递归和回溯这两种重要的编程技巧。同时,这个问题也为我们提供了一个在有限搜索空间中寻找解的有效方法,这在...

    基于Java实现的回溯法解决N皇后问题的实验报告

    内容概要:本文档详细介绍了利用Java实现回溯法求解经典的N皇后问题的过程。文章首先简要介绍了回溯法的基本概念及其特性,然后针对具体问题——N皇后问题进行了深入剖析,探讨了如何采用合适的数据结构提高解题效率...

    分支限界法解决N皇后问题

    使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。

    八皇后问题的LasVegas算法与回溯法的混合实现

    八皇后问题的MonteCarlo算法与回溯法的混合实现,代码精确实现,实验报告或者说论文有详细的阐述!

    n皇后问题(队列分支限界法)

    这个问题是回溯算法和分支限界法的良好应用实例,旨在展示如何在有限的搜索空间中找到所有可能的解决方案。 在描述中提到的"队列分支限界法"是一种特殊的搜索策略,它结合了广度优先搜索(BFS)的队列结构和分支...

    八皇后问题求解 java

    在这个Java程序设计中,我们将深入探讨如何利用回溯法来解决八皇后问题。 回溯法是一种试探性的解决问题的方法,它尝试逐步构造可能的解决方案,如果在某一步发现当前的选择不能导致有效的解决方案,就会撤销这一步...

    数独游戏的回溯法求解

    总结来说,本实例通过Java的回溯法实现了数独游戏的求解,深入展示了递归和回溯法在解决复杂问题时的强大能力。理解并掌握这种算法对于提升编程思维和问题解决技巧具有重要意义。在实际应用中,回溯法不仅适用于数独...

    java求解n queques 问题-八皇后问题

    利用回溯法求解八皇后问题,从八皇后问题延伸到n皇后问题。利用水平,主对角线,反对角线三个数组简化算法。 使用方法: 输入要求解的n皇后数目,程序自动输出每种具体方案和总的方法数。

    Queen(回溯法之n后问题)

    Queen(回溯法之n后问题) 八皇后问题用回溯法求解,皇后个数自己任意输入,dos下图解显示。vc6.0中编译通过。

    Java回溯法求分割回文字符串源码

    在编程领域,回溯法是一...通过这个Java回溯法求分割回文字符串的源码,我们可以学习到如何运用回溯法来解决字符串处理问题,以及如何在Java中实现这种算法。这不仅锻炼了我们的逻辑思维能力,也加深了对回溯法的理解。

    回溯算法java实例

    回溯算法是一种在解决问题时,通过尝试所有可能的解决方案,并在发现不符合条件的解时,及时退回并尝试其他可能性的...通过实践和理解回溯法在八皇后问题和迷宫寻路中的应用,你可以逐步提升自己的算法思维和编程能力。

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

    这个问题在计算机科学中常被用来作为算法和回溯法的示例。本压缩包包含了两种不同的解决方法:广度优先搜索(BFS)和深度优先搜索(DFS),均使用Java编程语言实现。 首先,我们来详细解释广度优先搜索(BFS)。BFS...

    N皇后问题,带界面的 java版

    这是一个典型的约束满足问题,通常使用回溯法来求解。 回溯法是一种试探性的解决问题的方法,当遇到无法满足条件的情况时,会撤销之前的选择,尝试其他路径。在N皇后问题中,回溯法的实现步骤如下: 1. 从第一行...

    N皇后问题的Java程序实现及分析.pdf

    在Java中,我们采用回溯法来实现N皇后问题的求解。回溯法是一种系统地搜索问题解的方法,它通过尝试分步去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,...

    java 实现N皇后问题源代码,不含界面代码

    该Java程序采用了回溯法来解决N皇后问题。回溯法是一种通过尝试解决子问题,并且能够撤销不成功的决定的方法。在这个例子中,我们尝试将每个皇后放置在棋盘的不同位置上,并检查是否违反了规则。如果违反了规则,则...

    学习常用算法之(3)回溯法

    在实际应用中,回溯法常用于解决如八皇后问题、数独问题、旅行商问题等。以全排列问题为例,可以通过一个二维数组记录当前数字的使用状态,来避免重复。Java代码中,`NAllArrangement`类展示了如何利用回溯法实现...

    回溯法入门学习之一

    // 调用回溯法求解 Solution solution = new Solution(problemData); solution.backtracking(); } } class Solution { private int[] data; public Solution(int[] data) { this.data = data; } ...

    java_n_queen.rar_0-1背包_n后回溯_queen

    在IT领域,特别是算法设计与实现中,"java_n_queen.rar_0-1背包_n后回溯_queen"这个标题暗示了两个经典的算法问题:N皇后问题和0-1背包问题,它们都是通过回溯法来解决的。下面将详细讲解这两个问题以及回溯法的概念...

    用遗传算法解决八皇后问题

    八皇后问题是一个经典的回溯法问题,它要求在8×8的棋盘上放置8个皇后,使得任意两个皇后都不能在同一行、同一列或同一条对角线上。这个问题的解决方案数量为92种,而通过遗传算法可以有效地寻找这些解。 遗传算法...

Global site tag (gtag.js) - Google Analytics