USACO Section 1.5.4 [Checker Challenge] Java题解

题意分析：
该题是需要深度优化的八皇后问题，首先看一下，经典八皇后问题的一般解法：

public class Queens {
	private final static int MAX = 8;
	// site[i] = j => col:i row:j
	private static int[] site = new int[MAX];

	private static boolean check(int col){
		for(int i = 0; i < col; i++){
			if(site[i] == site[col] || //不在一行上
				Math.abs(site[col]-site[i]) == col - i) //也不在对角线上
			return false;
		}
		return true;
	}
	
	private static void queens(int col){
		if(col == MAX)
			;//output();
		else
			for(int i = 0; i < MAX; i ++){
				site[col] = i;
				if(check(col))
					queens(col+1);
			}
	}
	
	public static void main(String[] args){
		queens(0);
	}
}

该题不一样的地方有：
1）N不是8，而是6-13
2）需输出结果个数和头3个结果

解题思路：
1）只考虑一半的column结果乘以2，另一半认为是沿中心垂直对称的。如果N是奇数，则结果中数量要补上中间那条column。
2）优化对角线的判断，使之成为搜索的状态，而不是每次判断都要重新算（这里和The Clocks这一题有异曲同工）。可以发现两条对角线上的元素特征分别是i+j以及i-j+N是相同的，因此开两个2×N大小的int数组来记录占用情况。注意此处不是boolean而是int的原因是占用的影响有累积效应。
3）同理，可以优化列占用情况。（和上述八皇后不同的是，这题必须一行一行考虑）
4）小数据的情况要特别考虑，该题中N为6时，优化check是可以用的，但是由于要输出3个结果，只查找一半是不可行的，要查找全部。

代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/checker.java