九宫幻方（DFS实现）c++

题目描述

题目分析

要完成这个问题，我们需要做这几步

1.用1~9的数字替换掉输入中的0，且幻方中不能出现重复元素

2.替换完成后，要判断是否为幻方

判断是否为幻方

bool check()//检查是否为幻方 
{
	int sum=a[1][1]+a[2][2]+a[3][3];//左对角线的和 
	if(sum!=a[1][3]+a[2][2]+a[3][1])	return false;//判断右对角线的和 
	for(int i=1;i<=3;i++)
	{
		int tmp1=0,tmp2=0;
		for(int j=1;j<=3;j++)	
		{
			tmp1+=a[i][j];//计算一行的和 
			tmp2+=a[j][i];//计算一列的和 
		}
		if(tmp1!=sum||tmp2!=sum)	return false;
	}
	return true;
}

用dfs方法替换0元素

void dfs(int now)
{
	if(now>n)
	{
		if(check())
		{
			cnt++;//如果是幻方，数量＋1 
			for(int i=1;i<=3;i++)//将该矩阵复制到ans矩阵中 
				for(int j=1;j<=3;j++)
					ans[i][j]=a[i][j];
		}
		return;
	}
	int x=p[now].first,y=p[now].second;//根据当前的now索引，从p数组中获取对应的坐标(x, y)，这是下一个要填入的数字的位置
	for(int k=1;k<=9;k++)
	{
		if(vis[k])	continue;//如果数字k已经被使用过（即vis[k]为1），则跳过该次循环 
		a[x][y]=k;//在位置(x, y)填入数字k
		vis[k]=1;//标记k，说明其已经使用过 
		dfs(now+1);//递归调用dfs 
		a[x][y]=0;//回溯，将位置(x, y)的数字重新设置为0
		vis[k]=0;//回溯，标记数字k为未使用
	}
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int vis[10],a[5][5],ans[5][5];
int n,cnt;
pair<int,int>p[10];
bool check()//检查是否为幻方 
{
	int sum=a[1][1]+a[2][2]+a[3][3];//左对角线的和 
	if(sum!=a[1][3]+a[2][2]+a[3][1])	return false;//判断右对角线的和 
	for(int i=1;i<=3;i++)
	{
		int tmp1=0,tmp2=0;
		for(int j=1;j<=3;j++)	
		{
			tmp1+=a[i][j];//计算一行的和 
			tmp2+=a[j][i];//计算一列的和 
		}
		if(tmp1!=sum||tmp2!=sum)	return false;
	}
	return true;
}

void dfs(int now)
{
	if(now>n)
	{
		if(check())
		{
			cnt++;//如果是幻方，数量＋1 
			for(int i=1;i<=3;i++)//将该矩阵复制到ans矩阵中 
				for(int j=1;j<=3;j++)
					ans[i][j]=a[i][j];
		}
		return;
	}
	int x=p[now].first,y=p[now].second;//根据当前的now索引，从p数组中获取对应的坐标(x, y)，这是下一个要填入的数字的位置
	for(int k=1;k<=9;k++)
	{
		if(vis[k])	continue;//如果数字k已经被使用过（即vis[k]为1），则跳过该次循环 
		a[x][y]=k;//在位置(x, y)填入数字k
		vis[k]=1;//标记k，说明其已经使用过 
		dfs(now+1);//递归调用dfs 
		a[x][y]=0;//回溯，将位置(x, y)的数字重新设置为0
		vis[k]=0;//回溯，标记数字k为未使用
	}
}

signed main()
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==0)	p[++n]=make_pair(i,j);//如果某坐标上的元素为0，就用p数组记录它的坐标
			vis[a[i][j]]=1; //对矩阵中出现过的数打上标记，0也打上标记了，但无所谓，因为幻方要填的数字没有0 
		}
	}
	dfs(1);//开始搜索
	if(cnt==1)//如果幻方的个数为1，直接输出ans矩阵 
	{
		for(int i=1;i<=3;i++)
		{
			for(int j=1;j<=3;j++)
			{
				if(j<=2)	cout<<ans[i][j]<<" "; 	
				else	cout<<ans[i][j]<<endl;
				
			}
			
		} 	
	}
	else	cout<<"Too Many"<<endl;
	return 0;	
}