USACO 1.5.4 Checker Challenge （N皇后問題） 位運算解法
本文正體字版由OpenCC轉換
經典的N皇后（8皇后擴展）問題，學過算法的都知道。
這道題要用回溯法，搜索+優化，但一般的方法很難解決N>=13以上的問題。所以這裏重點介紹位操作法。
什麼是位運算？ 程 序 中的所有數在計算機內存中都是以二進制的形式儲存的。位運算說穿了，就是直接對整數在內存中的二進制位進行操作。比如，and運算本來是一個邏輯運 算 符，但整數與整數之間也可以進行and運算。舉個例子，6的二進制是110，11的二進制是1011，那麼6 and 11的結果就是2，它是二進制 對應位進行邏輯運算的結果（0表示False，1表示True，空位都當0處理）： 110 AND 1011
0010 –> 2 由於位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。
我的解法基本思想還是用回溯法，和普通算法一樣，這是一個遞歸過程，程序一行一行地尋找可以放皇后的地方。過程帶三個參數，row、ld和rd，分別表示在 縱列和兩個對角線方向的限制條件下這一行的哪些地方不能放。我們以6x6的棋盤爲例，看看程序是怎麼工作的。假設現在已經遞歸到第四層，前三層放的子已經 標在左圖上了。紅色、藍色和綠色的線分別表示三個方向上有衝突的位置，位於該行上的衝突位置就用row、ld和rd中的1來表示。
upperlim=(1 << n)-1意爲算出該棋盤的目標狀態（全部被佔滿）。
pos=upperlim & ~(row | ld | rd)
把它們三個並起來，得到該行所有的禁位，取反後就得到所有可以放的位置（用pos來表示）。
p=pos & -pos;
-a相當於~a + 1，這裏的代碼就相當於pos & (~pos+1)，其結果是取出最右邊的那個1。
這樣，p就表示該行的某個可以放子的位置，把它從pos中移除並遞歸調用test過程。
注意遞歸調用時三個參數的變化，每個參數都加上了一個禁位，但兩個對角線方向的禁位對下一行的影響需要平移一位。
最後，如果遞歸到某個時候發現row=upperlim (目標狀態111111) 了，說明六個皇后全放進去了，此時程序找到的解的個數加1。
代碼如下：
/*
ID: cmykrgb1
PROG: checker
LANG: C++
*/
#include <stdio.h>
FILE *fi,*fo;
unsigned long int upperlim,sum;
int a[14],n;
int ps(int a) //不用 log 節省時間
{
switch (a)
{
case 1:
return 1;
case 2:
return 2;
case 4:
return 3;
case 8:
return 4;
case 16:
return 5;
case 32:
return 6;
case 64:
return 7;
case 128:
return 8;
case 256:
return 9;
case 512:
return 10;
case 1024:
return 11;
case 2048:
return 12;
case 4096:
return 13;
}
}
void test(unsigned long int row,unsigned long int ld,unsigned long int rd,int deep)
{
unsigned long int pos,p;
if (row!=upperlim)
{
pos=upperlim & ~(row | ld | rd);
while (pos!=0)
{
p=pos & -pos;
pos=pos-p;
if (sum<3) a[deep]=p;
test(row+p,(ld+p)<< 1,(rd+p)>> 1,deep+1);
}
}
else
{
sum++;
int i;
if (sum<=3)
{
for (i=1;i<=n-1;i++)
fprintf(fo,"%d ",ps(a[i]));
fprintf(fo,"%dn",ps(a[n]));
}
}
}
int main(void)
{
fi=fopen("checker.in","r");
fo=fopen("checker.out","w");
fscanf(fi,"%d",&n);
fclose(fi);
upperlim=(1 << n)-1;
test(0,0,0,1);
fprintf(fo,"%dn",sum);
fclose(fo);
return 0;
}
上次修改時間 2017-05-26