当前位置:首页 > 精彩小资讯 > 正文

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

提起回溯法求解婚配问题c语言,大家都知道,有人问求教C语言回溯法写出八皇后问题的92种解,另外,还有人想问C语言编程,用回溯法解四皇后问题,你知道这是怎么回事?其实求给这个程序做个详细的注释C语言回溯法任…,下面就一起来看看求教C语言回溯法写出八皇后问题的92种解,希望能够帮助到大家!

回溯法求解婚配问题c语言

1、回溯法求解婚配问题c语言:求教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种。

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

(2)8皇后(或者n皇后)

保证8个皇后不能互相攻击,即保证每一横行、每一竖行、每一斜行最多一个皇后。

我们撇开第三个条件,如果每一横行、每一竖行都只有一个皇后。

将88棋盘标上坐标。我们讨论其中的一种解法:

——-Q

—Q—-

Q——-

–Q—–

—–Q–

-Q——

——Q-

求给这个程序做个详细的注释C语言回溯法任…

—-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

#include

#include

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

以上就是与求教C语言回溯法写出八皇后问题的92种解相关内容,是关于求教C语言回溯法写出八皇后问题的92种解的分享。看完回溯法求解婚配问题c语言后,希望这对大家有所帮助!

最新文章