问题描述：八皇后问题是要求在八行八列的表格里面，要求放入8个皇后，要求所有的皇后都不能在同一行、同一列，并且不能在同一对角线上
解决方法：首先是采用回溯法（一种系统地搜索问题的解的方法），其思想是：从一条路往前走，能进则进，不能进则退回来，找另一条路继续试探
思路：
1、算法开始，清空棋盘，从棋盘的第一行第一列开始
2、检测该位置是否可以放皇后（同行、同列、对角线上都没有其他皇后），如果可以放则跳到第3步，如果冲突则跳到第4步
3、将皇后放入该位置
3.1 检测是否是最后一行，如果是则输出结果，然后将下一行设置为当前行，下一列设置为当前列，将该行的a[i]标志设置为初始值，即标志为该行皇后还没完成定位，重新新的一轮求解，
3.2 如果不是最后一行则继续下一行的皇后定位，跳到步骤2
4、列数加1
4.1如果当前列不是最后一列则跳到第2步
4.1如果当前列是最后一列，则回溯，即如果是已经是第一行了，那么结束程序。如果不是第一行则设置当前行为上一行，设置当前列为当前皇后位置的后一列，清除该行皇后的位置标志，继续步骤2。
程序说明：首先想到的是用什么数据结构表示棋盘和皇后，最直接的想法可能是用一个二维的数组表示，但是其实有一种很巧妙的做法，就是用一个一维的数组就搞定了，例如a[i]=j;表示有皇后在第i行的第j列，该数组的皇后已经不可能在同一行了，
判断位置是否可以，可以从是否同一列（用a[i]=col)和是否对角线上（可以利用线段斜率为-1判断，即abs(row-i)=abs(a[i]-col)
非递归方法：
#include<stdio.h>
#include<math.h>
#define QUEEN 8
#define INITIAL -1000
int a[QUEEN];
void init()
{
int p;
for(p=0;p<QUEEN;p++)
{
a[p] = INITIAL;
}
}
int value(int row,int col)
{
int i;
for (i = 0; i < QUEEN; ++i) //对棋盘进行扫描
{
if (a[i] == col || abs(i - row) == abs(a[i] - col)) //判断列冲突与斜线上的冲突
return 0;
}
return 1;
}
void print(){
int i, j;
for (i = 0; i < QUEEN; ++i)
{
for (j = 0; j < QUEEN; ++j)
{
if (a[i] != j) //a[i]为初始值
printf("%c ", '.');
else //a[i]表示在第i行的第a[i]列可以放置皇后
printf("%c ", '#');
}
printf("\n");
}
for (i = 0; i < QUEEN; ++i)
printf("%d ", a[i]);
printf("\n");
printf("--------------------------------\n");
}
void queen(){
int i,j,n=0;
i=0;
j=0;
while(i<QUEEN)//i行
{
while(j<QUEEN)//j列
{
if(value(i,j))//判断该位置是否可以放皇后
{
a[i]=j;//放置皇后
j=0;
break;
}
else
{
j++;
}
}
if(a[i]==INITIAL)//该行是否已经找到放皇后的位置
{
if(i==0)//已经回溯回到第一行了，程序结束
{
break;
}
else
{
--i;//设置当前行为该行
j=a[i]+1;//设置当前列为当前行皇后位置的下一列
a[i] = INITIAL;//清除该行的标志
continue;
}
}
if(i==QUEEN-1)//得到一种情况
{
printf("第%d种方式\n",++n);
print();//打印该情况
j=a[i]+1;//设置当前列为皇后位置的下一列
a[i]=INITIAL;//清除该行的标志
continue;
}
i++;//下一行
}
}
int main(void)
{
init();
queen();
return ;
}
递归方法：
#include <stdio.h>
#include <stdlib.h>
const int N=20; //最多放皇后的个数
int q[N]; //各皇后所在的行号
int cont = 0; //统计解得个数
//输出一个解
void print(int n)
{
int i,j;
cont++;
printf("第%d个解：",cont);
for(i=1;i<=n;i++)
printf("(%d,%d) ",i,q[i]);
printf("\n");
for(i=1;i<=n;i++) //行
{
for(j=1;j<=n;j++) //列
{
if(q[i]!=j)
printf("x ");
else
printf("Q ");
}
printf("\n");
}
}
//检验第i行的k列上是否可以摆放皇后
int find(int i,int 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)
{
place(1,8); //问题从最初状态解起
system("pause");
return 0;
}