Beyond the Void
BYVoid
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

相關日誌