/**

 * 功能：打印八皇后在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;

	}