2008-02-04

八皇后问题

关键字: 算法 
public class Queens {
	private int[] queens = new int[8];	//解数组
	private int[] colflag =new int[8];	//列冲突标记
	private int[] flags1 = new int[15];	//对角线冲突标记
	private int[] flags2 = new int[15];	//对角线冲突标记
	private int roots ;
	private void trySet(int row){
		for (int column=0; column < 8; column++){
			if (colflag[column] == 0 
					&& flags1[row-column + 7]==0 
					&& flags2[row + column]==0 ){
				queens[row] = column;
				if (row <7){
					colflag[column] = 1;
					flags1[row-column + 7]= 1;
					flags2[row + column]=1;
					trySet(row+1);
				}else{
					roots ++;
					printit();
				}
				colflag[column] = 0;
				flags1[row-column + 7] = 0;
				flags2[row + column] = 0;
			}
		}
	}
	private void printit(){
		System.out.println (roots);
		for (int i = 0;i<8; i++){
			for (int j =0 ;j<8; j ++){
				if (queens[i]==j){
					System.out.print (" x");
				}else{
					System.out.print (" o");
				}
			}
			System.out.print("\n");
		}
		System.out.println("=================");
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new Queens().trySet(0);		
	}
}
评论
metaphy 2008-02-04
以下为已知的N-皇后解数目
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352
发表评论

您还没有登录，请登录后发表评论

metaphy
搜索本博客
我的相册
E4a25167-de99-3f5d-a292-f4dd7f86392a-thumb
theend
共 10 张
最近加入圈子
存档
最新评论