K皇后問題

FZU比賽殘留了一題搜索題K Queen?沒做, 題目大意就是在m*n的棋盤上布置k個皇后，使得這k個皇后互不攻擊（這里的攻擊含義同“八皇后問題”，即兩個皇后不可以在同一行，同一列及同一斜線上)。其中1≤m*n≤150,1≤k≤50，時限10s
????
??? 其實從題目中我們可以推出一個很簡單但是很重要的結論，即min(m, n)?< 13， 言下之意就是說這個棋盤的較短的一邊長度不會超過12，這樣就不會對150這個數字感到恐懼了。同樣，我們可以斷言 k <= min(m, n)。另外一個簡單的結論是
f[m][n][k] = f[n][m][k] (f[m][n][k]表示m*n的棋盤放置k個互不攻擊的皇后種數)

??? 其次，我們可能想到直接回溯進行硬搜，那很不幸這樣是行不通的。為什么行不通，很多相似的狀態進行重復的搜索，我們需要把那些相似狀態給去除掉，也就是要加上一個強力的剪枝才行。 不難發現，我們要處理的是一個棋盤，而棋盤具有某些對稱的性質。通過利用這些性質我們可以有效的減少搜索空間，從而使得效率得到很大提升。（理論上說應該能減少1/4，我在使用過程中為了方便，減少了1/2)

?? 能否更快些呢？記得以前在群里頭聽討論說n皇后有個超快的位運算版本，上網搜了搜，發現確實很強悍，如果配合上位運算再加上對稱性，那是相當的完美了。(關于n皇后位運算版本的介紹可以參加matrix67的blog的這篇文章)

?? 下面是AC的代碼，6.2s //農夫三拳@seu #include <stdio.h> #include <string.h>typedef long long i64;i64 s[151][151][51]; int m, n, x, y; int MASK; i64 ans;void dfs(int m, int n, int row, int ld, int rd, int num, int p, int index) {if(num == p)ans++;else if(index < m){if(num + m - index > p)dfs(m, n, row, ld << 1, rd >> 1, num, p, index + 1);int pos = MASK & ~(row | rd | ld);while(pos != 0){int pp = pos & -pos;pos = pos - pp;dfs(m, n, row + pp, (ld + pp) << 1, (rd + pp) >> 1, num + 1, p, index + 1);}} }i64 solve(int m, int n, int p) {if(s[m][n][p] != -1)return s[m][n][p];if(p > n)return 0;i64 ret = 0;int i, j;for(j = 0; j < n; j++){int pos = 1 << (n - 1 - j);ans = 0;dfs(m, n, pos, pos << 1, pos >> 1, 1, p, 1); ret += ans;} s[m][n][p] = ret;return ret; }int main() {int i, j;memset(s, -1, sizeof(s));while(scanf("%d%d%d%d", &m, &n, &x, &y) == 4){if(m < n && n > 31){int t = m;m = n;n = t;}if(y > n)y = n;MASK = (1 << n) - 1;i64 res = 0;if(x == 0)res++, x = 1;for(i = x; i <= y; i++){for(j = i; j <= m; j++)res += solve(j, n, i);}printf("%lld\n", res);}return 0; }

后記:
1. 通過實驗發現，當給定m*n(n > m)棋盤的時候，在n < 31的范圍以內盡量使n較大，反之將m，n進行交換處理，這樣可以充分的利用int范圍內的位運算的效果。 其實當用64位的位運算之后，速度反而降下來了。
2. 如果利用一行的對稱型，我們只要枚舉第一個皇后在某行的列的一半就可以了 轉自：http://www.cnblogs.com/drizzlecrj/archive/2007/10/04/913703.html

總結

以上是生活随笔為你收集整理的K皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。