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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *