Question

求教C语言回溯法写出八皇后问题的92种解

最好用简单容易理解的方法写出来，我是菜鸟，如果可以，最好加上注释，，虽然有点难度，但希望高手能教教

Answer 1

(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!

Answer 2

#include<stdio.h>
#include<stdlib.h>
#define Max 8
int queen[Max],sum=0;
void show()
{
    int i;
    printf("(");
    for (i = 0; i < Max; i++)
    {
        printf("%3d", queen[i] + 1);
    }
    printf(")\n");
    ++sum;
}
int PLACE(int n)	//阻止Max个皇后在同一列和同一对角线上
{
    int i;
    for (i = 0; i < n; i++)
    {
        if ((queen[i] == queen[n]) || (abs(queen[i] - queen[n]) == abs(i - n)))
        {
            return 0;
        }
    }
    return 1;
}
void NQUEENS(int n)    
{
    int i;
    for (i = 0; i < Max; i++)
    {
        queen[n] = i;
        if (PLACE(n))
        {
            if (n == Max - 1)
            {
                show();
            }
            else
            {
                NQUEENS(n + 1);
            }
        }
    }
}
int main(void)
{
    NQUEENS(0);
    printf("%d皇后问题共有%d种情况\n", Max, sum);
    system("pause");
    return 1;
}