通过回溯算法对未输入得数字进行全排列后,依次填入格子,判断是否符合条件。
可以更改幻方的大小,来填充任意幻方
#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
int board[3][3];//保存输入的幻方
int ans[3][3][3];//填充后符合条件的幻方
int tmp[3][3];//幻方高度,(多少个答案)
bool vist[9]={0};//临时变量来保存幻方,不能让输入的幻方board变化
int anstop=0;//记录该数字是否已填充
int nums[10];//保存输入幻方没有的数字
int N=0;//记录nums的元素个数
int path[10];//记录回溯元素
int pathtop=0;//回溯数组path的元素个数
void check()//判断填充幻方是否符合条件
{
int i,j;
int k=0;
for(i=0;i<3;i++)//填充临时幻方tmp
{
for(j=0;j<3;j++)
{
if(board[i][j]==0)//填充没有输入的数字
tmp[i][j]=path[k++];
else
tmp[i][j]=board[i][j];
}
}
//幻方tmp的3行
int a=tmp[0][0]+tmp[0][1]+tmp[0][2];
int b=tmp[1][0]+tmp[1][1]+tmp[1][2];
int c=tmp[2][0]+tmp[2][1]+tmp[2][2];
//3列
int d=tmp[0][0]+tmp[1][0]+tmp[2][0];
int e=tmp[0][1]+tmp[1][1]+tmp[2][1];
int f=tmp[0][2]+tmp[1][2]+tmp[2][2];
//对角线
int g=tmp[0][0]+tmp[1][1]+tmp[2][2];
int h=tmp[0][2]+tmp[1][1]+tmp[2][0];
if(a==b&&b==c&&c==d&&d==e&&e==f&&f==g&&g==h)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
ans[i][j][anstop]=tmp[i][j];//符合条件,填入记录答案幻方ans
}
}
anstop++;//答案个数++
}
}
void backtracking()
{
if(pathtop==N)//已经把nums的所有元素进行全排列
{
if(anstop>1)//答案个数多余2个,无需往后判断
{
printf("too many");
exit(0);
}
check();//把path中的所有元素填入是否
return;
}
int i;
for(i=0;i<N;i++)//把nums的所有元素进行全排列
{
if(!vist[i])
{
path[pathtop++]=nums[i];
vist[i]=1;
backtracking();
vist[i]=0;
pathtop--;
}
}
}
int main(int argc, char *argv[])
{
int i,j;
int hash[10]={0};
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%d",&board[i][j]);
hash[board[i][j]]++;
}
}
for(i=1;i<10;i++)//记录未输入的数字
{
if(!hash[i])
nums[N++]=i;
}
backtracking();
for(i=0;i<3;i++)//输出答案
{
for(j=0;j<3;j++)
printf("%d ",ans[i][j][0]);
printf("\n");
}
return 0;
}
标签:填充,int,幻方,蓝桥,回溯,path,include,九宫
From: https://blog.csdn.net/m0_73061507/article/details/137376186