于是一个决策就变成了：在这个位置填了一个数，在这一行填了 $k$ ，在这一列填了 $k$ ，在这一宫填了 $k$ 。发现每一个都必须只选一个决策，于是这就是一个精确覆盖问题，可以用 $dancing$ $links$ 求解。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int map[10][10];

const int MAXN = 729 * 324 * 2;

#define INF 0x3f3f3f3f

struct DLX

{

	int n,m,cnt;

	int head;

	int L[MAXN],R[MAXN],U[MAXN],D[MAXN],col[MAXN],row[MAXN];

	int h[MAXN],s[MAXN];

	DLX(){head = 0;}

	int ans[MAXN];

	inline void init(int _n,int _m)

	{

		n = _n;m = _m;

		for(register int i = 0;i <= m;++i)

		{

			R[i] = i + 1;L[i] = i - 1;U[i] = D[i] = i;

		}

		R[m] = 0;

		L[0] = m;

		memset(h,-1,sizeof(h));

		memset(s,0,sizeof(s));

		cnt = m;s[0] = INF;

		return;

	}

	inline void add(int r,int c)

	{

		++cnt;

		++s[c];

		row[cnt] = r;col[cnt] = c;

		U[cnt] = c;D[cnt] = D[c];U[D[c]] = cnt;D[c] = cnt;

		if(h[r] == -1)h[r] = R[cnt] = L[cnt] = cnt;

		else

		{

			R[cnt] = h[r];L[cnt] = L[h[r]];R[L[h[r]]] = cnt;L[h[r]] = cnt;

		}

		return;

	}

	inline void remove(int k)

	{

		R[L[k]] = R[k];L[R[k]] = L[k];

		for(register int i = D[k];i != k;i = D[i])

			for(register int j = R[i];j != i;j = R[j])

				U[D[j]] = U[j],D[U[j]] = D[j],--s[col[j]];

		return;

	}

	inline void resume(int k)

	{

		L[R[k]] = k;R[L[k]] = k;

		for(register int i = U[k];i != k;i = U[i])

			for(register int j = L[i];j != i;j = L[j])

				U[D[j]] = j,D[U[j]] = j,++s[col[j]];

		return;

	}

	bool dance()

	{

		if(R[head] == head)return true;

		int mcol = 0;

		for(int i = R[mcol];i != mcol;i = R[i])

			if(s[i] < s[mcol])

				mcol = i;

		if(D[mcol] == mcol)return false;

		remove(mcol);

		++ans[0];

		for(int i = U[mcol];i != mcol;i = U[i])

		{

			ans[ans[0]] = row[i];

			for(int j = R[i];j != i;j = R[j])remove(col[j]);

			if(dance())return true;

			for(int j = L[i];j != i;j = L[j])resume(col[j]);

		}

		--ans[0];

		resume(mcol);

		return false;

	}

}dlx;

inline int to(int i,int j,int k){return (i - 1) * 81 + (j - 1) * 9 + k;}

inline void insert(int i,int j,int k)

{

	int cur = to(i,j,k);

	dlx.add(cur,81 * 0 + (i - 1) * 9 + j);//(i,j)这个格子已填数

	dlx.add(cur,81 * 1 + (i - 1) * 9 + k);//第i行填了数k

	dlx.add(cur,81 * 2 + (j - 1) * 9 + k);//第j行填了数k

	dlx.add(cur,81 * 3 + ((i - 1) / 3 * 3 + (j - 1) / 3) * 9 + k);//第((i-1)/3*3+(j-1)/3+1)宫填了数k

	return;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	dlx.init(729,324);

	for(int i = 1;i <= 9;++i)

		for(int j = 1;j <= 9;++j)

			map[i][j] = read();

	for(int i = 1;i <= 9;++i)

		for(int j = 1;j <= 9;++j)

			for(int k = 1;k <= 9;++k)

				if(map[i][j] == k || map[i][j] == 0)

					insert(i,j,k);

	dlx.dance();

	for(int i = 1;i <= dlx.ans[0];++i)

		map[(dlx.ans[i] - 1) / 81 + 1][(dlx.ans[i] - 1) % 81 / 9 + 1] = (dlx.ans[i] - 1) % 9 + 1;

	for(int i = 1;i <= 9;++i)

	{

		for(int j = 1;j <= 9;++j)

			printf("%d ",map[i][j]);

		puts("");

	}

	return 0;

}