8皇后问题

发布网友发布时间：2022-04-10 23:30

共1个回答

热心网友时间：2022-04-11 00:59

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int sum=0;/*记录方案的个数*/

int Place(int k,int *x)
/*判断新加入的皇后所在的位置 k 是否与其他皇后的位置冲突，此函数用来作为是否进行剪枝的判断条件*/
{
int j;
for(j=1;j<k;j++)
if( (abs(k-j) == abs(x[j]-x[k])) || (x[j]==x[k]) )/*x[i]表示皇后 i 放在棋盘的第 i 行的第x[i]列*/
return 0;/*能攻击到其他皇后，返回 0 */
return 1;/*不能攻击到其他皇后，返回 1 */
}

void Backtrack(int t,int n,int *x)
/*递归回溯求解*/
{
int i;
if(t>n)
{
sum++;
/*输出一个方案*/
printf("方案%d：",sum);
for(i=1;i<=n;i++)
printf("(%d,%d) ",i,x[i]);
printf("\n");
}
else
for(i=1;i<=n;i++)
{
x[t]=i;
if(Place(t,x)) Backtrack(t+1,n,x);/*如果新加入第t个皇后所在的位置 i 没有与其他皇后的位置冲突，则进入解空间子树，试探第t+1个皇后的位置；否则不进入子树，舍弃该段子树，即进行剪枝*/
}
}

main()
{
int n,*x;
int i;
printf("请输入皇后的个数：");
scanf("%d",&n);
x=(int *)malloc((n+1)*sizeof(int));/*x[0]未使用*/
printf("以下每个方案都表示出了%d个皇后在棋盘上的坐标\n\n",n);
Backtrack(1,n,x);/*求解*/
printf("总共有%d种方案\n",sum);
}

请输入皇后的个数：8
以下每个方案都表示出了8个皇后在棋盘上的坐标

