"教主" 楼天城 ony.ai CTO 在量子位微信公众号上出了一个问题：17皇后有多少组解？
我自己写了一份代码，代码如下
public class QueenProblem {
// 一组解
public static class QueenResult{
// result[i] 代表第 i 行, result[i]列放一个皇后
public int []result;
public QueenResult(int[] a) {
result = new int[a.length];
for(int i = 0; i < a.length; i++) {
result[i] = a[i];
}
}
}
public static long countQueenProblemResults(int n) {
// a[i] 代表第 i 行, a[i]列放一个皇后
int [] a = new int[n];
long count = 0;
// 保存解，n 较大时，解太多,不要开启
//List results = new ArrayList<>();
for(int i = 0; i < n; i++) {
a[i] = i;
}
int row = 1;
int method = 0; // 0: new , 1: next
// 当 row 小于 0 ，说明回溯到没有得选择了，结束循环
while(row >= 0) {
if(!pickup(a, row, method)) {
// 这一行已经没有可能的选择时，返回到上一行
row = row - 1;
method = 1;
}else {
if(row == (n-1)) {
// 在最后一行，说明得出一个解
count = count + 1;
//results.add(new QueenResult(a));
// 返回到上一行，尝试另外一个值作为列时，有哪些解
row = row - 1;
method = 1;
}else {
// 移动到下一行，选择下一行的列
row = row + 1;
method = 0;
}
}
}
// for(QueenResult res : results) {
// print(res);
// }
return count;
}
private static void print(QueenResult res) {
int len = res.result.length;
for(int i = 0; i < len; i++) {
for(int j = 0; j < res.result[i]; j++) {
System.out.print("* ");
}
System.out.print("1 ");
for(int j = res.result[i] + 1; j < len; j++) {
System.out.print("* ");
}
System.out.println("");
}
System.out.println("++++++++++++++++++++++++++++");
}
/**
* 计算 row 行的皇后放在哪一个列上。
* @param a
* @param row
* @param method 0 代表为该行重新选择, 1 代表为该行选择下一个
* @return
*/
private static boolean pickup(int []a, int row, int method) {
boolean ret;
if(0 == method) {
// 既然是重新选择，那么[row,a.lenght) 的都应纳入选择的范围
ret = pickup(a, row, row, a.length);
}else {
// 为 row 行选择下一个列：这个选择的列必须比当前列大，且满足不
// 在对角线上的列当中的最小值
// [row+1, a.length) 比 v=a[row] 大的移动到前面，使得大的聚集在 [row,end) 段中.
int end = row;
int v = a[row]; // 必须先保存下来
int temp;
for(int i = row + 1; i < a.length; i++) {
if(a[i] > v) {
temp = a[end];
a[end] = a[i];
a[i] = temp;
end = end + 1;
}
}
ret = pickup(a, row, row, end);
}
return ret;
}
/**
* 计算 row 行的皇后放在哪一个列上。 这一个列应满足在a的 [begin, end) 中取值，
* 且和 [0, row)行放的皇后不在对角线上，最后选择满足这两个要求中的最小的列.
* @param a
* @param row
* @param begin
* @param end
* @return
*/
private static boolean pickup(int []a, int row, int begin, int end) {
int temp;
while(begin < end) {
int minIndex = begin;
// 我觉得判断和 [0, row)行放的皇后是否在对角线的计算量比较大，所以
// 先取出最小值，然后再判断是否在对角线。
for(int i = begin+1; i < end; i++) {
if(a[i] < a[minIndex]) {
minIndex = i;
}
}
if(isDiagonal(a, row, a[minIndex])) {
// minIndex 不符合，就把 minIndex 和 begin 对调，然后 begin 往后移一个，
// 看下一个最下值是否满足不在在对角线上
temp = a[begin];
a[begin] = a[minIndex];
a[minIndex] = temp;
begin = begin + 1;
}else {
// minIndex 满足条件, 代表 row 行的皇后目前可以放在 a[minIndex] 列，
// 所以此时需要把 a[row] 替换为 a[minIndex]
temp = a[row];
a[row] = a[minIndex];
a[minIndex] = temp;
return true;
}
}
return false;
}
/**
* 判断把皇后放在 (row, column) 上是否和 0 - (row-1) 行所放的皇后在对角线上
* @param a
* @param row
* @return
*/
private static boolean isDiagonal(int []a, int row, int column) {
boolean diagonal = false;
for(int i = 0; i < row; i++) {
int d1 = row - i;
int d2 = column - a[i];
// 45 度角或-45度角
if(d1 == d2 || -d1 == d2) {
diagonal = true;
break;
}
}
return diagonal;
}
public static void main(String[] args) {
for(int n = 14; n <= 17; n++) {
long begin = System.currentTimeMillis();
long count = countQueenProblemResults(n);
long end = System.currentTimeMillis();
System.out.println("n:" + n + " count:" + count + " pass:" + (end-begin)/1000);
}
}测试结果如下：
n:14 count:365596 pass:2
n:15 count:2279184 pass:14
n:16 count:14772512 pass:100
n:17 count:95815104 pass:716
写完代码后，第一次调试在判断是否在斜线上的方法 isDiagonal 出了点小问题，一下就定位到只比较了 d1==d2, 第二个条件忘记加了。增加后第二遍测试马上就通过了。
后面我和书上经典的代码（翻译成java）在同一台电脑测试比较了下，我的算法比书上的算法速度上快1倍多。因为我在计算下一行皇后放置的位置时是从剩下的可选择的列中选择的，而书上的代码为了简洁总是全部列中扫描一遍。在返回到上一行的选择时，书上的代码总是从上一次的位置依次往后选择，而我的代码是先从剩下的列中刷选出比当前列大的列，然后依次选择。
