skdbf的gravatar头像
skdbf 2015-03-20 21:00:16

八皇后问题java代码算法解法

八皇后问题
是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

解的个数
下表给出了 n 皇后问题的解的个数包括独立解U(OEIS中的数列A002562)以及互不相同的解D(OEIS中的数列A000170)的个数:

n 1 2 3 4 5 6 7 ... 26
U 1 0 0 1 2 1 6 ... 2,789,712,466,510,289
D 1 0 0 2 10 4 40 ... 22,317,699,616,364,044

 

下面的代码都有注释:

Queen.java

package package1;

public class Queen{
	private int x,y;
	
	Queen(int x,int y){
		this.x=x;
		this.y=y;
	}
	int getX(){
		return x;
	}
	int getY(){
		return y;
	}
	void setX(int x){
		this.x = x;
	}
	
	void setY(int y){
		this.y = y;
	}
	
	boolean isAttack(Queen m, Queen n){  //判断是否相互攻击
		int x1 = m.getX();
		int x2 = n.getX();
		int y1 = m.getY();
		int y2 = n.getY();
		if(y1==y2||y1-y2==x1-x2||y1-y2==x2-x1){
			return true;
		}
		return false;
	}
	
	boolean isFine(Queen[] q){
		for(int i=0; i<this.x;i++){
			if(isAttack(this,q[i])){ //之前所有的数组元素和这时的数组元素之间判断是否攻击
			return false;
			}
		}
		return true;	
		}
}

Resolve.java

package package1;
import javax.swing.JOptionPane;
public class Resolve {
	static int count=0;
	static int N;
	
	public static Queen[] setQueen(Queen[] q,int i){ 
		if(i>N-1){
			printQueen(q);
			count++;
			return q;
		}
		
		for(int j=0;j<N;j++){  //用j来控制列
			q[i]=new Queen(i,j);
			if(q[i].isFine(q)) //判断(i,j)坐标的这个数组元素是否能成为皇后的点
				
				if(setQueen(q,i+1)==null)
				continue;
		}	
			return null;
	}
	
	public static void printQueen(Queen[]q){  //打印出符合条件的坐标
		for(int i=0;i<N;i++){
		  System.out.print("( "+i+" , "+q[i].getY()+" )");
		}
		System.out.println();
	}
	
	public static void main(String[] args){
		 String str = JOptionPane.showInputDialog(null,"please enter the number of Queens","N Queens",
				               JOptionPane.QUESTION_MESSAGE);
		 N = Integer.parseInt(str);
			Queen []q = new Queen[N];
            setQueen(q,0);
            System.out.println("解的总数为"+count);
		   
		
	}

}

打赏

顶部 客服 微信二维码 底部
>扫描二维码关注最代码为好友扫描二维码关注最代码为好友