9.9递归和动态规划(九)——N皇后

2015年8月14日 10点热度 0条评论 来源: half1_2_1

/**

 * 功能:打印八皇后在8*8棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。

 * 这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。

 */

	static int GRID_SIZE=8;

	/**
	 * 思路:每一行只能摆放一个皇后,因此不需要将棋盘存储为完整的8*8矩阵,只需一维数组,其中columns[r]=c表示有个皇后位于r行c列。
	 * @param row
	 * @param columns
	 * @param results
	 */
	public static void placeQueen(int row,Integer[] columns,ArrayList<Integer[]> results){
		if(row==GRID_SIZE){
			/*Creates and returns a copy of this object. The precise meaning of "copy" may depend on the class of the object.
			 *  The general intent is that, for any object x, the expression: 
			    x.clone() != x				will be true.
			 *  and that the expression: 
			 	x.clone().getClass() == x.getClass()	will be true. 
			 *	but these are not absolute requirements. While it is typically the case that: 
			 	x.clone().equals(x)	will be true, this is not an absolute requirement. */
			results.add(columns.clone());			
		}else{
			for(int col=0;col<GRID_SIZE;col++){
				if(checkValid(columns,row,col)){
					columns[row]=col;//摆放皇后
					placeQueen(row+1, columns, results);
				}
			}
		}
	}
	
	/**
	 * 检查(row,column)是否可以摆放皇后,方法:
	 * 检查有无其他皇后位于同一列或对角线,不必检查是否在同一行上,因为调用placeQueen时,一次只会摆放一个皇后。由此可知,这一行是空的。
	 * @param columns
	 * @param row
	 * @param column
	 * @return
	 */
	public static boolean checkValid(Integer[] columns,int row,int column){
		for(int r=0;r<row;r++){
			int c=columns[r];
			/* 检查同一列是否有皇后 */
			if(c==column)
				return false;
			
			/* 检查对角线:
			 * 若两行的距离等于两列的距离,则表示两个皇后在同一对角线上。
			 */
			int columnDistance=Math.abs(c-column);
			int rowDistance=row-r;//row>r,不用取绝对值
			if(columnDistance==rowDistance)
				return false;
		}
		
		return true;
	}

    原文作者:half1_2_1
    原文地址: https://blog.csdn.net/shangqing1123/article/details/47661353
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。