Question

编写程序对八皇后问题进行求解（用C++）：编写程序对八皇后问题进行求解： 在8行8列的棋盘上放置8个皇后，

Answer 1

这是一个古老的具有代表性的问题，用计算机求解时的算法也很多，这里仅介绍一种。
采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。如：a[1]=5，表示在棋盘的第一例的第五行放一个皇后。
程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。
程序采用回溯法，算法的细节参看程序。
//网上找的，我自己在vc上编写了一遍，自己设断点，一步步看它的运行过程，很经典，易懂
#include<iostream.h>
#define NUM 8/*定义数组的大小*/
int a[NUM+1];
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;/*正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素*/
a[1]=1;/*为数组的第一个元素赋初值*/
cout<<"8皇后可能的结果:"<<endl;
while(not_finish) /*not_finish=1:处理尚未结束*/
{
while(not_finish&&i<=NUM)/*处理尚未结束且还没处理到第NUM个元素*/
{
for(flag=1,k=1;flag&&k<i;k++)/*判断是否有多个皇后在同一行*/
if(a[k]==a[i])flag=0;
for(k=1;flag&&k<i;k++) /*判断是否有多个皇后在同一对角线*/
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
if(!flag)
{
if(a[i]==a[i-1])/*若a[i]的值已经经过一圈追上a[i-1]的值*/
{
i--;/*退回一步，重新试探处理前一个元素*/
if(i>1&&a[i]==NUM)
a[i]=1;/*当a[i]为NUM时将a[i]的值置1*/
else if(i==1&&a[i]==NUM)
not_finish=0;/*当第一位的值达到NUM时结束*/
else a[i]++;
}
else if(a[i]==NUM) a[i]=1;
else a[i]++;/*将a[i]的值取下一个值*/
}
else if(++i<=NUM)
if(a[i-1]==NUM) a[i]=1;/*若前一个元素的值为NUM则a[i]=1*/
else a[i]=a[i-1]+1; /*否则元素的值为前一个元素的下一个值*/
}
if(not_finish)
{
++count;
if((count-1)%3==0) cout<<endl;
cout<<"["<<count<<"]:";
for(k=1;k<=NUM;k++)/*输出结果*/
cout<<a[k];
cout<<" ";
if(a[NUM-1]<NUM) a[NUM-1]++;/*修改倒数第二位的值*/
else a[NUM-1]=1;
i=NUM-1; /*开始寻找下一个足条件的解*/
}
}
}