六角填数(dfs)
程序员文章站
2023-12-23 17:19:51
...
如图【1.png】所示六角形中,填入1~12的数字。使得每条直线上的数字之和都相同。
图中,已经替你填好了3个数字,请你计算星号位置所代表的数字是多少?
题解:参考博客:https://blog.csdn.net/qq_32183461/article/details/50705953(写的很仔细)
代码:
#include<stdio.h>
int a[13]={0},v[13]={0}; //存入数据,判断是否已存在
void dfs(int x);
void judge();
int main()
{
int i;
a[1]=1; //把数据存入数组
a[2]=8;
a[12]=3;
v[1]=1; //如果已填入标记为1
v[8]=1;
v[3]=1;
dfs(1); //从1开始填数
return 0;
}
void dfs(int x)
{
int i,b[6];
if(x==1||x==2||x==12) //如果已经填入则跳到下一步
{
dfs(x+1);
return;
}
if(x==13) //填入最后一步的时候,判断是否平
judge();
for(int i=1;i<13;i++)
{
if(v[i]==0) //如果没有被填入
{
v[i]=1; //标记为已填入
a[x]=i; //赋值
dfs(x+1);//搜索下一步
v[i]=0; //清零
}
}
}
void judge()
{
int i,b[6];
b[0]=a[1]+a[3]+a[6]+a[8]; //和为26
b[1]=a[1]+a[4]+a[7]+a[11];
b[2]=a[8]+a[9]+a[10]+a[11];
b[3]=a[2]+a[3]+a[4]+a[5];
b[4]=a[2]+a[6]+a[9]+a[12];
b[5]=a[5]+a[7]+a[10]+a[12];
for(int i=1;i<6;i++)
if(b[i]!=b[i-1]) //如果不相等继续搜索
return;
//printf("%d\n",a[6]);
for(int i=1;i<13;i++)
printf("%d ",a[i]);
}