Question

用c++编程：八皇后问题。在一个8×8的国际象棋盘，有八个皇后，每个皇后占一格；要求棋盘上放上八个

用c++编程：八皇后问题。在一个8×8的国际象棋盘，有八个皇后，每个皇后占一格；要求棋盘上放上八个皇后时不会出现相互“攻击”的现象，即不能有两个皇后在同一行、列或对角线上。问有多少种不同的方法。

Answer 1

//八皇后问题
#include <iostream>
using namespace std;
const int N=8;
int x[9];
int num = 0; //统计解的个数

//输出一种布局
void print(int *p,int n){
int i,j;
cout << num <<":\n";
for(i=1; i<=n; i++){
for(j=1; j<p[i]; j++)
cout <<" - ";
cout <<" Q ";
for(j=p[i]+1; j<=n; j++)
cout <<" - ";
cout <<endl;
}
}

//求解n皇后布局
void nQueens(int n){
int k=1;
int j=1, flag=1;
x[1]=0;
while( k>0 ){
x[k]+=1; //转到下一行
while( x[k]<=n ){
//判断第k个皇后可否放在第x[k]列
j=flag=1;
while( j<k && flag ){
if( x[j]==x[k] || (abs(x[j]-x[k])==abs(j-k)) )
flag=0;
j++;
}
if( flag==1 ) //可放
break;
//如果无解，最后一个皇后就会安排到格子外面去
x[k]+=1;
}
if( x[k]<=n ){
//第k个皇后仍被放置在格子内，有解
if( k==n ){
num++;
print(x,N); //输出这种布局
}else{
k++;
x[k]=0; //转到下一行
}
}else //第k个皇后已经被放置到格子外了，没解，回溯
k--; //回溯
}
}

int main(){
nQueens(N);
cout <<"共有" <<num <<"种布局方法。\n";
return 0;
}

追问

最后是有92种吗