#include<iostream>
using namespace std;
const int N = 20; //最多放皇后的个数
int q[N]; //各皇后所在的行号
int cont = 0; //统计解得个数
void print(int n){//输出解
int i, j;
cont++;
cout << "第" << cont << "个解:";
cout << endl;
for (i = 1; i <= n; i++){//行
for (j = 1; j <= n; j++){//列
if (q[i] != j)cout << "0";
else cout << "X";
}
cout << endl;
}
}
int find(int i, int k){//判断第i行的k列上是否可以摆放皇后
int j = 1;
while (j<i){//j=1~i-1是已经放置了皇后的行
//判断第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上
if (q[j] == k || abs(j - i) == abs(q[j] - k))return 0;
j++;
}return 1;
}
void place(int k, int n){//放置皇后到棋盘上
int j;
if (k > n) print(n);
else{
for (j = 1; j <= n; j++){ //试探第k行的每一个列
if (find(k, j)){
q[k] = j;
place(k + 1, n); //递归总是在成功完成了上次的任务的时候才做下一个任务
}
}
}
}
int main(void){
int n;
cout << "现有N×N的棋盘,放入N个皇后,要求所有皇后不能在同一行、同一列、同一对角线上。" << endl;
cout << "请输入皇后的个数(n<=20),n=:";
cin >> n;
if (n > 20) cout << "n值太大,不能求解!\n";
else{
cout << n<<"皇后问题求解如下:\n";
place(1, n); //问题从最初状态解起
cout << endl;
}
system("pause");
return 0;
}