USACO 1.5.4 Checker Challenge (N皇后問題) 位運算解法

經典的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;
}

相關日誌