方案1：(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)
方案2：(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)
方案3：(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)
方案4：(1,1) (2,7) (3,5) (4,8) (5,2) (6,4) (7,6) (8,3)
方案5：(1,2) (2,4) (3,6) (4,8) (5,3) (6,1) (7,7) (8,5)
方案6：(1,2) (2,5) (3,7) (4,1) (5,3) (6,8) (7,6) (8,4)
方案7：(1,2) (2,5) (3,7) (4,4) (5,1) (6,8) (7,6) (8,3)
方案8：(1,2) (2,6) (3,1) (4,7) (5,4) (6,8) (7,3) (8,5)
方案9：(1,2) (2,6) (3,8) (4,3) (5,1) (6,4) (7,7) (8,5)
方案10：(1,2) (2,7) (3,3) (4,6) (5,8) (6,5) (7,1) (8,4)
方案11：(1,2) (2,7) (3,5) (4,8) (5,1) (6,4) (7,6) (8,3)
方案12：(1,2) (2,8) (3,6) (4,1) (5,3) (6,5) (7,7) (8,4)
方案13：(1,3) (2,1) (3,7) (4,5) (5,8) (6,2) (7,4) (8,6)
方案14：(1,3) (2,5) (3,2) (4,8) (5,1) (6,7) (7,4) (8,6)
方案15：(1,3) (2,5) (3,2) (4,8) (5,6) (6,4) (7,7) (8,1)
方案16：(1,3) (2,5) (3,7) (4,1) (5,4) (6,2) (7,8) (8,6)
方案17：(1,3) (2,5) (3,8) (4,4) (5,1) (6,7) (7,2) (8,6)
方案18：(1,3) (2,6) (3,2) (4,5) (5,8) (6,1) (7,7) (8,4)
方案19：(1,3) (2,6) (3,2) (4,7) (5,1) (6,4) (7,8) (8,5)
方案20：(1,3) (2,6) (3,2) (4,7) (5,5) (6,1) (7,8) (8,4)
方案21：(1,3) (2,6) (3,4) (4,1) (5,8) (6,5) (7,7) (8,2)
方案22：(1,3) (2,6) (3,4) (4,2) (5,8) (6,5) (7,7) (8,1)
方案23：(1,3) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,2)
方案24：(1,3) (2,6) (3,8) (4,1) (5,5) (6,7) (7,2) (8,4)
方案25：(1,3) (2,6) (3,8) (4,2) (5,4) (6,1) (7,7) (8,5)
方案26：(1,3) (2,7) (3,2) (4,8) (5,5) (6,1) (7,4) (8,6)
方案27：(1,3) (2,7) (3,2) (4,8) (5,6) (6,4) (7,1) (8,5)
方案28：(1,3) (2,8) (3,4) (4,7) (5,1) (6,6) (7,2) (8,5)
方案29：(1,4) (2,1) (3,5) (4,8) (5,2) (6,7) (7,3) (8,6)
方案30：(1,4) (2,1) (3,5) (4,8) (5,6) (6,3) (7,7) (8,2)
方案31：(1,4) (2,2) (3,5) (4,8) (5,6) (6,1) (7,3) (8,7)
方案32：(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,1) (8,5)
方案33：(1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,5) (8,1)
方案34：(1,4) (2,2) (3,7) (4,5) (5,1) (6,8) (7,6) (8,3)
方案35：(1,4) (2,2) (3,8) (4,5) (5,7) (6,1) (7,3) (8,6)
方案36：(1,4) (2,2) (3,8) (4,6) (5,1) (6,3) (7,5) (8,7)
方案37：(1,4) (2,6) (3,1) (4,5) (5,2) (6,8) (7,3) (8,7)
方案38：(1,4) (2,6) (3,8) (4,2) (5,7) (6,1) (7,3) (8,5)
方案39：(1,4) (2,6) (3,8) (4,3) (5,1) (6,7) (7,5) (8,2)
方案40：(1,4) (2,7) (3,1) (4,8) (5,5) (6,2) (7,6) (8,3)
方案41：(1,4) (2,7) (3,3) (4,8) (5,2) (6,5) (7,1) (8,6)
方案42：(1,4) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3) (8,8)
方案43：(1,4) (2,7) (3,5) (4,3) (5,1) (6,6) (7,8) (8,2)
方案44：(1,4) (2,8) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
方案45：(1,4) (2,8) (3,1) (4,5) (5,7) (6,2) (7,6) (8,3)
方案46：(1,4) (2,8) (3,5) (4,3) (5,1) (6,7) (7,2) (8,6)
方案47：(1,5) (2,1) (3,4) (4,6) (5,8) (6,2) (7,7) (8,3)
方案48：(1,5) (2,1) (3,8) (4,4) (5,2) (6,7) (7,3) (8,6)
方案49：(1,5) (2,1) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)
方案50：(1,5) (2,2) (3,4) (4,6) (5,8) (6,3) (7,1) (8,7)
方案51：(1,5) (2,2) (3,4) (4,7) (5,3) (6,8) (7,6) (8,1)
方案52：(1,5) (2,2) (3,6) (4,1) (5,7) (6,4) (7,8) (8,3)
方案53：(1,5) (2,2) (3,8) (4,1) (5,4) (6,7) (7,3) (8,6)
方案54：(1,5) (2,3) (3,1) (4,6) (5,8) (6,2) (7,4) (8,7)
方案55：(1,5) (2,3) (3,1) (4,7) (5,2) (6,8) (7,6) (8,4)
方案56：(1,5) (2,3) (3,8) (4,4) (5,7) (6,1) (7,6) (8,2)
方案57：(1,5) (2,7) (3,1) (4,3) (5,8) (6,6) (7,4) (8,2)
方案58：(1,5) (2,7) (3,1) (4,4) (5,2) (6,8) (7,6) (8,3)
方案59：(1,5) (2,7) (3,2) (4,4) (5,8) (6,1) (7,3) (8,6)
方案60：(1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,4) (8,8)
方案61：(1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,8) (8,4)
方案62：(1,5) (2,7) (3,4) (4,1) (5,3) (6,8) (7,6) (8,2)
方案63：(1,5) (2,8) (3,4) (4,1) (5,3) (6,6) (7,2) (8,7)
方案64：(1,5) (2,8) (3,4) (4,1) (5,7) (6,2) (7,6) (8,3)
方案65：(1,6) (2,1) (3,5) (4,2) (5,8) (6,3) (7,7) (8,4)
方案66：(1,6) (2,2) (3,7) (4,1) (5,3) (6,5) (7,8) (8,4)
方案67：(1,6) (2,2) (3,7) (4,1) (5,4) (6,8) (7,5) (8,3)
方案68：(1,6) (2,3) (3,1) (4,7) (5,5) (6,8) (7,2) (8,4)
方案69：(1,6) (2,3) (3,1) (4,8) (5,4) (6,2) (7,7) (8,5)
方案70：(1,6) (2,3) (3,1) (4,8) (5,5) (6,2) (7,4) (8,7)
方案71：(1,6) (2,3) (3,5) (4,7) (5,1) (6,4) (7,2) (8,8)
方案72：(1,6) (2,3) (3,5) (4,8) (5,1) (6,4) (7,2) (8,7)
方案73：(1,6) (2,3) (3,7) (4,2) (5,4) (6,8) (7,1) (8,5)
方案74：(1,6) (2,3) (3,7) (4,2) (5,8) (6,5) (7,1) (8,4)
方案75：(1,6) (2,3) (3,7) (4,4) (5,1) (6,8) (7,2) (8,5)
方案76：(1,6) (2,4) (3,1) (4,5) (5,8) (6,2) (7,7) (8,3)
方案77：(1,6) (2,4) (3,2) (4,8) (5,5) (6,7) (7,1) (8,3)
方案78：(1,6) (2,4) (3,7) (4,1) (5,3) (6,5) (7,2) (8,8)
方案79：(1,6) (2,4) (3,7) (4,1) (5,8) (6,2) (7,5) (8,3)
方案80：(1,6) (2,8) (3,2) (4,4) (5,1) (6,7) (7,5) (8,3)
方案81：(1,7) (2,1) (3,3) (4,8) (5,6) (6,4) (7,2) (8,5)
方案82：(1,7) (2,2) (3,4) (4,1) (5,8) (6,5) (7,3) (8,6)
方案83：(1,7) (2,2) (3,6) (4,3) (5,1) (6,4) (7,8) (8,5)
方案84：(1,7) (2,3) (3,1) (4,6) (5,8) (6,5) (7,2) (8,4)
方案85：(1,7) (2,3) (3,8) (4,2) (5,5) (6,1) (7,6) (8,4)
方案86：(1,7) (2,4) (3,2) (4,5) (5,8) (6,1) (7,3) (8,6)
方案87：(1,7) (2,4) (3,2) (4,8) (5,6) (6,1) (7,3) (8,5)
方案88：(1,7) (2,5) (3,3) (4,1) (5,6) (6,8) (7,2) (8,4)
方案89：(1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6)
方案90：(1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6)
方案91：(1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4)
方案92：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
总共有92种方案
请按任意键继续. . .