題目描述
會下國際象棋的人都很清楚:皇後可以在橫、豎、斜線上不限步數地吃掉其他棋子。如何将8個皇後放在棋盤上(有8 * 8個方格),使它們誰也不能被吃掉!這就是著名的八皇後問題。
輸入
一個整數n( 1 < = n < = 10 )
輸出
每行輸出對應一種方案,按字典序輸出所有方案。每種方案順序輸出皇後所在的列号,相鄰兩數之間用空格隔開。如果一組可行方案都沒有,輸出“no solute!”
樣例輸入
4
樣例輸出
2 4 1 3
3 1 4 2
#include<bits/stdc++.h>
using namespace std;
int n,a[10];
bool flag[10]={false};
bool no;
void DFS(int index){
for(int i=0;i<index-1;i++){//剪枝
for(int j=i+1;j<index;j++){
if(abs(i-j)==abs(a[i]-a[j]))
return;
}
}
if(index==n){
for(int i=0;i<n;i++){
cout<<a[i]+1;
if(i<n-1) cout<<" ";
}
cout<<"\n";
no=false;
return;
}
for(int i=0;i<n;i++){
if(!flag[i]){
a[index]=i;
flag[i]=true;
DFS(index+1);
flag[i]=false;
}
}
}
int main(){
while(cin>>n){
no=true;
DFS(0);
if(no) cout<<"no solute!"<<endl;
}
return 0;
}