#include<bits/stdc++.h>
using namespace std;
#define max 10
int arr[max];
void display(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i]!=j)
cout<<"_ ";
else
cout<<"Q ";
}
cout<<endl;
}
cout<<"=++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
}
bool canplace(int k,int i){
for(int j=1;j<k;j++){
if(arr[j]==i || abs(arr[j]-i)==abs(j-k))
return false;
}
return true;
}
void nQueen(int k,int n){
for(int j=1;j<=n;j++){
if(canplace(k,j)){
arr[k]=j;
if(k==n)
display(n);
else{
nQueen(k+1,n);
}
}
}
}
int main(){
int n=4;
nQueen(1,n);
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBtYXggMTAKaW50IGFyclttYXhdOwoKdm9pZCBkaXNwbGF5KGludCBuKXsKCWZvcihpbnQgaT0xO2k8PW47aSsrKXsKCQlmb3IoaW50IGo9MTtqPD1uO2orKyl7CgkJCWlmKGFycltpXSE9aikKCQkJY291dDw8Il8gICI7CgkJCWVsc2UKCQkJY291dDw8IlEgIjsKCQl9CgkJY291dDw8ZW5kbDsKCX0KCWNvdXQ8PCI9KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrIjw8ZW5kbDsKfQpib29sIGNhbnBsYWNlKGludCBrLGludCBpKXsKCWZvcihpbnQgaj0xO2o8aztqKyspewoJCWlmKGFycltqXT09aSB8fCBhYnMoYXJyW2pdLWkpPT1hYnMoai1rKSkKCQkgcmV0dXJuIGZhbHNlOwoJfQoJcmV0dXJuIHRydWU7Cn0Kdm9pZCBuUXVlZW4oaW50IGssaW50IG4pewoJZm9yKGludCBqPTE7ajw9bjtqKyspewoJCWlmKGNhbnBsYWNlKGssaikpewoJCQlhcnJba109ajsKCQkJaWYoaz09bikKCQkJZGlzcGxheShuKTsKCQkJZWxzZXsKCQkJCW5RdWVlbihrKzEsbik7CgkJCX0KCQl9Cgl9Cn0KCmludCBtYWluKCl7CglpbnQgbj00OwoJblF1ZWVuKDEsbik7CglyZXR1cm4gMDsKfQ==