题目传送门1:
传送门2:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
void read(int &a)
{
a=0;
int d=1;
char ch;
while(ch=getchar(),ch>'9'||ch<'0')
if(ch=='-')
d=-1;
a=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')
a=a*10+ch-'0';
a*=d;
}
void write(int x)
{
if(x<0)
putchar(45),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int a[11][11];
bool r[11][11],l[11][11],g[11][11];
void print()
{
for(re int i=1;i<=9;i++)
{
write(a[i][1]);
for(re int j=2;j<=9;j++)
{
putchar(' ');
write(a[i][j]);
}
putchar('
');
}
exit(0);
}
void dfs(int x,int y)
{
if(a[x][y])
{
if(x==9&&y==9)
print();
else if(y==9)
dfs(x+1,1);
else dfs(x,y+1);
}
else
{
for(re int i=1;i<=9;i++)
{
if(r[x][i]&&l[y][i]&&g[(x-1)/3*3+(y-1)/3+1][i])
{
a[x][y]=i;
r[x][i]=false;
l[y][i]=false;
g[(x-1)/3*3+(y-1)/3+1][i]=false;
if(x==9&&y==9)
print();
else if(y==9)
dfs(x+1,1);
else dfs(x,y+1);
a[x][y]=0;
r[x][i]=true;
l[y][i]=true;
g[(x-1)/3*3+(y-1)/3+1][i]=true;
}
}
}
}
int main()
{
memset(r,true,sizeof(r));
memset(l,true,sizeof(l));
memset(g,true,sizeof(g));
for(re int i=1;i<=9;i++)
for(re int j=1;j<=9;j++)
{
read(a[i][j]);
if(a[i][j])
{
r[i][a[i][j]]=false;
l[j][a[i][j]]=false;
g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=false;
}
}
dfs(1,1);
return 0;
}