八皇后-位运算版

   八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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行，找到的解的个数加一。