2010年1月13日星期三.sgu224
k皇后問題的位運算優(yōu)化
這個是基本上學(xué)過編程的人都會寫過的程序。
但是對于這個NP問題，只能搜索解決。如果寫的不好的話很容易超時。
今天在Matrix67的文章中看到了使用位運算的方法，本來我還想用dancing links來
搜一下呢，這個方法太精妙了！
傳送門: http://www.matrix67.com/blog/archives/266
我們知道(x&-x)是求x的最低位1，而這個操作是非常快的。
在這個遞推過程中，只保存當(dāng)前行的不可行解，然后利用求反和上邊說的求最低位1的方法對當(dāng)前
行的可行解進行遍歷，然后遞推求解
不過這個不是n皇后問題，是k皇后，所以還需要對算法進行一些小小的改動。
//http://m.shnenglu.com/schindlerlee/
typedef long long LL;
const int N = 16;
int n, k;
#define bin(x) (1 << (x))
#define L(x) ((x) << 1)
#define R(x) ((x) >> 1)
#define low(x) ((x) & -(x))
int res = 0, full;
//row代表列的狀態(tài)，ld代表左對角線，rd代表右對角線，cnt是已經(jīng)使用的皇后數(shù)
//line是已經(jīng)推到了第幾第幾行
void dfs(int row, int ld, int rd, int cnt, int line)
{
int p, t;
if (line < n && cnt < k) {
t = full & ~(row | ld | rd);
while (t != 0) {
p = low(t);
t ^= p;
dfs(row + p, L(ld + p), R(rd + p), cnt + 1, line + 1); //下一行
}
dfs(row, L(ld), R(rd), cnt, line + 1); //此行空
} else if(cnt == k){
res++;
}
}
int main()
{
int i, j;
scanf("%d%d", &n, &k);
full = bin(n) - 1;
dfs(0, 0, 0, 0, 0);
printf("%d\n", res);
return 0;
}