目前最快的N皇后问题算法！！！
最近老师布置了一道算法题目－－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));
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
问题点数：100、回复次数：134Top
1 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2006-04-24 14:33:13 得分 0
学习
Top
2 楼Rick_ang（东方未名）回复于 2006-04-24 15:07:47 得分 0
学习..这个需要慢慢看Top
3 楼universes（及时揭帖是一种美德 | CSDN也这么黑）回复于 2006-04-24 15:14:37 得分 0
mark
Top
4 楼languagec（各有所求）回复于 2006-04-24 15:53:37 得分 0
hahaTop
5 楼iamcaicainiao（老菜，长征）回复于 2006-04-24 16:03:28 得分 0
学习+收藏Top
6 楼jixingzhong（瞌睡虫·星辰）回复于 2006-04-24 16:03:37 得分 0
没有注释，没有算法，
看起来就麻烦了 ...
楼主把这个算法的链接给出来吧，
在有算法的基础上，
看程序快一些 ...
Top
7 楼jixingzhong（瞌睡虫·星辰）回复于 2006-04-24 16:34:10 得分 0
代码不复杂，
关键就在 位置 的合法性判断上，
也就是那几个变量的作用 .....Top
8 楼sharpdew（风刃）回复于 2006-04-24 16:36:48 得分 0
呵呵，有点意思，回去看看Top
9 楼IceCraft（心淡情浓）回复于 2006-04-24 17:08:29 得分 0
就只有这个完整的程序，没有任何算法说明，所以才请大家说说这个算法的原理的。Top
10 楼hai1039（天下）回复于 2006-04-24 17:21:53 得分 0
不好意思, 这个程序是俺1996年写的, 贴在北京的某BBS上.
因为年代久远, 原算法已记不请. 只记得是根据采用数组的一种叠代方法,
改为位操作, 并做了相当的优化才变成现代的样子.
要进一步提高速度, 可以考虑N皇后问题的对称性, 有可能把速度提高3倍.Top
11 楼zidane_yubo（天涯独尊）回复于 2006-04-24 17:29:49 得分 0
楼上的真牛Top
12 楼Roaming_Sheep（Roaming Sheep）回复于 2006-04-24 17:44:34 得分 0
楼上的楼上真牛Top
13 楼YFY（天易）回复于 2006-04-24 17:50:42 得分 0
楼上的楼上的楼上真牛Top
14 楼IceCraft（心淡情浓）回复于 2006-04-24 17:58:05 得分 0
to hai1039(天下):
真是太幸运了，能这么快就能得到原作者您的回复！这个算法写得真是非常优秀，我已经看过很多皇后问题的算法，这一个真的可以称为是目前最快速效率最高的算法了。
我正是打算对您这个算法进行一些改动，采用对称性＋分布式计算来进一步提高运算速度。但是算法写得实在是太精简了，我虽然跟踪了变量的“位结构”变化情况，但是对其中的几个关键语句还是无法理解，烦请您给予我些许提示，不甚感激。加上注释和说明后，这段代码将很有可能成为皇后算法中的经典之作，使更多人能够从中领会算法的精妙之处。（老师也常说位运算的皇后解法是最快的，可是从来没有做过任何说明和提示）Top
15 楼TERRYYRRET（命运）回复于 2006-04-24 17:59:01 得分 0
呵呵Top
16 楼yuanchuang（元创）回复于 2006-04-24 18:12:30 得分 5
你代码短是用了递归。效率如何不清楚。因为还没有仔细看。
我也写过一个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
17 楼yuanchuang（元创）回复于 2006-04-24 18:27:16 得分 0
刚才看了一下我自己的，该成对位操作还比较难，佩服楼主！Top
18 楼yuanchuang（元创）回复于 2006-04-24 18:32:02 得分 0
hai1039(天下)：
拜师，行不？
我在江苏Top
19 楼smokerain（烟雨朦朦）回复于 2006-04-24 18:38:23 得分 0
我晕，我在AMD1.67G的机器上用VS2003也用了137秒，怎么回事？Top
20 楼province_（雍昊）回复于 2006-04-24 19:33:59 得分 0
学习INGTop
21 楼yuanchuang（元创）回复于 2006-04-24 20:50:34 得分 0
yuanchuang(元创) ( ) 信誉：88 2006-04-24 18:32:00 得分: 0
hai1039(天下)：
拜师，行不？
我在江苏
-------------------------------
算了，还得靠自己Top
22 楼r_s（星期四）回复于 2006-04-25 08:16:13 得分 0
学习
学习
再学习Top
23 楼Kevin_jun（）回复于 2006-04-25 08:28:22 得分 0
学习
@_@Top
24 楼wangzk（wangzukui）回复于 2006-04-25 09:34:22 得分 0
看看
(以下签名由MyCSDN回复工具生成)
-----------------------------------------------
MyCSDN - CSDN离线数据浏览工具。
下载地址：http://nj.onlinedown.net/soft/6591.htmTop
25 楼yuanchuang（元创）回复于 2006-04-25 09:39:26 得分 0
为什么在我电脑上不能运行呢？Top
26 楼dreamXren（追梦人）回复于 2006-04-25 11:42:04 得分 10
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.aspxTop
27 楼danjiewu（阿丹）回复于 2006-04-25 11:59:11 得分 10
#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
28 楼sk_fault（晨光一线）回复于 2006-04-25 12:43:15 得分 0
学习Top
29 楼awl005（忽然）回复于 2006-04-25 13:16:59 得分 0
35秒?
我在CD2.8G的CPU上101秒:
16 皇后
共有14772512种排列,计算时间101秒
看来CD很烂,那个1.66G是什么CPU
Top
30 楼XPR（橡皮人）回复于 2006-04-25 13:17:24 得分 0
精彩,学习中!!Top
31 楼sharpdew（风刃）回复于 2006-04-25 14:34:11 得分 10
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
32 楼sharpdew（风刃）回复于 2006-04-25 14:39:02 得分 0
如果借用N*N网格的对称信息，我觉得也可能有更高的效率提升！Top
33 楼sharpdew（风刃）回复于 2006-04-25 14:45:28 得分 0
程序采用了递归，也就是借用了编译系统提供的自动回溯功能。Top
34 楼bluebay（bluebay）回复于 2006-04-25 15:39:20 得分 0
MarkTop
35 楼sharpdew（风刃）回复于 2006-04-25 15:40:37 得分 40
我完整地贴一下：
// 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
36 楼dylin（家住红灯区,市府前）回复于 2006-04-25 16:38:47 得分 0
大开眼界了@_@Top
37 楼hai1039（天下）回复于 2006-04-25 17:39:48 得分 5
谢谢sharpdew的注释, 这个算法和原来采用数组的算法没有本质上的区别, 都是同样的回溯方法, 只不过在具体实现上采用了位操作.
因为N皇后每高一级的计算量是前一级的7-9倍, 所以采用对称算法或者小规模的多CPU计算充其量也只能在单位时间内多算一到两级.
以下为已知的N-皇后解数目
n a(n)
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352
Top
38 楼lx6636（水果萝卜）回复于 2006-04-25 21:04:50 得分 0
mark 好好学习Top
39 楼jyk1970（）回复于 2006-04-25 21:21:51 得分 0
好！Top
40 楼diedknight（diedknight）回复于 2006-04-25 21:28:06 得分 0
看了注释算法是看懂了,
但 long p = pos & -pos;
为什么能得到pos的最右为1的bit?
希望能说明一下...
谢谢Top
41 楼soft_biao（巴不豆）回复于 2006-04-25 21:36:06 得分 0
这算法让我打开眼界了，值得学习，呵呵
回 diedknight：
-pos为负数，在内存里是以补码形式存储的，补码＝原码（除符号位）取反＋１
２者相与刚好取得最后为１的bit，其他为０Top
42 楼ykzhujiang（朱朱）回复于 2006-04-25 21:43:05 得分 0
先mark一下Top
43 楼diedknight（diedknight）回复于 2006-04-25 22:00:07 得分 0
谢谢soft_biao(巴不豆)
:)Top
44 楼ENOUGH_XU（苦点,累点->没关系）回复于 2006-04-25 22:41:18 得分 0
学习
Top
45 楼qingyuan18（zealot_tang）回复于 2006-04-25 23:01:59 得分 0
写算法的真是高人辈出啊！Top
46 楼joyself（独来读网）回复于 2006-04-25 23:03:36 得分 0
做个记号，回来看Top
47 楼IceCraft（心淡情浓）回复于 2006-04-27 14:59:45 得分 0
感谢 dreamXren(追梦人)、danjiewu(阿丹)以及sharpdew(风刃)的解答。特别是sharpdew(风刃)同志还给出了算法的核心原理说明，以及每一步的详细注释，让我很快就理解了这个算法的原理，谢谢！
再次感谢三位的解答！
按照此算法思路，我重写出了一个Java版的皇后算法，不仅采用了位运算，也使用了对称原理减少了一半的计算时间。同时我采用Java的分布式计算能力，允许网络中多台计算机同时进行计算。最新的测试结果是在1台双核1.66G笔记本和1台机架服务器（2个3.0G超线程CPU）上同时运行得出的，近似于6个CPU同时运行，计算16皇后问题用了5秒，如果机器数目增多，时间也将随之减少，当然也要考虑每台机器的性能和网络状况。
等完成这次作业后再把程序共享给大家。Top
48 楼jsbanwjly（我自痴狂）回复于 2006-04-27 15:21:45 得分 0
markTop
49 楼oosky2004（我要好东西）回复于 2006-04-27 16:06:49 得分 0
这个要作个记号。
太N了。
Top
50 楼esprit0318（遥远的。。。AZA~~AZA~~FIGHTING......）回复于 2006-04-27 18:41:42 得分 0
markTop
51 楼csj50（行风）回复于 2006-04-27 18:45:37 得分 0
markTop
52 楼daidongsheng（Baggio⑩）回复于 2006-04-27 19:09:19 得分 0
mark！！Top
53 楼cattlenzq（吃狼的豆腐（不要给分了，散起来真麻烦！））回复于 2006-04-27 19:26:18 得分 0
mark，
不过我2500+好象算不出来16皇后。。。。。。。。。。。。。
8个停快
就是16个几分钟都没有反映。。。Top
54 楼wind19（南北）回复于 2006-04-27 19:46:46 得分 0
肯定不能用递归Top
55 楼bombwang（王）回复于 2006-04-27 20:15:09 得分 0
先mark一下Top
56 楼fengjunonline（奔跑的豆子）回复于 2006-04-27 21:17:22 得分 0
收藏Top
57 楼li341151（）回复于 2006-04-27 21:27:26 得分 0
向高人学习!Top
58 楼gjianpro（#ifndef _DEBUG）回复于 2006-04-27 21:47:20 得分 0
学习Top
59 楼stonepeter（笨笨石头.NET_从公务员转身成为了程序员）回复于 2006-04-27 22:32:00 得分 0
100秒->17秒->5秒!!!!20倍啊！！！！
再次证明了同样的算法思想，由不同的人来实现效率的不一样啊不一样！！！Top
60 楼niatclock（豆豆雅）回复于 2006-04-27 22:49:02 得分 0
很好Top
61 楼aootb（阿拉丁）回复于 2006-04-27 23:16:17 得分 0
mark,study.Top
62 楼justrun2005（机枪）回复于 2006-04-27 23:51:32 得分 0
收藏Top
63 楼caiyuantian（）回复于 2006-04-28 00:11:39 得分 0
国外早已出现了更快的算法，到google上搜索n queen就可看到一个Jeff Somers's N Queens Solutions的链接，用他的程序，我的电脑算１６皇后时少于１０秒就算出来了Top
64 楼IceCraft（心淡情浓）回复于 2006-04-28 00:36:26 得分 0
多谢caiyuantian()的提示！经过测试，在我的机器上T2300双核1.66G（实际计算中只用到一个核心），用了21秒，计算速度确实已经优于本文围绕的位运算解法。
初步看了一下，它的判断原理和sharpdew(风刃)所描述的原理相似，也就是和本文算法的判断原理相似；并且它没有使用位运算来存储每行的3个判断结果，而是采用了int数组；最重要的是它没有使用递归，而是只用for循环。
我想最大的区别就是最后这一点了，值得深入学习！Top
65 楼IceCraft（心淡情浓）回复于 2006-04-28 00:56:40 得分 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
66 楼hai1039（天下）回复于 2006-04-28 08:47:52 得分 0
Jeff Somers's N Queens Solutions 的方法是采用了左右对称, 只算一半,所以在算法的复杂度上和上面的位操作算法是一样的.
关键还要在降低算法复杂度上有突破啊, 现在的复杂度是O(M^N) M在7-9之间, N为皇后个数.Top
67 楼wangchine（争当猩猩）回复于 2006-04-28 09:16:17 得分 0
牛人。 记号Top
68 楼smilefox（笑面狐）回复于 2006-04-28 09:20:27 得分 0
16 皇后
共有14772512种排列, 计算时间25秒
amd sempron 2800+
512MTop
69 楼ivefire（）回复于 2006-04-28 09:39:13 得分 0
mark一下Top
70 楼dxrenderman（）回复于 2006-04-28 09:41:43 得分 0
markTop
71 楼alexanda2000（书生活）回复于 2006-04-28 10:38:46 得分 0
收藏一下Top
72 楼hiji（写代码的民工）回复于 2006-04-28 10:42:08 得分 0
16皇后
共有14772512种排列, 计算时间40秒
amd sempron 2400+
768MTop
73 楼taizi1010（青菜）回复于 2006-04-28 11:41:02 得分 0
MarkTop
74 楼hiji（写代码的民工）回复于 2006-04-28 11:48:04 得分 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+
768MTop
75 楼name99_6（Bruce）回复于 2006-04-28 12:38:51 得分 0
markTop
76 楼tjuzhangrui（）回复于 2006-04-28 14:52:32 得分 0
太巧妙了，只用了3个long型的数据记录行和两个对角线的限制就把问题解决了。Top
77 楼tjuzhangrui（）回复于 2006-04-28 15:15:15 得分 0
你的用的都是什么型号的CPU?我双核P4 3.0+1G内存算16皇后还要66秒Top
78 楼panzi667（迅雷免费电影下载社区http://www.woyaola.net）回复于 2006-04-28 15:43:30 得分 0
好贴Top
79 楼tongshushan（雨点轻轻洒过）回复于 2006-04-28 18:18:52 得分 0
markTop
80 楼epico（飘零燕）回复于 2006-04-28 19:17:14 得分 5
我把它的变量的意义说明一下，剩下的可以自己分析。
在程序每次运行中，列增加一个，所以，不用计算。
row,代表行。ld，rd，代表对角线的数值。对角线一共有两个方向，所以用两个变量。ld,rd的值表示该对角线在该行所占的格是。
在他的程序中，以上三个变量，比如row在第二个格,则用0000000010表示。1在第几位就表示后在第一个行或对角线。
upperlim的作用是限制row数，比如，一共五行，就用0000011111限定位数。
pos做运算后，结果是在行列中可以置位的数。
p是取出最右端可以置位的row。pos减去p后，可以取出下一个可以置位的row.
test(row + p, (ld + p) << 1, (rd + p) >> 1);
此句是关键将对存在皇后的行，对角线置位。在下一行，将对角线对应的位置位。由于，分别是左右对角线，所占据的格要错一位。
Top
81 楼epico（飘零燕）回复于 2006-04-28 19:19:14 得分 0
有一点说错了，
在他的程序中，以上三个变量，比如row在第二个格,则用0000000010表示。1在第几位就表示后在第一个行或对角线。
row,ld,rd分别代表以前所放置的后所占据的位置。代表多个后的位置，而不是一个后。
Top
82 楼eion（那个谁）回复于 2006-04-28 19:21:59 得分 5
#define QUEENS 13
// 皇后所在位置，site[i]表示第i行皇后所在位置
int site[QUEENS];
// 判断攻击条件
int collision(int i, int k)
{
if (site[i] == site[k] ||
abs(site[i]-site[k]) == abs(i-k))
return 1;
return 0;
}
// 找到一个就停止
void eight_queue()
{
int i = 0;
int j = 0;
int k;
site[0] = 0;
while (i < QUEENS && i>=0)
{
site[i] = j++;
if (j > QUEENS)
{
i --;
j = site[i]+1;
continue;
}
for (k=0; k<i && !collision(i, k); k++);
if (k == i)
{
i++; j=0;
}
}
}
// 打印所有的解
void all_eight_queue()
{
int i = 0;
int j = 0;
int k;
int n = 0;
site[0] = 0;
while (i>=0 && site[0] < QUEENS) // 退出条件
{
if (i == QUEENS) // 找到一个解，输出
{
printf("%4d: ", n++);
for (k=0; k<i; k++) printf("%d ", site[k]); printf("\n");
}
site[i] = j++; // 尝试下一个点
if (j > QUEENS) // 摆出了棋盘，则退回到上一个行
{
i --;
j = site[i]+1;
continue;
}
for (k=0; k<i && !collision(i, k); k++); // 攻击检测
if (k == i) // 无攻击，则继续摆下一行
{
i++; j=0;
}
}
}
void all_eight_queue_no_print()
{
int i = 0;
int j = 0;
int k;
int n = 0;
site[0] = 0;
while (i>=0 && site[0] < QUEENS) // 退出条件
{
if (i == QUEENS) // 找到一个解，输出
{
//printf("%4d: ", n++);
//for (k=0; k<i; k++) printf("%d ", site[k]); printf("\n");
}
site[i] = j++; // 尝试下一个点
if (j > QUEENS) // 摆出了棋盘，则退回到上一个行
{
i --;
j = site[i]+1;
continue;
}
for (k=0; k<i && !collision(i, k); k++); // 攻击检测
if (k == i) // 无攻击，则继续摆下一行
{
i++; j=0;
}
}
}
void test_8queen()
{
//all_eight_queue();
eight_queue();
for (int i=0; i<QUEENS; i++)
{
printf("%d ", site[i]);
}
printf("\n");
time_t t1 = time(0);
all_eight_queue_no_print();
time_t t2 = time(0);
printf("total time: %d\n", t2 - t1);
}
结果：
0 2 4 1 8 11 9 12 3 5 7 10 6
total time: 19
N＝26时的一个解：
0 2 4 1 3 8 10 12 14 20 22 24 19 21 23 25 9 6 15 11 7 5 17 13 18 16
Top
83 楼epico（飘零燕）回复于 2006-04-28 19:26:33 得分 0
不好意思，没看晚回帖，就回了。不好意思。Top
84 楼cqzj119（小蛇）回复于 2006-04-28 20:49:01 得分 0
惭愧，我的程序在P2.4上求16皇后用了789秒，太丢脸了，请高手指教。
程序如下：
/* -----------------------------------------------------------------------------
* NQueen.cpp: N 皇后
* 2006.4.28
* -----------------------------------------------------------------------------
*/
#include <iostream>
#include <windows.h>
using namespace std;
bool IsSafe(int *q, int step, int pos)
{
for (int i = 0; i < step; ++i) {
if (q[i] == pos) return false;
if (i - q[i] == step - pos) return false;
if (i + q[i] == step + pos) return false;
}
return true;
}
int NextStep(int *q, int step, int N)
{
for (int i = q[step] + 1; i < N; ++i) {
if (IsSafe(q, step, i) ) return i;
}
return -1;
}
long NQueen(int N)
{
int *q = new int[N];
for (int i = 0; i < N; ++i) {
q[i] = -1;
}
int step = 0;
long cnt = 0;
while (0 <= step) {
if (-1 == (q[step] = NextStep(q, step, N) ) ) {
--step;
} else {
++step;
}
if (N == step) {
--step;
++cnt;
}
}
delete q;
return cnt;
}
int main(int argc, char *argv[])
{
int N = 4;
switch (argc) {
case 1:
break;
case 2:
N = atoi(argv[1]);
break;
default:
cout << "usage: " << argv[0] << " [num]" << endl;
return -1;
}
if (4 > N) {
cout << "num must be more than or equal 4" << endl;
return -1;
}
DWORD dwBegin = ::GetTickCount();
long lCnt = NQueen(N);
DWORD dwEnd = ::GetTickCount();
cout << "共有 " << lCnt << " 种解!, 耗时:["
<< (float)(dwEnd - dwBegin) / 1000 << "]秒" << endl;
return 0;
}Top
85 楼wyl0502（）回复于 2006-04-28 21:33:03 得分 0
以前在usaco上做过。。也是利用了对称性，用3个数组来记录列、主对角线和次对角线的方式，回嗍。。也可以在1s内求出13皇后的。。。后面的没试了。。呵呵。。而且估计要是用gcc -O3选项优化一下效果可能还更好一些。。。
不过要是只想得到一个解的话，还是用遗传算法，约束满足问题。。。等启发式算法Top
86 楼jcdreamjc（枫）回复于 2006-04-28 22:45:29 得分 0
mark + studyTop
87 楼xiaolipeng（）回复于 2006-04-28 23:04:44 得分 0
我顶，学习学习啊！Top
88 楼burnett（）回复于 2006-04-28 23:17:15 得分 0
mark 慢慢研究～～Top
89 楼helnet（十字背负者）回复于 2006-04-29 00:16:29 得分 0
确实很强，收藏起来慢慢看Top
90 楼tatbaby（岛主）回复于 2006-04-29 00:27:18 得分 0
markTop
91 楼gengjindong（﹎王子﹎℡）回复于 2006-04-29 00:39:16 得分 0
[code]#include<math.h>
#include<stdio.h>
int a[8];
/*判断能是否在一直线上*/
int j(int n){
int i;
for(i=0;i<n;i++){
if(a[i]==a[n]||(n-i)==abs(a[n]-a[i])) return 0;
}
return 1;
}
/*输出*/
void print(){
int i;
for(i=0;i<8;i++)
printf("(%d,%d)-",i,a[i]);
printf("\n");
}
/*递归*/
int queens(int n){
int i;
for(i=0;i<8;i++)
{a[n]=i;
if(j(n)){
if(n==7) print();
else queens(n+1);
}
}
}
main()
{
queens(0);
getch();
} [/code]
i是行
a[n]是列
结果是输出所有的排序。
这是一个简单的N皇后问题算法Top
92 楼huntaway（huntaway）回复于 2006-04-29 01:15:35 得分 0
拜托，不要把盲目搜索当成最快的N皇后算法。用局部搜索+随机行走可以在短时间内解决百万皇后级别问题。Top
93 楼shines（郭子）回复于 2006-04-29 03:19:33 得分 0
MK~~Top
94 楼IceCraft（心淡情浓）回复于 2006-04-29 08:40:50 得分 0
还要劳请huntaway(huntaway)同志能够稍微说明一下“局部搜索+随机行走”用在queen问题中的原理，让大家更深入的学习一下：）
不过我不认为本文所讨论的算法是盲目的，也请你解释一下了Top
95 楼caiyuantian（）回复于 2006-04-29 08:43:11 得分 0
to huntaway(huntaway)用局部搜索+随机行走只能得到１个随机解吧，并不能得到所有解。Top
96 楼psusong（栀子花开）回复于 2006-04-29 09:17:20 得分 0
look lookTop
97 楼coastcdl（H）回复于 2006-04-29 10:01:44 得分 0
markTop
98 楼boxer_tony（）回复于 2006-04-29 10:35:54 得分 0
markTop
99 楼Makaveli（鸡蛋羹）回复于 2006-04-29 10:38:45 得分 0
mark 学习ingTop
100 楼jplayer（ssssssss）回复于 2006-04-29 11:25:06 得分 0
markTop
101 楼hertcloud（·￡孙子兵法￡·）回复于 2006-04-29 16:57:57 得分 0
不错 我P4 1.5 512内存
win2003下 vs2003 release编译 40秒。。Top
102 楼duduhaha（三人行必有我师）回复于 2006-04-29 17:50:23 得分 0
好贴留名!Top
103 楼gengjindong（﹎王子﹎℡）回复于 2006-04-29 18:16:32 得分 0
huntaway(huntaway)不错，我同意他怕说法。
不好意思我有点盲目了。
嗯。。。
huntaway(huntaway)
我希望我们能长期合作下去。
http://blog.csdn.net/gengjindong
是我的blog。把你的也留下吧。
我们可以互动学习，交流。Top
104 楼eagleking0000（）回复于 2006-04-29 19:02:33 得分 0
我咋就运行不了呢?Top
105 楼gengjindong（﹎王子﹎℡）回复于 2006-04-30 05:13:31 得分 0
能不能运行得了。只用心就可以了。
没有心的程序是永远都运行不了的。
你知道吗？
有的时候程序不听你的。
顺其自然吧。
一个算法的成功与失败。不是在于复杂。
而是在于一个长长的程序如何去简化。
程序和人的性格是一样的。
他是人类性格的结晶。
我想在这里的所以人都比我大。
我才19岁。
你们能不能一气所成，就在自己了。
送大家四个字：进取，创新。
Top
106 楼Jiana（Robin.English）回复于 2006-04-30 11:31:40 得分 0
恩，看看Top
107 楼geniuscaobo（也许会有一天）回复于 2006-04-30 15:57:07 得分 0
贴子标记Top
108 楼elvai_wind（）回复于 2006-05-05 09:39:17 得分 10
/* N Queens Problem */
/* 试探-回溯算法，递归实现 */
/* sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。 */
#include <time.h>
long sum = 0, upperlim = 1,half=0;
/* 试探算法从最右边的列开始。 */
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网格中某个已放置的皇后针对其对角线 */
/* 上产生的限制都被记录下来了。 */
if(row==0&&p>half)
continue;
else
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);
/* 采用对称式算法计算，增加全局变量half */
half=(n-1)/2;
half=upperlim<<half;
/* N个皇后只需N位存储，N列中某列有皇后则对应bit置1。 */
upperlim = (upperlim << n) - 1;
test(0, 0, 0);
printf("all %ld counts, ji suan time %d miao \n", sum*2, (int) (time(0) - tm));
getch();
}
本人把上例稍微修改后（采用了对称式算法，速度可以提高一半），不信大家试试！
Jeff Somers's N Queens Solutions 采用的也是对称式的方式~
至于复杂度的降低，还需要好好考虑！Top
109 楼Leomaxking（害怕孤独，但已习惯孤独）回复于 2006-05-05 14:32:51 得分 0
先标记下Top
110 楼caiyujie87（从头开始（小蔡））回复于 2006-05-06 12:34:46 得分 0
学习Top
111 楼hybest（）回复于 2006-05-09 15:58:14 得分 0
你们都好厉害哦，怎么才能学好数据结构？目前我只能写很短的算法，一看到长算法就害怕！！！Top
112 楼ra_zy（）回复于 2006-05-09 16:57:44 得分 0
markTop
113 楼wucanbi（）回复于 2006-05-09 18:29:14 得分 0
受益非浅Top
114 楼breakind（冰舞,把练街舞的精神拿来编程,必有所成.）回复于 2006-05-24 12:36:36 得分 0
16 皇后 C3 1.0GHZ 256M 用了188秒
真是的快啊!Top
115 楼sonald（第六指）回复于 2006-05-26 22:45:02 得分 0
牛人；学习中，下来好好看Top
116 楼snailbreak（悄悄的来，正如我悄悄的走）回复于 2006-05-26 23:30:24 得分 0
JFTop
117 楼gengjindong（﹎王子﹎℡）回复于 2006-05-27 06:42:39 得分 0
C语言并不难。
只不过是有点烦。
如何能学好数据结构那就要看自己的自学能力了。
一个天才都不敢说出一个好的学习方案。
所以万事得靠自己。
网上有好多有关C语方的视频。我希望自己能在自学预习的情况下多看一些学习教程。
Top
118 楼shellyyee（☆☆☆☆☆-----疏狂一醉,生活大师）回复于 2006-05-27 08:36:14 得分 0
长见识了....只是留名学习...Top
119 楼Cybergate（）回复于 2006-05-27 09:29:47 得分 0
太优美了，我当时也写了个位运算的，但远远没这么精炼啊。Top
120 楼daseny（胡杨）回复于 2006-05-27 11:09:08 得分 0
mark
一到周末心就飞了，等等再看吧。
呵呵，也许是昨天被几个线程折磨惨了……Top
121 楼transcendself（全全）回复于 2006-06-06 15:30:00 得分 0
goodTop
122 楼SamuelKevin（曼陀罗）回复于 2006-06-11 13:17:47 得分 0
shoucangTop
123 楼mgdcs（蓝色雪狐）回复于 2006-06-11 13:38:09 得分 0
输入20的话，时间很长啊Top
124 楼sunbird69（太阳鸟）回复于 2006-06-11 13:53:40 得分 0
mark
Top
125 楼heihei2004（嘿嘿）回复于 2006-06-11 14:33:17 得分 0
强，markTop
126 楼Free_Wind22（还没想好...）回复于 2006-06-11 16:37:08 得分 0
学习...Top
127 楼POPO_POPO（○泡泡○）回复于 2006-06-11 18:24:51 得分 0
随时关注此帖Top
128 楼tanlerstar（★天狼星★）回复于 2006-06-13 10:01:10 得分 0
哎!你们太狠了!!
学习学习!Top
129 楼wupei（工大四老之一）回复于 2006-06-19 15:48:37 得分 0
upup
Top
130 楼templarzq（原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒）回复于 2006-06-19 16:04:05 得分 0
mark
Top
131 楼ayw215（松花鼠）回复于 2006-06-19 18:47:06 得分 0
强人好多啊Top
132 楼xmhl（oye）回复于 2006-06-20 09:33:10 得分 0
markTop
133 楼gezichong（鸽子虫）回复于 2006-08-28 15:58:13 得分 0
顶Top
134 楼nankezhishi（南柯之石）回复于 2006-10-09 08:47:24 得分 0
回溯永远是最慢的.
启发式算法,如遗传算法\局部搜索．
１０００后问题 数秒解决．
当然，在下不会．Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
