#include<iostream>
#include<cstdio>
#include<vector>
#define N 11
#define M 236200                       
using namespace std;
int head,cnt;
int g[N][N],u[M],d[M],l[M],r[M],row[M],col[M],num[330],ans[730];
vector<int> v[730];
void Init()
{
	for(int i=0;i<=324;++i)
	{
		u[i]=i;
		d[i]=i;
		l[i]=i-1;
		r[i]=i+1;
	}
	l[head]=324;
	r[324]=head;
	cnt=325;
}
void Addrow(int x)
{
    int first=cnt;
    for(int i=0;i<v[x].size();++i)
    {
        int j=v[x][i];
        u[cnt]=u[j];
        d[u[j]]=cnt;
        u[j]=cnt;
        d[cnt]=j;
        l[cnt]=cnt-1;
        r[cnt]=cnt+1;
        col[cnt]=j;
        row[cnt]=x;
        ++num[j];
        ++cnt;
    }
    l[first]=cnt-1;
    r[cnt-1]=first;
}
void Remove(int x)
{
    r[l[x]]=r[x];
    l[r[x]]=l[x];
    for(int i=d[x];i!=x;i=d[i])
        for(int j=r[i];j!=i;j=r[j])
        {
            u[d[j]]=u[j];
            d[u[j]]=d[j];
            --num[col[j]];
        }
}
void Restore(int x)
{
    for(int i=u[x];i!=x;i=u[i])
        for(int j=l[i];j!=i;j=l[j])
        {
            d[u[j]]=j;
            u[d[j]]=j;
            ++num[col[j]];
        }
    r[l[x]]=x;
    l[r[x]]=x;
}
bool Dance(int dep)
{
    if(r[head]==head)
    {//cout<<"sdadad\n";
    	int x,y,z;
    	for(int i=0;i<dep;++i)
    	{
    		x=(ans[i]-1)/9/9;
    		y=(ans[i]-1)/9%9;
    		z=ans[i]%9;
    		z=z==0?9:z;
    		g[x][y]=z;
		}
    	return 1;
	}  
	
    int now=r[head];
    for(int i=r[head];i!=head;i=r[i])
        if(num[i]<num[now])
            now=i;
    Remove(now);
    for(int i=d[now];i!=now;i=d[i])
    {
    	ans[dep]=row[i];
        for(int j=r[i];j!=i;j=r[j])
            Remove(col[j]);
        if(Dance(dep+1))
            return 1;
        for(int j=l[i];j!=i;j=l[j])
            Restore(col[j]);
    }
    Restore(now);
    return 0;
}
int main()
{
	Init();
	for(int i=0;i<9;++i)
		for(int j=0;j<9;++j)
		{
			scanf("%d",&g[i][j]);	
			for(int k=1;k<=9;++k)
			{
				if(g[i][j]!=k&&g[i][j])
					continue;
				int x=i*9*9+j*9+k;//cout<<x<<"\n";
				v[x].push_back(i*9+j+1);
				v[x].push_back(i*9+81+k);
				v[x].push_back(i*9+81*2+k);
				v[x].push_back(81*3+(i/3*3+j/3)*9+k);
				Addrow(x);
			}
		}
	Dance(0);
	for(int i=0;i<9;++i)
	{
		for(int j=0;j<9;++j)
			printf("%d ",g[i][j]);
		printf("\n");	
	}
	return 0;
			
}

样例输入：

8 0 0 0 0 0 0 0 0 
0 0 3 6 0 0 0 0 0 
0 7 0 0 9 0 2 0 0 
0 5 0 0 0 7 0 0 0 
0 0 0 0 4 5 7 0 0 
0 0 0 1 0 0 0 3 0 
0 0 1 0 0 0 0 6 8 
0 0 8 5 0 0 0 1 0 
0 9 0 0 0 0 4 0 0

样例输出：

8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

我惨不忍睹的输出：

8 6 2 1 4 7 3 5 9
5 9 3 6 2 8 1 4 7
1 7 4 3 9 5 2 6 8
6 5 1 3 2 7 4 8 9
3 8 9 6 4 5 7 2 1
7 4 2 1 8 9 5 3 6
5 2 1 4 7 9 3 6 8
4 3 8 5 2 6 7 1 9
6 9 7 1 3 8 4 5 2

求助$QAQ$