最近重新复习了一下沙特人的算法书， 根据他的算法实现了8皇后问题，
自己用C做了一个实现。
12个皇后的问题在我的机器（AMD 3000＋， 256，LINUX 2.6）上运行了4.7秒左右，
后来在忘上又找了一个实现,这是
链接， 他的竟然只用0.04秒。SO 快。
佩服。
贴上代码：
我的：
#include <string.h>
#include <assert.h>
long nqueens(int);
int test_queens(const char *,const int , const int);
int main(void)
{
assert (nqueens(12) == 14200);
//assert (nqueens(13) == 73712);
}
long
nqueens(int n)
{
register int key = 0;
int scount = 0;
char retv[20];
int test_val;
memset(retv, 0, 20);
while( key >= 0) {
while( retv[key] <= n-1) { // n-1 means zero was a position
retv[key] = retv[key] + 1;
if ( (test_val = test_queens(retv,key, n)) == 1) //part answer
key++;
else if (test_val == 0)
{
scount++;
}
}
retv[key] = 0;
key--;
}
outter:
return(scount);
}
// if queens is illegel result return -1
// else if queens is legel return 0
// or part result return 1
int test_queens(const register char *v,const int key, const register int n)
{
for (int i = 0; i < n; i++) {
char vi = v[i], vk = v[key];
if (vi == 0 || vk == 0 )return 1;
if( i == key ) continue;
if (vi == vk || vk-vi == key - i || vk-vi == i - key)
return -1;
}
return 0;
}
>time ./my
real 0m0.556s
user 0m0.552s
sys 0m0.000s
那位兄台的
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef unsigned long ulong;
static const ulong ulong_bit = sizeof(ulong) * CHAR_BIT;static inline ulong search(ulong lb, ulong cb, ulong rb, ulong cnt) {
if (~0ul == cb)
cnt += 1;
else
for (ulong bs = lb | cb | rb; ~0ul != bs;) {
ulong b = ~bs & (bs+1);
bs |= b;
cnt = search((lb | b) << 1, cb | b, (rb | b) >> 1, cnt);
}
return cnt;
}static inline ulong nQs(ulong m) { return search(0, ~0ul >> m, 0, 0); }int main(int argc, char* argv[]) {
ulong a = argc < 2 ? ulong_bit : atol(argv[1]);
ulong n = a < ulong_bit ? a : ulong_bit; // n = min(a, ulong_bit)
printf("%li: %li total solutions\n", 12, nQs(12));
return 0;
}
>time ./internet
12: 14200 total solutions
real 0m0.081s
user 0m0.024s
sys 0m0.004s
