#include <iostream>
#include <vector>
using namespace std;
void backtrack(int, vector<int>, int, int);
bool place(int, vector<int>);
void displayqueen(vector<int>, int, int);
int sum = 0;
int main(void)
{
int N;
int kind;
cout<<"请输入皇后的个数：";
cin>>N;
vector<int> x(N+1,0);
cout<<"----------------------------------"<<endl;
cout<<'\t'<<"结果显示的形式："<<endl;
cout<<'\t'<<" 1.直接形式."<<endl;
cout<<'\t'<<" 2.矩阵形式."<<endl;
cout<<"----------------------------------"<<endl;
cout<<"请输入你想显示结果的形式：";
cin>>kind;
backtrack(1, x, N, kind);
return 0;
}
void backtrack(int t, vector<int> x, int N, int kind)
{
if(t > N)
{
sum += 1;
displayqueen(x, N, kind);
}
else
{
for(int i=1; i<N+1; i++)
{
x[t] = i;
if(place(t, x))
{
backtrack(t+1, x, N, kind);
}
}
}
}
bool place(int k, vector<int> x)
{
for(int j=1; j<k; j++)
{
if((abs(k-j) == abs(x[k]-x[j])) || (x[k] == x[j]))
{
return false;
break;
}
}
return true;
}
void displayqueen(vector<int> x, int N, int kind)
{
if(kind == 1)
{
cout<<"第"<<sum<<"个解：";
for(int i=1; i<N+1; i++)
{
cout<<x[i]<<' ';
}
cout<<endl;
}
else
{
vector<vector<int> > S(N+1, vector<int>(N+1));
for(int i=1; i<N+1; i++)
{
for(int j=1; j<N+1; j++)
{
S[i][j] = 0;
}
}
for(i=1; i<N+1; i++)
{
for(int j=1; j<N+1; j++)
{
S[i][x[i]] = 1;
}
}
cout<<"第"<<sum<<"个解："<<endl;
for(i=1; i<N+1; i++)
{
for(int j=1; j<N+1; j++)
{
cout<<S[i][j]<<' ';
}
cout<<endl;
}
}
}
