C++ 八皇后問題

題目

在n*n的棋盤中，放置n個皇后，使他們互不攻擊，攻擊範圍為同行、同列、同對角線。請問有幾種放置方法？

解法

1. 經過觀察發現，每行每列恰好放一個皇后。解題時，我們可以逐行放，而且不用考慮橫向攻擊。
2. 使用回溯法：若當前步驟沒有合法選擇，則回到遞迴的上一層。
3. 如何判斷對角線？同一條對角線的x+y值相同(左下右上)、x-y值相同(左上右下)。
4. 用 put[x] 表示第 x 行皇后的 y 位置。
5. 用 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