内容:
皇后问题是一个古老而著名的问题，是回溯算法的典型问题，该问题是19世纪著名的数学家高斯于1850年提出的：
在8*8格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，
这样的格局称为问题的一个解。写一个程序求出所有解。使用二维数组实现。
步骤：
- 算法分析
? ? ? ?八皇后在棋盘上分布的各种可能的各局数目非常大，约等于2^32种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i-1个皇后处于不同列和不同的对角线位置即可。
? ? ? ?对于八皇后问题的求解可采用回溯算法，从上至下依次在每一行放置皇后，进行搜索，若在某一行的任意一列放置皇后均不能满足要求，则不再向下搜索，而进行回溯，回溯至有其他列可放置皇后的一行，再向下搜索，直到搜索至最后一行，找到可行解，输出结果。
? ? ? ?回溯法：回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种优选搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标时，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的、规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
? ? 2.概要设计
使用C语言，其中设置了以下函数
程序运行流程图如下：
?
3.运行结果：此处只展示部分可行解。
?
?4、源码如下：
typedef int bool;
#define true 1
#define false 0
//解的数目
int num=0;
//*m[8][8]表示棋盘，初始为*，表示未放置皇后
char m[8][8]={'*'};
//对于棋盘前row-1行已放置好皇后
//检查在第row行、第column列放置一枚皇后是否可行
bool Check(int row,int column)
{
int i,j;
if(row==1)return true;
//纵向只能有一枚皇后
for(i=0;i<=row-2;i++)
{
if(m[i][column-1]=='Q') return false;
}
//左上至右下只能有一枚皇后
i=row-2;
j=i-(row-column);
while(i>=0&&j>=0)
{
if(m[i][j]=='Q') return false;
i--;
j--;
}
//右上至左下只能有一枚皇后
i=row-2;
j=row+column-i-2;
while(i>=0&&j<=7)
{
if(m[i][j]=='Q') return false;
i--;
j++;
}
return true;
}
void Output() //当已放置8枚皇后，为可行解时，输出棋盘
{
int i,j;
num++;
printf("可行解 %d:\n",num);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("%c",m[i][j]);
}
printf("\n");
}
}
//采用递归函数实现八皇后回溯算法
//该函数求解当棋盘前row-1行已放置好皇后，在第row行放置皇后
void EigthQueen(int row)
{
int j;
for(j=0;j<8;j++)//考虑在第row行的各列放置皇后
{
m[row-1][j]='Q';//在其中一列放置皇后
if(Check(row,j+1)==true)//检查在该列放置皇后是否可行
{
if(row==8) Output();//若该列可放置皇后，且该列为最后一列，则找到一可行解，输出
else EigthQueen(row+1);//若该列可放置皇后，则向下一行继续搜索、求解
}
//取出该列的皇后，进行回溯，在其他列放置皇后
m[row-1][j]='*';
}
}
//主函数
int main()
{
EigthQueen(1);//求解八皇后问题
}