目前最快的N皇后问题算法！！！

Question

最近老师布置了一道算法题目－－N皇后问题。这个算法在本科时已经做过，现在的要求是尽可能的提高算法的执行效率。如果采用传统的办法，用3个数组来记录列、主对角线和次对角线的方式，虽然优化过语句，并且使用对称原则来减少一半的运算时间，但在1.66Ghz的机器上计算16皇后仍需要100多秒。
有的同学使用多线程方式来改进了算法，有效利用了服务器的多个CPU同时计算，好像在4CPU机器上用了17秒。但我觉得这并没有体现出算法的高效。
昨天在google上有幸找到了一个难得一见的算法，在1.66Ghz的机器上计算16皇后才用了35秒，是我目前见到的最快的皇后问题算法了。简单的看了一下算法原理，它有别于传统的数组判断模式，而是采用了位运算。我也跟踪了几个变量的位结构变化情况，但是直到今天仍没能理解作者对该算法的设计思想和算法原理。
因此期望CSDN中的算法高手不吝赐教，能对这个算法做个注释，并描述一下算法原理，在下感激不仅！
原始程序是C语言版的，我把它转换成Java语言版，并且惊奇的发现，几乎是一样的程序，Java执行速度居然比C的快了2秒。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
import java.util.Calendar;public class Queen { public static int sum = 0, upperlimit = 1; public static void compute(int row, int ld, int rd) { if (row != upperlimit) {
int pos = upperlimit & ~(row | ld | rd);
while (pos != 0) { int p = pos & -pos;
pos -= p;
compute(row + p, (ld + p) << 1, (rd + p) >> 1);
} } else
sum++;
} public static void main(String[] args) {
Calendar start;
int n = 8; if (args.length > 0)
n = Integer.parseInt(args[0]);
start = Calendar.getInstance();
if ((n < 1) || (n > 32)) {
System.out.println(" 只能计算1-32之间\n");
return;
}
System.out.println(n + " 皇后\n");
upperlimit = (upperlimit << n) - 1;
compute(0, 0, 0);
System.out.println("共有"
+ sum
+ "种排列, 计算时间"
+ (Calendar.getInstance().getTimeInMillis() - start
.getTimeInMillis()) / 1000 + "秒 \n");
}}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

Answer 1

这是C语言版本，请大家分析一下了：#include <stdio.h>
#include <stdlib.h>
#include <time.h>long sum = 0, upperlim = 1;void test(long row, long ld, long rd)
{if (row != upperlim)
{
long pos = upperlim & ~(row | ld | rd);
while (pos)
{
long p = pos & -pos;pos -= p;
test(row + p, (ld + p) << 1, (rd + p) >> 1);
}
} else
sum++;
}int main(int argc, char *argv[])
{
time_t tm;
int n = 16;if (argc != 1)
n = atoi(argv[1]);
tm = time(0);
if ((n < 1) || (n > 32))
{
printf(" 只能计算1-32之间\n");
exit(-1);
}
printf("%d 皇后\n", n);
upperlim = (upperlim << n) - 1;test(0, 0, 0);
printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}

Answer 2

在C语言版已经有不少同志做了详细分析和解答，大家可以参考一下：
http://community.csdn.net/Expert/TopicView3.asp?id=4709025