数据结构之八皇后
#include
#include
#include
#include
int printed;
void draw(int* a,int k)
{
int i,j;
for(i=0;i<k;i++)
{
printf("\t");
for(j=0;j<k;j++)
if(a[i]-1==j) printf("Q "); else printf("- ");
printf("\n");
}
printf("\n");
}
void Settle(int *a,int iStep,int k)
{
int i,j,l,flag=1;
for(i=0;i<iStep-1;i++)
if(a[iStep-1]==a[i]) return;
if(iStep==k)
{
for(j=0;j<k;j++)
for(l=0;l<k&&l!=j;l++)
if(fabs(j-l)==fabs(a[j]-a[l])) flag=0;
if(flag)
{
for(i=0;i<k;i++)
printf("(%d,%d) ",i+1,a[i]);
printf("\n");
draw(a,k);
printed++;
}
flag=1;
}
for(i=1;i<=k;i++)
{
a[iStep]=i;
Settle(a,iStep+1,k);
}
}
void main()
{
int* a;
int k;
printf("Enter the size of the square:");
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));
system("cls");
Settle(a,0,k);
if(! printed) printf("No answers accepted!\n");
else printf("%d states available!\n",printed);
}
这是用C语言实现的，主要是递归全排列，具体不会的再问我吧^^
八皇后问题解决思路
先声明我们根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组x[t]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。我们用递归来做：这问题要求皇后所在的位置必须和其他皇后的位置不在同一行、列还有 把两个皇后看成点其|斜率|=1所以我们就要写这个限定条件用一个函数来实现：函数内对没一个已经放好的皇后的位置进行判断，所以就要有个循环。我们既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现对吧！这小问题是什么呢，不难发现我们要在8*8的方格里放好8个皇后那我们就要知道在8（列）*7（行）是怎么放的在有我们事先写好的判断函数放好最后行就搞定了；以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了。。。。。。所以我们是以一行怎么放作为一个单元那好我们就去建一个可以放好一行的函数backtrack（int t）里面的t表示是第几行，在main函数调用的时候第一次传进来的是0也就是从第一行开始判断。我们就开始写函数体了： 没一行有8个位置可以放每一个位置我们都要去判断一下所以我们就用循环来搞定。 在这个循环里面我们让x[t]=i也就是从这一行的第一个开始判断。放好后就要去判断 是否符合条件。如果符合条件我们就在调用这个函数本身backtrack不过穿进去的参数 是t+1也就是下一行的意思。在进行判断下一行之前我们要判断一下t是不是等于8也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。打印8*8的矩阵（提示在写一个函数）皇后的位置用1表示出来没有的用0表示。这是我自己的体会 ; 里面可能有写表述不当的地方要是不懂可以来问我！（第一次回答这么长的问题）
数据结构八皇后问题
{输入棋盘大小值n;m=0; //从空配置开始notcatch=1; //空配置中皇后不能相互捕捉do{if(notcatch){if(m==n){输出解;调整(形成下一个候选解else扩展当前候选解至下一列; //向前试探else调整(形成下一个候选解); //向后回溯notcatch = 检查当前候选解的合理性*/#include "stdlib.h"#define MAXN 100//全局变量及全局工作数组定义int m,n,NotCatch;int ColFlag[MAXN+1]; /*表示第i列的第ColFlag[i]行有皇后,(1:有;0:没有)*/int RowFlag[MAXN+1]; /*RowFlag[i]:表示第i行没有皇后(1:没有;0:有)*/int upBiasFlag[2*MAXN+1]; /*upBiasFlag[i]:表示第i条上斜线(右高左斜)没有皇后(1:没有;0:有)*/int dnBiasFlag[2*MAXN+1]; /*dnBiasFlag[i]:表示第i条下斜线(左高右斜)没有皇后(1:没有;0:有)*///显示输入填写的数字void ArrangeQueen(){int i;char answer;printf("输入棋盘边格数：");scanf("%d",&n);for(i=0;i求采纳为满意回答。
