a160 - 祖靈想要下棋!!!!!!!!
題目描述
題目要求找出 N 皇后問題的所有解，並以棋盤的形式輸出。N 皇后問題是指在一個 N x N 的棋盤上放置 N 個皇后，使得任何兩個皇后都不能互相攻擊（即不在同一行、同一列或同一對角線上）。輸出時，用 'x' 表示空格，用 'Q' 表示皇后。最後輸出解的總數。
解題思路
這題使用 backtracking (回溯法) 解決 N 皇后問題。valid_position 函數檢查在給定的位置放置皇后是否安全，即是否與已放置的皇后衝突。put 函數遞迴地嘗試在每一列放置皇后。如果找到一個安全的位置，則繼續遞迴到下一列。如果所有列都放置了皇后，則輸出棋盤並增加解的計數。回溯法通過嘗試所有可能的放置方式，並在發現衝突時回溯到上一步，最終找到所有有效的解。
複雜度分析
- 時間複雜度: O(N!)。在最壞的情況下，需要嘗試所有可能的皇后放置方式。
- 空間複雜度: O(N)。主要用於儲存棋盤狀態和遞迴調用堆疊。
程式碼
#include <iostream>
using namespace std;
int n=0,ans=0;
bool space[13][13];
bool valid_position(int r , int c){
for(int i=0;i<n;++i){
if(space[i][c]==1&&i!=r)
return 0;
else if(space[r][i]==1&&i!=c)
return 0;
else if(r+i<n&&c+i<n&&space[r+i][c+i]==1)
return 0;
else if(r+i<n&&c-i>=0&&space[r+i][c-i]==1)
return 0;
else if(r-i>=0&&c+i<n&&space[r-i][c+i]==1)
return 0;
else if(r-i>=0&&c-i>=0&&space[r-i][c-i]==1)
return 0;
}
return 1;
}
void put(int col){
for(int j=0;j<n;++j){
space[col][j]=valid_position(col,j);
if(space[col][j]==1&&col==n-1){
for(int ii=0;ii<n;++ii){
for(int jj=0;jj<n;++jj){
if(space[ii][jj])
cout << 'Q';
else
cout << 'x';
}
cout << "\n";
}
++ans;
cout << "\n";
space[col][j]=0;
break;
}
else if(space[col][j]==1){
put(col+1);
space[col][j]=0;
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
ans=0;
for(int i=0;i<13;++i)
for(int j=0;j<13;++j)
space[i][j]=0;
put(0);
cout << "\n" << ans << "\n";
}
}