回溯法求N皇后问题

 回溯法：是一种选优搜索法， 回溯法从开始节点（根节点）出发，以深度优先方式搜索整个解空间。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

N皇后问题描述：在n乘n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之在同行或同列或同一斜线上的棋子。n后问题等价于在n 乘 n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

求解思路：有序地从第 1 行的第 1 列开始，尝试放上一个皇后，然后再尝试第 2 行的第几列能够放上一个皇后，如果第 2 行也放置成功，那么就继续放置第 3 行，如果此时第 3 行没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，最后得到和规则的解。

package 算法实验;
/**
 * n皇后类
 *  回溯法求n皇后
 *
 */
public class NQueens {
	private static int queensNum ;//皇后的个数
	//定义一个数组，x[k]表示第k行的列数，x[k]=j表示第k行的第j位置放一位皇后
	private static int []x;
	/**
	 * 产生n位皇后的方法
	 */
	public void produceNQueens(){
		x[1]=0;//每一行从0开始
		int k=1;//从第1行开始
		while(k>0){
			x[k]=x[k]+1;
			while((x[k]<=queensNum)&&!(place(k)))//判断约束条件
				x[k]=x[k]+1;
			if(x[k]<=queensNum)
				if(k==queensNum)
				{
					//输出各行皇后的位置
					for(int i=1;i<=queensNum;i++)
					System.out.print("("+i+","+x[i]+") ");
					System.out.println();
				}
				else {
					k++;
					x[k]=0;
				}
			else k--;//回溯
		}
			
	}
	/**
	 * 判断放置皇后的约束条件的方法
	 * @param k
	 * @return
	 */
	public boolean place(int k){
		for(int j=1;j<k;j++)
			//任何2个皇后不能放在同一行或同一列或同一斜线上。
			if((Math.abs(j-k))==(Math.abs(x[j]-x[k]))||(x[j]==x[k]))return false;
		return true;
		
	}
	/**
	 * 程序入口：主函数
	 * @param args
	 */
	public static void main(String[] args){
		 queensNum=4;//给皇后个数初始值
		x = new int[queensNum+1];//给数组x赋长度
		//实例化对象
		NQueens nq = new NQueens();
		System.out.println(+queensNum+"位皇后的位置是：");
		//调用产生n位皇后的方法
		nq.produceNQueens();
	}

}

 

当N=4时，运行结果是：

 4位皇后的位置是：
(1,2) (2,4) (3,1) (4,3)
(1,3) (2,1) (3,4) (4,2)

 

 当N=6时，运行结果是：

 6位皇后的位置是：
(1,2) (2,4) (3,6) (4,1) (5,3) (6,5)
(1,3) (2,6) (3,2) (4,5) (5,1) (6,4)
(1,4) (2,1) (3,5) (4,2) (5,6) (6,3)
(1,5) (2,3) (3,1) (4,6) (5,4) (6,2)