Robert Anderson's Blog

轉貼我自己 2008.6.27的文章

這次又更快了，這是從大陸那邊找來的，後來終於想通他們的原理了
他們用的是位元運算，非常快，而我將他們程式碼改了些，因為他們行跟列與我們相反
而且他們所謂的對稱性，似乎無法紀錄解答，這支程式原本也只能算出有幾組解答，目前這支基本程式是紀錄目前解答狀況，若需要記錄解答則另外建立陣列，否則刪除那段就行了
利用這些程式碼，個人成功解答了Another N Queen
#include <cstdlib>
#include <cstdio>
#define MAX 16

long sum = 0, upperlim = 1;    
long now[MAX];

int test(long, long, long, int);

int main(int argc, char *argv[])
{
   int n = 16;

   scanf("%d", &n);

   upperlim = (upperlim << n) - 1;        

   test(0, 0, 0, 0);
   printf("CASE %d: %ld combinations.\n", n, sum);
  
   system("PAUSE");
   return 0;
}

int test(long col, long ld, long rd, int row)
{
   if (col != upperlim)
   {
     long pos = upperlim & ~(col | ld | rd);
     while (pos)
     {
        long p = pos & -pos;                                             

        pos -= p;                          
       
        now[row]=p;
       
        test(col + p, (ld + p) << 1, (rd + p) >> 1, row+1);                             
       }
   }
   else  
   {
  
       sum++;
   }
}