当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-八皇后问题

发表于: 2012-01-20   作者:bylijinnan   来源:转载   浏览次数:
摘要: public class EightQueen { /** * 八皇后问题 * obviously,the location of a queen includes two index: row and column * 1.the eight queens should be put in different rows and different columns

public class EightQueen {

	/**
	 * 八皇后问题
	 * obviously,the location of a queen includes two index: row and column
	 * 1.the eight queens should be put in different rows and different columns
	 * 2.so,a integer array-(we name it columnIndex[8])
	 *    the index of array is from 0 to 7,we can use it as the rowIndex of a location:
	 *    rowIndex:     0  1  2  3  4  5  6  7 
	 *    columnIndex:  a0 a1 a2 a3 a4 a5 a6 a7(well,ai=columnIndex[i])
	 * 3.a0 a1 a2 a3 a4 a5 a6 a7 is a permutation of (0 1 2 3 4 5 6 7)
	 * 4.we output the permutations which does not violate the rules of EightQueen:
	 * 	 "任两个皇后都不能处于同一条横行、纵行或斜线上"
	 * 5.but how to judge?
	 *   let's look at this.we assume that after a permutation,the status is:
	 *     i= 0 1 2 3 4 5 6 7
	 *   a[i]=0 4 5 7 2 6 1 3
	 *   we found that (1,4) and (2,5) share the same diagonal.
	 *   that is a[i]-a[j]=i-j or a[i]-a[j]=j-i
	 * 
	 */
	public static void main(String[] args) {
		int MAX=8;
		int[] columnIndex=new int[MAX];
		for(int i=0;i<MAX;i++){
			columnIndex[i]=i;
		}
		eightQueen(columnIndex,0,MAX-1);//permutation(a,0,a.length-1)
		System.out.println(sum);
	}

	private static int sum;
	//produce permutation,print it if it obeys the rules of EightQueen
	public static void eightQueen(int[] columnIndex,int first,int last){
		if(first==last){
			if(check(columnIndex)){
				printQueenLocation(columnIndex);
				sum++;
			}
		}else{
			for(int i=first;i<=last;i++){
				swap(columnIndex,first,i);
				eightQueen(columnIndex,first+1,last);
				swap(columnIndex,first,i);
			}
		}
	}
	
	
	//the rule:can't be (a[i]-a[j]=i-j or a[i]-a[j]=j-1)
	public static boolean check(int[] columnIndex){
		boolean re=true;
		for(int i=0,len=columnIndex.length;i<len;i++){
			for(int j=i+1;j<len;j++){
				if((j-i==columnIndex[j]-columnIndex[i])||(i-j==columnIndex[j]-columnIndex[i])){
					re=false;
					break;
				}
			}
		}
		return re;
	}
	
	//print (i,j)
	public static void printQueenLocation(int[] columnIndex){
		for(int i=0,len=columnIndex.length;i<len;i++){
			System.out.print("(i,j)=("+i+","+columnIndex[i]+")");
		}
		System.out.println();
	}
	
	public static void swap(int[] a, int i, int j){
		int temp =a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

java-八皇后问题

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
《C和指针》第8章编程练习第8题: 1 /* 2 ** 八皇后问题 3 */ 4 5 #include <stdio.h> 6 #def
#include"stdio.h" #definenum8 inta[num][num],count=0; FILE*fw; intjudge() { intaa=0,bb=0; int
对角线线序 /** * @author hwy1782@gmail.com * @creation date 2010-8-22 上午11:18:47 * * 八皇后
题目:在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行、同一列或
八 皇后 问题,是一个古老而著名的问题,是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝
西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无
八皇后问题 八 皇后问题,是一个古老而著名的问题,是 回溯算法的典型例题。该问题是国际西洋棋棋手
一,问题描述 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一
暑假过了一半多了,前几天看到八皇后问题,就写了出来,使用回溯法。 八皇后问题:在8*8格的国际象
这几天突然对八皇后问题很感兴趣,准备自己动手实现它,从最笨的办法一直到用图论实现,展示出它的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号