[UVa]11195:Another n-Queen Problem

這題要用點bitwise運算的概念，
把原本用陣列記錄列、斜線的放置，
改成用bits來記錄。
由於有點複雜，
我稍微解釋一下程式碼。

y_board[i] = (1<<n)-1;

這裡是讓可以放置皇后的位置用1來記錄，
不可以放置皇后的位置('*')用0來記錄。
那y_board這個陣列是以row(y)來當索引值，
然後col的部份用bits來記錄。

if( s[j] == '*' )
　　y_board[i] ^= (1<<j);

這裡就是讓*的位置用1來做XOR運算，
簡單來說就是把j位置的1改成0。

backtracking( n, 0, (1<<n)-1, (1;<<(2*n-1))-
1, (1<<(2*n-1))-1);

這邊把記錄x和記錄兩種斜線的bits丟進去backtracking，
並且x的n個位數都是1，表示目前都可以擺，
而斜線部分的2*n-1個位數也都是1，也表示目前都可以擺。

int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);

將目前跑到那行row的斜線號碼全部抓出來，
例如8皇后的第一個row(row[0])，
x+y種類的斜線編號分別是
0+0=0,0+1=1,0+2=2,0+3=3......0+7=7，
也就是說用slash1 >> 0，
這樣即可讓slash1從個位數(2進位)開始的7個位數都剛好對應每一格。
而x-y+(2*n-1)種類的斜線編號分別是
0-0+15=15,0-1+15=14........0-7+15=8，
正好是從高位數(2進位)數過來0位數，
那為了推到個位數(2進位)，
就變成slash2 >> 8-0-1，
這樣就可以讓高位數(2進位)的7個位數推到個位數(2進位)來。

int canputqueen = y_board[y] & x & nowslash1 & nowslash2;

用&看看每一格是否能夠放置皇后，
y_board[]檢查是否為*，
x檢查是否這個col被放置皇后，
nowslash1檢查是否這條斜線被放置皇后，
nowslash2檢查另外一種斜線是否被放置皇后，
如果全部都是1，就表示這格可以放置皇后。

while( canputqueen )
{
　　xput = canputqueen & (-canputqueen);
　　backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
　　canputqueen ^= xput;
}

第一行自己&負自己，可以得到二進位最低位的1，
而我就從這最低位的1開始放置皇后，
那麼x就要記錄放置皇后，
而slash1和slash2也要記錄放置了皇后，
最後再將這個1從canputqueen裡面去除，
再繼續把皇后放在下一個1的位置。

我不知道這樣是否有助於讓你了解這題，
如果還是不了解就底下留言問，
或是先自行推演看看，
或是問其他你認識的人討論這樣XD

這題我剛開始就直接backtracking，
結果時間就爆掉了= ="
後來看到討論都說要用bitmask，
我就用了，
然後一直RE，
結論是我沒加return 0; = =""""""

[C](0.956)

	#include<stdio.h>
	int y_board[20] = {0};
	int answer = 0;
	void backtracking( int n, int y, int x, int slash1, int slash2 )
	{
	if( y == n )
	{
	answer++;
	return;
	}
	int nowslash1 = slash1 >> y;
	int nowslash2 = slash2 >> (n-y-1);
	int canputqueen = y_board[y] & x & nowslash1 & nowslash2;
	int xput;
	while( canputqueen )
	{
	xput = canputqueen & (-canputqueen);
	backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
	canputqueen ^= xput;
	}
	}
	int main()
	{
	int n;
	int casenumber = 1;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	int i, j;
	char s[20] = {0};
	for( i = 0 ; i < n ; i++ )
	{
	scanf( "%s", s );
	y_board[i] = (1<<n)-1;
	for( j = 0 ; j < n ; j++ )
	if( s[j] == '*' )
	y_board[i] ^= (1<<j);
	}
	answer = 0;
	backtracking( n, 0, (1<<n)-1, (1<<(2*n-1))-1, (1<<(2*n-1))-1);
	printf( "Case %d: %d\n", casenumber, answer );
	casenumber++;
	}
	return 0;
	}

view raw UVa11195.c hosted with ❤ by GitHub