主 题： 目前最快的N皇后问题算法！！！
作 者： IceCraft (心淡情浓)
等 级：
信 誉 值： 100
所属社区： C/C++ C语言
问题点数： 100
回复次数： 75
发表时间： 2006-4-24 13:20:15
最近老师布置了一道算法题目－－N皇后问题。这个算法在本科时已经做过，现在的要求是尽可能的提高算法的执行效率。如果采用传统的办法，用3个数组来记录列、主对角线和次对角线的方式，虽然优化过语句，并且使用对称原则来减少一半的运算时间，但在1.66Ghz的机器上计算16皇后仍需要100多秒。
有的同学使用多线程方式来改进了算法，有效利用了服务器的多个CPU同时计算，好像在4CPU机器上用了17秒。但我觉得这并没有体现出算法的高效。
昨天在google上有幸找到了一个难得一见的算法，在1.66Ghz的机器上计算16皇后才用了35秒，是我目前见到的最快的皇后问题算法了。简单的看了一下算法原理，它有别于传统的数组判断模式，而是采用了位运算。我也跟踪了几个变量的位结构变化情况，但是直到今天仍没能理解作者对该算法的设计思想和算法原理。
因此期望CSDN中的算法高手不吝赐教，能对这个算法做个注释，并描述一下算法原理，在下感激不仅！
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
#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));
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
sankt(黄景天) ( ) 信誉：110 2006-4-24 14:33:13 得分: 0
学习
Top
Rick_ang(东方未名) ( ) 信誉：100 2006-4-24 15:07:48 得分: 0
学习..这个需要慢慢看
Top
universes(universes) ( ) 信誉：100 2006-4-24 15:14:38 得分: 0
mark
Top
languagec(各有所求) ( ) 信誉：98 2006-4-24 15:53:37 得分: 0
haha
Top
iamcaicainiao(菜菜鸟) ( ) 信誉：95 2006-4-24 16:03:29 得分: 0
学习+收藏
Top
jixingzhong(瞌睡虫：选择了远方，只顾风雨兼程！) ( ) 信誉：102 2006-4-24 16:03:37 得分: 0
没有注释，没有算法，
看起来就麻烦了 ...
楼主把这个算法的链接给出来吧，
在有算法的基础上，
看程序快一些 ...
Top
jixingzhong(瞌睡虫：选择了远方，只顾风雨兼程！) ( ) 信誉：102 2006-4-24 16:34:10 得分: 0
代码不复杂，
关键就在 位置 的合法性判断上，
也就是那几个变量的作用 .....
Top
sharpdew(风刃) ( ) 信誉：100 2006-4-24 16:36:49 得分: 0
呵呵，有点意思，回去看看
Top
IceCraft(心淡情浓) ( ) 信誉：100 2006-4-24 17:08:30 得分: 0
就只有这个完整的程序，没有任何算法说明，所以才请大家说说这个算法的原理的。
Top
hai1039(天下) ( ) 信誉：100 2006-4-24 17:21:53 得分: 0
不好意思, 这个程序是俺1996年写的, 贴在北京的某BBS上.
因为年代久远, 原算法已记不请. 只记得是根据采用数组的一种叠代方法,
改为位操作, 并做了相当的优化才变成现代的样子.
要进一步提高速度, 可以考虑N皇后问题的对称性, 有可能把速度提高3倍.
Top
zidane_yubo(天涯独尊) ( ) 信誉：100 2006-4-24 17:29:50 得分: 0
楼上的真牛
Top
Roaming_Sheep(Roaming Sheep) ( ) 信誉：100 2006-4-24 17:44:35 得分: 0
楼上的楼上真牛
Top
YFY(天易) ( ) 信誉：100 2006-4-24 17:50:43 得分: 0
楼上的楼上的楼上真牛
Top
IceCraft(心淡情浓) ( ) 信誉：100 2006-4-24 17:58:06 得分: 0
to hai1039(天下):
真是太幸运了，能这么快就能得到原作者您的回复！这个算法写得真是非常优秀，我已经看过很多皇后问题的算法，这一个真的可以称为是目前最快速效率最高的算法了。
我正是打算对您这个算法进行一些改动，采用对称性＋分布式计算来进一步提高运算速度。但是算法写得实在是太精简了，我虽然跟踪了变量的“位结构”变化情况，但是对其中的几个关键语句还是无法理解，烦请您给予我些许提示，不甚感激。加上注释和说明后，这段代码将很有可能成为皇后算法中的经典之作，使更多人能够从中领会算法的精妙之处。（老师也常说位运算的皇后解法是最快的，可是从来没有做过任何说明和提示）
Top
TERRYYRRET(命运) ( ) 信誉：100 2006-4-24 17:59:02 得分: 0
呵呵
Top
yuanchuang(元创) ( ) 信誉：86 2006-4-24 18:12:31 得分: 0
你代码短是用了递归。效率如何不清楚。因为还没有仔细看。
我也写过一个n皇后，用的是回溯法，我感觉效率应该还可以，但如果该成对位操作的话，应该性能有较大的提升，但在写的时候知识太匮乏了，所以用的是数组：
http://blog.csdn.net/yuanchuang/archive/2006/01/12/577598.aspx
等会儿，我有时间，我也改一下。
我用sdk写了一个俄罗斯方块，这个倒是全部用的是位操作：
http://blog.csdn.net/yuanchuang/archive/2006/04/01/646940.aspx
这是当时想加入饼子堂写的，因为当时对位操作有了一定概念，所以用的是位操作。
Top
yuanchuang(元创) ( ) 信誉：86 2006-4-24 18:27:16 得分: 0
刚才看了一下我自己的，该成对位操作还比较难，佩服楼主！
Top
yuanchuang(元创) ( ) 信誉：86 2006-4-24 18:32:03 得分: 0
hai1039(天下)：
拜师，行不？
我在江苏
Top
smokerain(烟雨朦朦) ( ) 信誉：98 2006-4-24 18:38:23 得分: 0
我晕，我在AMD1.67G的机器上用VS2003也用了137秒，怎么回事？
Top
province_(雍昊) ( ) 信誉：100 2006-4-24 19:33:59 得分: 0
学习ING
Top
yuanchuang(元创) ( ) 信誉：86 2006-4-24 20:50:34 得分: 0
yuanchuang(元创) ( ) 信誉：88 2006-04-24 18:32:00 得分: 0
hai1039(天下)：
拜师，行不？
我在江苏
-------------------------------
算了，还得靠自己
Top
r_s(星期四) ( ) 信誉：100 2006-4-25 8:16:14 得分: 0
学习
学习
再学习
Top
Kevin_jun() ( ) 信誉：100 2006-4-25 8:28:22 得分: 0
学习
@_@
Top
wangzk(wangzukui) ( ) 信誉：100 2006-4-25 9:34:22 得分: 0
看看
(以下签名由MyCSDN回复工具生成)
-----------------------------------------------
MyCSDN - CSDN离线数据浏览工具。
下载地址：http://nj.onlinedown.net/soft/6591.htm
Top
yuanchuang(元创) ( ) 信誉：86 2006-4-25 9:39:26 得分: 0
为什么在我电脑上不能运行呢？
Top
dreamXren(追梦人) ( ) 信誉：100 2006-4-25 11:42:05 得分: 0
long sum = 0, upperlim = 1; // sum用来记录排列总数，upperlim用来作bit mark。
// 有多少个皇后，就有多少bit被置1。（从低位到高位）
// 放置顺序是从右边列开始的。
void test(long row, long ld, long rd) // row记录了列的放置信息。bit为1时代表已经放置了皇后。
// ld记录了上一个皇后的左边1列不能放置皇后。
//rd记录了左边1列不能放置皇后。
// 如：上一次放的是第6列: 则
// row **** **** **1* ****
// ld **** **** *1** *****
// rd **** **** ***1 ****
{
if (row != upperlim)
{
long pos = upperlim & ~(row | ld | rd); // 将row，ld，rd同时为0的bit提出来。
while (pos) // if pos = 0，那么皇后没有地方放？？？
{
long p = pos & -pos; // 将pos除最低的为1的bit外，所有的位清零后赋值给p
// pos不改变。（取得可以放皇后的最右边的列）
pos -= p; // 将pos的最低的为1的bit清零。（次右边的列，为循环做准备）
test(row + p, (ld + p) << 1, (rd + p) >> 1); // row + p将当前列置1，表示放上了皇后
// (ld + p) << 1。设置左边列不能放。
}
} else // row的每一位为1，即所有皇后都放好了。
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)) // long为32位，呵呵，所以这里是<=32
{
printf(" 只能计算1-32之间\n");
exit(-1);
}
printf("%d 皇后\n", n);
upperlim = (upperlim << n) - 1; //有多少个皇后，就有多少bit被置1。（从低位到高位）
test(0, 0, 0);
printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}
关于位的操作，可以看看
http://blog.csdn.net/dreamXren/archive/2005/11/30/540245.aspx
Top
danjiewu(阿丹) ( ) 信誉：100 2006-4-25 11:59:11 得分: 0
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long sum = 0, upperlim = 1;
void test(long row, long ld, long rd) \\row表示已经有皇后的行，ld、rd分别表示已经有皇后的斜列，每一位表示该列中可以摆放皇后的位置，1表示可以摆放，0表示不可以摆放。row在每查找下一列时不用改动，ld、rd需要分别左移和右移一位。
{
if (row != upperlim) \\当所有行都有皇后时说明摆放完毕
{
long pos = upperlim & ~(row | ld | rd); \\pos的每一位表示该列中可以摆放皇后的位置，1表示可以摆放，0表示不可以摆放
while (pos) \\如果pos中还有可以摆放的位置
{
long p = pos & -pos; \\p为pos中最末一个可以摆放的位置
pos -= p; \\将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));
}
===========================
这个解释没有错吧？
Top
sk_fault(晨光一线) ( ) 信誉：100 2006-4-25 12:43:16 得分: 0
学习
Top
awl005(忽然) ( ) 信誉：100 2006-4-25 13:16:59 得分: 0
35秒?
我在CD2.8G的CPU上101秒:
16 皇后
共有14772512种排列,计算时间101秒
看来CD很烂,那个1.66G是什么CPU
Top
XPR(橡皮人) ( ) 信誉：100 2006-4-25 13:17:24 得分: 0
精彩,学习中!!
Top
sharpdew(风刃) ( ) 信誉：100 2006-4-25 14:34:11 得分: 0
LZ的代码容易看懂，但我觉得核心的是在针对试探－回溯算法所用的数据结构的设计上。
程序采用了递归，也就是借用了程序提供的自动回溯功能。
算法的核心：使用bit数组来代替以前由int或者bool数组来存储当前格子被占用或者说可用信息，从这可以看出N个皇后对应需要N位表示。
巧妙之处在于：以前我们需要在一个N*N正方形的网格中挪动皇后来进行试探回溯，每走一步都要观察和记录一个格子前后左右对角线上格子的信息；采用bit位进行信息存储的话，就可以只在一行格子也就是（1行×N列）个格子中进行试探回溯即可，对角线上的限制被化归为列上的限制。
程序中主要需要下面三个bit数组，每位对应网格的一列，在C中就是取一个整形数的某部分连续位即可。
row用来记录当前哪些列上的位置不可用，也就是哪些列被皇后占用，对应为1；
ld，rd同样也是记录当前哪些列位置不可用，但是不表示被皇后占用，而是表示会被已有皇后吃掉的位置。这三个位数组进行“与”操作后就是表示当前还有哪些位置可以放置新的皇后，对应0的位置可放新的皇后。如下图所示的8皇后问题求解得第一步：
row: [ ][ ][ ][ ][ ][ ][ ][*]
ld: [ ][ ][ ][ ][ ][ ][*][ ]
rd: [ ][ ][ ][ ][ ][ ][ ][ ]
------------------------------------
row|ld|rd: [ ][ ][ ][ ][ ][ ][*][*]
所有下一个位置的试探过程都是通过位操作来实现的，这是借用了C语言的好处，上面有位同学对其中得操作已经说得挺清楚了。
Top
sharpdew(风刃) ( ) 信誉：100 2006-4-25 14:39:03 得分: 0
如果借用N*N网格的对称信息，我觉得也可能有更高的效率提升！
Top
sharpdew(风刃) ( ) 信誉：100 2006-4-25 14:45:29 得分: 0
程序采用了递归，也就是借用了编译系统提供的自动回溯功能。
Top
bluebay(bluebay) ( ) 信誉：100 2006-4-25 15:39:20 得分: 0
Mark
Top
sharpdew(风刃) ( ) 信誉：100 2006-4-25 15:40:38 得分: 0
我完整地贴一下：
// N Queens Problem
// 试探-回溯算法，递归实现
// sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。
long sum = 0, upperlim = 1;
// 试探算法从最右边的列开始。
void test(long row, long ld, long rd) 。
{
if (row != upperlim)
{
// row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
// 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1。
// 也就是求取当前哪些列可以放置皇后。
long pos = upperlim & ~(row | ld | rd);
while (pos) // 0 -- 皇后没有地方可放，回溯。
{
// 拷贝pos最右边为1的bit，其余bit置0。
// 也就是取得可以放皇后的最右边的列。
long p = pos & -pos;
// 将pos最右边为1的bit清零。
// 也就是为获取下一次的最右可用列使用做准备，
// 程序将来会回溯到这个位置继续试探。
pos -= p;
// row + p，将当前列置1，表示记录这次皇后放置的列。
// (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
// (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
// 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
// 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
// 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
// 上产生的限制都被记录下来了。
test(row + p, (ld + p) << 1, (rd + p) >> 1);
}
}
else
{
// row的所有位都为1，即找到了一个成功的布局，回溯。
sum++;
}
}
int main(int argc, char *argv[])
{
time_t tm;
int n = 16;
if (argc != 1)
n = atoi(argv[1]);
tm = time(0);
// 因为整型数的限制，最大只能32位，
// 如果想处理N大于32的皇后问题，需要
// 用bitset数据结构进行存储。
if ((n < 1) || (n > 32))
{
printf(" 只能计算1-32之间\n");
exit(-1);
}
printf("%d 皇后\n", n);
// N个皇后只需N位存储，N列中某列有皇后则对应bit置1。
upperlim = (upperlim << n) - 1;
test(0, 0, 0);
printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}
上述代码容易看懂，但我觉得核心的是在针对试探－回溯算法所用的数据结构的设计上。
程序采用了递归，也就是借用了编译系统提供的自动回溯功能。
算法的核心：使用bit数组来代替以前由int或者bool数组来存储当前格子被占用或者说可用信息，从这
可以看出N个皇后对应需要N位表示。
巧妙之处在于：以前我们需要在一个N*N正方形的网格中挪动皇后来进行试探回溯，每走一步都要观察
和记录一个格子前后左右对角线上格子的信息；采用bit位进行信息存储的话，就可以只在一行格子也
就是（1行×N列）个格子中进行试探回溯即可，对角线上的限制被化归为列上的限制。
程序中主要需要下面三个bit数组，每位对应网格的一列，在C中就是取一个整形数的某部分连续位即可
。
row用来记录当前哪些列上的位置不可用，也就是哪些列被皇后占用，对应为1。
ld，rd同样也是记录当前哪些列位置不可用，但是不表示被皇后占用，而是表示会被已有皇后在对角线
上吃掉的位置。这三个位数组进行“或”操作后就是表示当前还有哪些位置可以放置新的皇后，对应0
的位置可放新的皇后。如下图所示的8皇后问题求解得第一步：
row: [ ][ ][ ][ ][ ][ ][ ][*]
ld: [ ][ ][ ][ ][ ][ ][*][ ]
rd: [ ][ ][ ][ ][ ][ ][ ][ ]
------------------------------------
row|ld|rd: [ ][ ][ ][ ][ ][ ][*][*]
所有下一个位置的试探过程都是通过位操作来实现的，这是借用了C语言的好处，详见代码注释。
Top
dylin(愚公担出来的泥巴) ( ) 信誉：100 2006-4-25 16:38:47 得分: 0
大开眼界了@_@
Top
hai1039(天下) ( ) 信誉：100 2006-4-25 17:39:48 得分: 0
谢谢sharpdew的注释, 这个算法和原来采用数组的算法没有本质上的区别, 都是同样的回溯方法, 只不过在具体实现上采用了位操作.
因为N皇后每高一级的计算量是前一级的7-9倍, 所以采用对称算法或者小规模的多CPU计算充其量也只能在单位时间内多算一到两级.
以下为已知的N-皇后解数目
n a(n)
11
20
30
42
510
64
740
892
9352
10724
112680
1214200
1373712
14365596
152279184
1614772512
1795815104
18666090624
194968057848
2039029188884
21314666222712
222691008701644
2324233937684440
24227514171973736
252207893435808352
Top
lx6636(水果萝卜) ( ) 信誉：97 2006-4-25 21:04:51 得分: 0
mark 好好学习
Top
jyk1970() ( ) 信誉：100 2006-4-25 21:21:51 得分: 0
好！
Top
diedknight(diedknight) ( ) 信誉：99 2006-4-25 21:28:07 得分: 0
看了注释算法是看懂了,
但 long p = pos & -pos;
为什么能得到pos的最右为1的bit?
希望能说明一下...
谢谢
Top
soft_biao(巴不豆) ( ) 信誉：100 2006-4-25 21:36:07 得分: 0
这算法让我打开眼界了，值得学习，呵呵
回 diedknight：
-pos为负数，在内存里是以补码形式存储的，补码＝原码（除符号位）取反＋１
２者相与刚好取得最后为１的bit，其他为０
Top
ykzhujiang(朱朱) ( ) 信誉：100 2006-4-25 21:43:06 得分: 0
先mark一下
Top
diedknight(diedknight) ( ) 信誉：99 2006-4-25 22:00:07 得分: 0
谢谢soft_biao(巴不豆)
:)
Top
ENOUGH_XU(足球小兵) ( ) 信誉：100 2006-4-25 22:41:18 得分: 0
学习
Top
qingyuan18(zealot_tang) ( ) 信誉：99 2006-4-25 23:02:00 得分: 0
写算法的真是高人辈出啊！
Top
joyself(独来读网) ( ) 信誉：97 2006-4-25 23:03:36 得分: 0
做个记号，回来看
Top
IceCraft(心淡情浓) ( ) 信誉：100 2006-4-27 14:59:46 得分: 0
感谢 dreamXren(追梦人)、danjiewu(阿丹)以及sharpdew(风刃)的解答。特别是sharpdew(风刃)同志还给出了算法的核心原理说明，以及每一步的详细注释，让我很快就理解了这个算法的原理，谢谢！
再次感谢三位的解答！
按照此算法思路，我重写出了一个Java版的皇后算法，不仅采用了位运算，也使用了对称原理减少了一半的计算时间。同时我采用Java的分布式计算能力，允许网络中多台计算机同时进行计算。最新的测试结果是在1台双核1.66G笔记本和1台机架服务器（2个3.0G超线程CPU）上同时运行得出的，近似于6个CPU同时运行，计算16皇后问题用了5秒，如果机器数目增多，时间也将随之减少，当然也要考虑每台机器的性能和网络状况。
等完成这次作业后再把程序共享给大家。
Top
jsbanwjly(我自痴狂) ( ) 信誉：100 2006-4-27 15:21:45 得分: 0
mark
Top
oosky2004(oosky) ( ) 信誉：95 2006-4-27 16:06:49 得分: 0
这个要作个记号。
太N了。
Top
esprit0318(遥远的。。。AZA~~AZA~~FIGHTING......) ( ) 信誉：100 2006-4-27 18:41:43 得分: 0
mark
Top
csj50(行风) ( ) 信誉：100 2006-4-27 18:45:37 得分: 0
mark
Top
daidongsheng(孤寂浪子) ( ) 信誉：99 2006-4-27 19:09:20 得分: 0
mark！！
Top
cattlenzq(查无此人) ( ) 信誉：100 2006-4-27 19:26:18 得分: 0
mark，
不过我2500+好象算不出来16皇后。。。。。。。。。。。。。
8个停快
就是16个几分钟都没有反映。。。
Top
wind19(南北) ( ) 信誉：100 2006-4-27 19:46:46 得分: 0
肯定不能用递归
Top
bombwang(王) ( ) 信誉：100 2006-4-27 20:15:09 得分: 0
先mark一下
Top
fengjunonline(可可豆) ( ) 信誉：100 2006-4-27 21:17:22 得分: 0
收藏
Top
li341151() ( ) 信誉：100 2006-4-27 21:27:27 得分: 0
向高人学习!
Top
gjianpro(#ifndef DEBUG) ( ) 信誉：100 2006-4-27 21:47:20 得分: 0
学习
Top
stonepeter(笨笨石头.NET_不想做公务员想做程序员了) ( ) 信誉：100 2006-4-27 22:32:00 得分: 0
100秒->17秒->5秒!!!!20倍啊！！！！
再次证明了同样的算法思想，由不同的人来实现效率的不一样啊不一样！！！
Top
niatclock(豆豆雅) ( ) 信誉：100 2006-4-27 22:49:03 得分: 0
很好
Top
aootb(阿拉丁) ( ) 信誉：100 2006-4-27 23:16:18 得分: 0
mark,study.
Top
justrun2005(机枪) ( ) 信誉：100 2006-4-27 23:51:33 得分: 0
收藏
Top
caiyuantian() ( ) 信誉：100 2006-4-28 0:11:40 得分: 0
国外早已出现了更快的算法，到google上搜索n queen就可看到一个Jeff Somers's N Queens Solutions的链接，用他的程序，我的电脑算１６皇后时少于１０秒就算出来了
Top
IceCraft(心淡情浓) ( ) 信誉：100 2006-4-28 0:36:27 得分: 0
多谢caiyuantian()的提示！经过测试，在我的机器上T2300双核1.66G（实际计算中只用到一个核心），用了21秒，计算速度确实已经优于本文围绕的位运算解法。
初步看了一下，它的判断原理和sharpdew(风刃)所描述的原理相似，也就是和本文算法的判断原理相似；并且它没有使用位运算来存储每行的3个判断结果，而是采用了int数组；最重要的是它没有使用递归，而是只用for循环。
我想最大的区别就是最后这一点了，值得深入学习！
Top
IceCraft(心淡情浓) ( ) 信誉：100 2006-4-28 0:56:41 得分: 0
更正一下，测试的时候忘了把CPU性能开到最大。1.66Ghz上应该是12秒。
顺便贴出Jeff Somers's N Queens Solutions的运行情况，作者是在800Mhz机器上运行得到的：
1 1 n/a
2 0 < 0 seconds
3 0 < 0 seconds
4 2 < 0 seconds
5 10 < 0 seconds
6 4 < 0 seconds
7 40 < 0 seconds
8 92 < 0 seconds
9 352 < 0 seconds
10 724 < 0 seconds
11 2680 < 0 seconds
12 14200 < 0 seconds
13 73712 < 0 seconds
14 365596 00:00:01
15 2279184 00:00:04
16 14772512 00:00:23
17 95815104 00:02:38
18 666090624 00:19:26
19 4968057848 02:31:24
20 39029188884 20:35:06
21 314666222712 174:53:45
22 2691008701644 ?
23 24233937684440 ?
24 ? ?
看来作者也只尝试到21皇后，22、23应该是一些科学研究组织早已公开的结果了。24、25在前边hai1039(天下) 的回复中已经公开了。兄弟们可以试着挑战下26以后的结果数了：）
Top
hai1039(天下) ( ) 信誉：100 2006-4-28 8:47:53 得分: 0
Jeff Somers's N Queens Solutions 的方法是采用了左右对称, 只算一半,所以在算法的复杂度上和上面的位操作算法是一样的.
关键还要在降低算法复杂度上有突破啊, 现在的复杂度是O(M^N) M在7-9之间, N为皇后个数.
Top
wangchine(北斗七星高) ( ) 信誉：100 2006-04-28 09:16:00 得分: 0
牛人。 记号
Top
smilefox(笑面狐) ( ) 信誉：100 2006-04-28 09:20:00 得分: 0
16 皇后
共有14772512种排列, 计算时间25秒
amd sempron 2800+
512M
Top
ivefire(火) ( ) 信誉：100 2006-04-28 09:39:00 得分: 0
mark一下
Top
dxrenderman() ( ) 信誉：100 2006-04-28 09:41:00 得分: 0
mark
Top
alexanda2000(书生活) ( ) 信誉：100 2006-04-28 10:38:00 得分: 0
收藏一下
Top
hiji(写代码的民工) ( ) 信誉：100 2006-04-28 10:42:00 得分: 0
16皇后
共有14772512种排列, 计算时间40秒
amd sempron 2400+
768M
Top
taizi1010(青菜) ( ) 信誉：100 2006-04-28 11:41:00 得分: 0
Mark
Top
hiji(写代码的民工) ( ) 信誉：100 2006-04-28 11:48:00 得分: 0
N Queens program by Jeff Somers.
allagash98@yahoo.com or jsomers@alumni.williams.edu
Start: Fri Apr 28 11:45:06 2006
End: Fri Apr 28 11:45:17 2006
Calculations took 11 seconds.
For board size 16, 14772512 solutions found.
這個強啊，16皇后只用了11秒
amd sempron 2400+
768M
Top
name99_6() ( ) 信誉：100 2006-04-28 12:38:00 得分: 0
mark
| -ICP -IDC -ISP |