求教C语言回溯法写出八皇后问题的92种解
(1)全排列
将自然数1~n进行排列，***形成n!中排列方式，叫做全排列。
例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，***3!=6种。
(2)8皇后（或者n皇后）
保证8个皇后不能互相攻击，即保证每一横行、每一竖行、每一斜行最多一个皇后。
我们撇开第三个条件，如果每一横行、每一竖行都只有一个皇后。
将8*8棋盘标上坐标。我们讨论其中的一种解法：
- - - - - - - Q - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - -如果用坐标表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
将横坐标按次序排列，纵坐标就是8/4/1/3/6/2/7/5。这就是1~8的一个全排列。
我们将1~8的全排列存入输入a[]中(a[0]~a[7])，然后8个皇后的坐标就是(i+1,a[i])，其中i为0~7。
这样就能保证任意两个不会同一行、同一列了。
置于斜行，你知道的，两个点之间连线的斜率绝对值为1或者-1即为同一斜行，充要条件是|x1-x2|=|y1-y2|（两个点的坐标为（x1,y1）(x2,y2)）。我们在输出的时候进行判断，任意两个点如果满足上述等式，则判为失败，不输出。
下面附上代码：添加必要的注释，其中全排列的实现看看注释应该可以看懂：
#include<stdio.h>#include<math.h>
#include<string.h>
#include<stdlib.h>
int?printed;
//该函数用于画图，这里为了节约空间则略去
//读者只需要将draw(a,k);去掉注释即可画图
void?draw(int*?a,int?k)
{
int?i,j;
for(i=0;i<k;i++)
{
printf("\t");
for(j=0;j<k;j++)
//有皇后输出Q，否则输出-
if(a[i]-1==j)?printf("Q?");?else?printf("-?");
printf("\n");
}
printf("\n");
}
//递归实现全排列,a是数组，iStep是位置的测试点，k是皇后的个数，一般等于8
void?Settle(int?*a,int?iStep,int?k)
{
int?i,j,l,flag=1;
//如果iStep的数字等于a之前的数字，则存在重复，返回
for(i=0;i<iStep-1;i++)
if(a[iStep-1]==a[i])?return;
//如果iStep==k，即递归结束到最后一位，可以验证是否斜行满足
if(iStep==k)?
{
//双重循环判断是否斜行满足
for(j=0;j<k;j++)
for(l=0;l<k&&l!=j;l++)
//如果不满足，则flag=0
if(fabs(j-l)==fabs(a[j]-a[l]))?flag=0;
//如果flag==1，则通过了斜行的所有测试，输出。
if(flag)
{
for(i=0;i<k;i++)
printf("(%d,%d)?",i+1,a[i]);
printf("\n");
//如果去掉这里的注释可以获得画图，由于空间不够，这里略去
// draw(a,k);
//printed变量计算有多少满足题意的结果，是全局变量
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));
//清屏，从iStep=0处进入递归
system("cls");
Settle(a,0,k);
//判断最后是否有结果
if(!?printed)?printf("No?answers?accepted!\n");
else?printf("%d?states?available!\n",printed);
}
附输出结果（输入k=8）：
(1,1)?(2,5)?(3,8)?(4,6)?(5,3)?(6,7)?(7,2)?(8,4)
(1,1)?(2,6)?(3,8)?(4,3)?(5,7)?(6,4)?(7,2)?(8,5)
(1,1)?(2,7)?(3,4)?(4,6)?(5,8)?(6,2)?(7,5)?(8,3)
(1,1)?(2,7)?(3,5)?(4,8)?(5,2)?(6,4)?(7,6)?(8,3)
(1,2)?(2,4)?(3,6)?(4,8)?(5,3)?(6,1)?(7,7)?(8,5)
(1,2)?(2,5)?(3,7)?(4,1)?(5,3)?(6,8)?(7,6)?(8,4)
(1,2)?(2,5)?(3,7)?(4,4)?(5,1)?(6,8)?(7,6)?(8,3)
(1,2)?(2,6)?(3,1)?(4,7)?(5,4)?(6,8)?(7,3)?(8,5)
(1,2)?(2,6)?(3,8)?(4,3)?(5,1)?(6,4)?(7,7)?(8,5)
(1,2)?(2,7)?(3,3)?(4,6)?(5,8)?(6,5)?(7,1)?(8,4)
(1,2)?(2,7)?(3,5)?(4,8)?(5,1)?(6,4)?(7,6)?(8,3)
(1,2)?(2,8)?(3,6)?(4,1)?(5,3)?(6,5)?(7,7)?(8,4)
(1,3)?(2,1)?(3,7)?(4,5)?(5,8)?(6,2)?(7,4)?(8,6)
(1,3)?(2,5)?(3,2)?(4,8)?(5,1)?(6,7)?(7,4)?(8,6)
(1,3)?(2,5)?(3,2)?(4,8)?(5,6)?(6,4)?(7,7)?(8,1)
(1,3)?(2,5)?(3,7)?(4,1)?(5,4)?(6,2)?(7,8)?(8,6)
(1,3)?(2,5)?(3,8)?(4,4)?(5,1)?(6,7)?(7,2)?(8,6)
(1,3)?(2,6)?(3,2)?(4,5)?(5,8)?(6,1)?(7,7)?(8,4)
(1,3)?(2,6)?(3,2)?(4,7)?(5,1)?(6,4)?(7,8)?(8,5)
(1,3)?(2,6)?(3,2)?(4,7)?(5,5)?(6,1)?(7,8)?(8,4)
(1,3)?(2,6)?(3,4)?(4,1)?(5,8)?(6,5)?(7,7)?(8,2)
(1,3)?(2,6)?(3,4)?(4,2)?(5,8)?(6,5)?(7,7)?(8,1)
(1,3)?(2,6)?(3,8)?(4,1)?(5,4)?(6,7)?(7,5)?(8,2)
(1,3)?(2,6)?(3,8)?(4,1)?(5,5)?(6,7)?(7,2)?(8,4)
(1,3)?(2,6)?(3,8)?(4,2)?(5,4)?(6,1)?(7,7)?(8,5)
(1,3)?(2,7)?(3,2)?(4,8)?(5,5)?(6,1)?(7,4)?(8,6)
(1,3)?(2,7)?(3,2)?(4,8)?(5,6)?(6,4)?(7,1)?(8,5)
(1,3)?(2,8)?(3,4)?(4,7)?(5,1)?(6,6)?(7,2)?(8,5)
(1,4)?(2,1)?(3,5)?(4,8)?(5,2)?(6,7)?(7,3)?(8,6)
(1,4)?(2,1)?(3,5)?(4,8)?(5,6)?(6,3)?(7,7)?(8,2)
(1,4)?(2,2)?(3,5)?(4,8)?(5,6)?(6,1)?(7,3)?(8,7)
(1,4)?(2,2)?(3,7)?(4,3)?(5,6)?(6,8)?(7,1)?(8,5)
(1,4)?(2,2)?(3,7)?(4,3)?(5,6)?(6,8)?(7,5)?(8,1)
(1,4)?(2,2)?(3,7)?(4,5)?(5,1)?(6,8)?(7,6)?(8,3)
(1,4)?(2,2)?(3,8)?(4,5)?(5,7)?(6,1)?(7,3)?(8,6)
(1,4)?(2,2)?(3,8)?(4,6)?(5,1)?(6,3)?(7,5)?(8,7)
(1,4)?(2,6)?(3,1)?(4,5)?(5,2)?(6,8)?(7,3)?(8,7)
(1,4)?(2,6)?(3,8)?(4,2)?(5,7)?(6,1)?(7,3)?(8,5)
(1,4)?(2,6)?(3,8)?(4,3)?(5,1)?(6,7)?(7,5)?(8,2)
(1,4)?(2,7)?(3,1)?(4,8)?(5,5)?(6,2)?(7,6)?(8,3)
(1,4)?(2,7)?(3,3)?(4,8)?(5,2)?(6,5)?(7,1)?(8,6)
(1,4)?(2,7)?(3,5)?(4,2)?(5,6)?(6,1)?(7,3)?(8,8)
(1,4)?(2,7)?(3,5)?(4,3)?(5,1)?(6,6)?(7,8)?(8,2)
(1,4)?(2,8)?(3,1)?(4,3)?(5,6)?(6,2)?(7,7)?(8,5)
(1,4)?(2,8)?(3,1)?(4,5)?(5,7)?(6,2)?(7,6)?(8,3)
(1,4)?(2,8)?(3,5)?(4,3)?(5,1)?(6,7)?(7,2)?(8,6)
(1,5)?(2,1)?(3,4)?(4,6)?(5,8)?(6,2)?(7,7)?(8,3)
(1,5)?(2,1)?(3,8)?(4,4)?(5,2)?(6,7)?(7,3)?(8,6)
(1,5)?(2,1)?(3,8)?(4,6)?(5,3)?(6,7)?(7,2)?(8,4)
(1,5)?(2,2)?(3,4)?(4,6)?(5,8)?(6,3)?(7,1)?(8,7)
(1,5)?(2,2)?(3,4)?(4,7)?(5,3)?(6,8)?(7,6)?(8,1)
(1,5)?(2,2)?(3,6)?(4,1)?(5,7)?(6,4)?(7,8)?(8,3)
(1,5)?(2,2)?(3,8)?(4,1)?(5,4)?(6,7)?(7,3)?(8,6)
(1,5)?(2,3)?(3,1)?(4,6)?(5,8)?(6,2)?(7,4)?(8,7)
(1,5)?(2,3)?(3,1)?(4,7)?(5,2)?(6,8)?(7,6)?(8,4)
(1,5)?(2,3)?(3,8)?(4,4)?(5,7)?(6,1)?(7,6)?(8,2)
(1,5)?(2,7)?(3,1)?(4,3)?(5,8)?(6,6)?(7,4)?(8,2)
(1,5)?(2,7)?(3,1)?(4,4)?(5,2)?(6,8)?(7,6)?(8,3)
(1,5)?(2,7)?(3,2)?(4,4)?(5,8)?(6,1)?(7,3)?(8,6)
(1,5)?(2,7)?(3,2)?(4,6)?(5,3)?(6,1)?(7,4)?(8,8)
(1,5)?(2,7)?(3,2)?(4,6)?(5,3)?(6,1)?(7,8)?(8,4)
(1,5)?(2,7)?(3,4)?(4,1)?(5,3)?(6,8)?(7,6)?(8,2)
(1,5)?(2,8)?(3,4)?(4,1)?(5,3)?(6,6)?(7,2)?(8,7)
(1,5)?(2,8)?(3,4)?(4,1)?(5,7)?(6,2)?(7,6)?(8,3)
(1,6)?(2,1)?(3,5)?(4,2)?(5,8)?(6,3)?(7,7)?(8,4)
(1,6)?(2,2)?(3,7)?(4,1)?(5,3)?(6,5)?(7,8)?(8,4)
(1,6)?(2,2)?(3,7)?(4,1)?(5,4)?(6,8)?(7,5)?(8,3)
(1,6)?(2,3)?(3,1)?(4,7)?(5,5)?(6,8)?(7,2)?(8,4)
(1,6)?(2,3)?(3,1)?(4,8)?(5,4)?(6,2)?(7,7)?(8,5)
(1,6)?(2,3)?(3,1)?(4,8)?(5,5)?(6,2)?(7,4)?(8,7)
(1,6)?(2,3)?(3,5)?(4,7)?(5,1)?(6,4)?(7,2)?(8,8)
(1,6)?(2,3)?(3,5)?(4,8)?(5,1)?(6,4)?(7,2)?(8,7)
(1,6)?(2,3)?(3,7)?(4,2)?(5,4)?(6,8)?(7,1)?(8,5)
(1,6)?(2,3)?(3,7)?(4,2)?(5,8)?(6,5)?(7,1)?(8,4)
(1,6)?(2,3)?(3,7)?(4,4)?(5,1)?(6,8)?(7,2)?(8,5)
(1,6)?(2,4)?(3,1)?(4,5)?(5,8)?(6,2)?(7,7)?(8,3)
(1,6)?(2,4)?(3,2)?(4,8)?(5,5)?(6,7)?(7,1)?(8,3)
(1,6)?(2,4)?(3,7)?(4,1)?(5,3)?(6,5)?(7,2)?(8,8)
(1,6)?(2,4)?(3,7)?(4,1)?(5,8)?(6,2)?(7,5)?(8,3)
(1,6)?(2,8)?(3,2)?(4,4)?(5,1)?(6,7)?(7,5)?(8,3)
(1,7)?(2,1)?(3,3)?(4,8)?(5,6)?(6,4)?(7,2)?(8,5)
(1,7)?(2,2)?(3,4)?(4,1)?(5,8)?(6,5)?(7,3)?(8,6)
(1,7)?(2,2)?(3,6)?(4,3)?(5,1)?(6,4)?(7,8)?(8,5)
(1,7)?(2,3)?(3,1)?(4,6)?(5,8)?(6,5)?(7,2)?(8,4)
(1,7)?(2,3)?(3,8)?(4,2)?(5,5)?(6,1)?(7,6)?(8,4)
(1,7)?(2,4)?(3,2)?(4,5)?(5,8)?(6,1)?(7,3)?(8,6)
(1,7)?(2,4)?(3,2)?(4,8)?(5,6)?(6,1)?(7,3)?(8,5)
(1,7)?(2,5)?(3,3)?(4,1)?(5,6)?(6,8)?(7,2)?(8,4)
(1,8)?(2,2)?(3,4)?(4,1)?(5,7)?(6,5)?(7,3)?(8,6)
(1,8)?(2,2)?(3,5)?(4,3)?(5,1)?(6,7)?(7,4)?(8,6)
(1,8)?(2,3)?(3,1)?(4,6)?(5,2)?(6,5)?(7,7)?(8,4)
(1,8)?(2,4)?(3,1)?(4,3)?(5,6)?(6,2)?(7,7)?(8,5)
92?states?available!