題目
在n*n的棋盤中,放置n個皇后,使他們互不攻擊,攻擊範圍為同行、同列、同對角線。請問有幾種放置方法?
解法
- 經過觀察發現,每行每列恰好放一個皇后。解題時,我們可以逐行放,而且不用考慮橫向攻擊。
- 使用回溯法:若當前步驟沒有合法選擇,則回到遞迴的上一層。
- 如何判斷對角線?同一條對角線的x+y值相同(左下右上)、x-y值相同(左上右下)。
- 用 put[x] 表示第 x 行皇后的 y 位置。
- 用 visited[2][n] 記錄所在的列、兩個對角線是否已有皇后。(i=0:列, i=1:左下右上, i=2:左上右下)(因x-y值會出現負值,所以要+n)
C++ Code
#include <iostream>
using namespace std;
int n, ans=0, put[100], visited[3][100];
void search(int now){
if(now == n) ans++; //跑到最後一行了,代表這組解ok
else for(int i=0; i<n; i++){
if(!visited[0][i] && !visited[1][now+i] && !visited[2][now-i+n]){
//比直的;比x+y對角線(x是now,y是i);比x-y對角線(因為會出現負值所以+n)
put[now] = i; //把第now行的皇后放在第i列
visited[0][i] = visited[1][now+i] = visited[2][now-i+n] = 1;
search(now+1);
visited[0][i] = visited[1][now+i] = visited[2][now-i+n] = 0; //改回來
}
}
}
int main(){
cin >> n;
search(0);
cout << ans << '\n';
}
//[input] 8 [output] 92
參考資料:算法競賽入門經典(第2版) 7.4.1 八皇后問題 P.191