分析
直接dfs估计也行,由于数很少,当根据已给数据推理后,发现:
- 中间的5是必然的
- 其余位置只要有一个数,根据中心对称比然有另一数可以取到
- 按上述推理补全后,仍然有六个以上的空,必然多于一种情况
- 剩下的都是一种,dfs后输出即可
C++ 10ms
#include<iostream>
#include<cstring>
#include<algorithm>
#define ffor(i,s,e) for(int i=s;i<e;i++)
using namespace std;
int a[3][3];
int t[3][3];//存储第一个可行方案
int used[10];//记录已使用的数字
int maxLev;//0的个数也是递归的最大层数
int sols;//方案数
bool check(){//检查合法方案
bool ans=true;
ffor(i,0,3)
ans=ans&&(a[i][0]+a[i][1]+a[i][2]==15)&&(a[0][i]+a[1][i]+a[2][i]==15);
int xie1=a[0][0]+a[1][1]+a[2][2];
int xie2=a[2][0]+a[1][1]+a[0][2];
return ans&&(xie1==15)&&(xie2=15);
}
bool notSame(){//和首个方案不同
bool ans=true;
ffor(i,0,3) ffor(j,0,3){
ans=ans&&(t[i][j]!=a[i][j]);
if(!ans) break;
}
return ans;
}
void dfs(int lev){
if(!lev){//0的位置填完了
if(check()&¬Same()){//新的方案
sols++;
if(sols==1){
ffor(i,0,3) ffor(j,0,3) t[i][j]=a[i][j];
}
}
return;
}
ffor(i,1,10){//枚举未使用的数字
if(!used[i]){
ffor(t,0,3) ffor(k,0,3){
if(!a[t][k]){//找到0的位置
used[i]=1;
a[t][k]=i;
dfs(lev-1);
a[t][k]=0;//恢复现场
used[i]=0;
break;
}
}
}
}
}
void init();//由已知数据填写必然结果
int main(){
init();
if(maxLev==0){//没有要填的位置
ffor(i,0,3){
ffor(j,0,3) cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}
if(maxLev>=6){//推理完后,仍然有六个空,必然大于一种方案
puts("Too Many");
}else {
dfs(maxLev);
ffor(i,0,3){
ffor(j,0,3) cout<<t[i][j]<<" ";
cout<<endl;
}
}
return 0;
}
void init(){
ffor(i,0,3) ffor(j,0,3){
cin>>a[i][j];
}
//补全中心
a[1][1]=5;
// 行、列、对角出现两个的,零位置可以直接补上
bool hasChang;//当前扫描是否有更新
do{
hasChang=false;
ffor(i,0,3) ffor(j,0,3){
if(!a[i][j]){
// 行上只有一个零
int cnt=0,sum=0;
ffor(t,0,3){
if(a[i][t]){
cnt++;
sum+=a[i][t];
}
}
if(cnt>1){
a[i][j]=15-sum;
hasChang=true;
continue;//已补齐当前0,继续搜索下一个
}
// 列上只有一个零
cnt=0,sum=0;
ffor(t,0,3){
if(a[t][j]){
cnt++;
sum+=a[t][j];
}
}
if(cnt>1){
a[i][j]=15-sum;
hasChang=true;continue;
}
//对角的情况,中间5固定了,有一个另一个一定知道
if(i==0&&j==0){
if(a[2][2]){
a[i][j]=10-a[2][2];
hasChang=true;continue;
}
}
if(i==2&&j==2){
if(a[0][0]){
a[i][j]=10-a[0][0];
hasChang=true;continue;
}
}
if(i==0&&j==2){
if(a[2][0]){
a[i][j]=10-a[2][0];
hasChang=true;continue;
}
}
if(i==2&&j==0){
if(a[0][2]) {
a[i][j]=10-a[0][2];
hasChang=true;continue;
}
}
}
}
}while(hasChang);
ffor(i,0,3) ffor(j,0,3){
if(a[i][j]){
maxLev++;//已经标记的
used[a[i][j]]=1;
}
}
maxLev=9-maxLev;//0的个数,即递归的最大层数
}
tql