#include <iostream>
using namespace std;

bool row[10][10],col[10][10],sqr[10][10];
int a[10][10];
char c[9][10];
bool solve()
{
	int i,j,k;
	for (i = 1; i < 10; ++i)
		for (j = 1; j < 10; ++j)
		{
			if (a[i][j] == 0)
			{
				for (k = 1; k < 10; ++k)
				{
					if (!row[i][k] && !col[j][k] && !sqr[(i-1)/3*3+(j-1)/3+1][k])
					{
						a[i][j] = k;
						row[i][k] = true;
						col[j][k] = true;
						sqr[(i-1)/3*3+(j-1)/3+1][k] = true;
						if (solve())
							return true;
						else
						{
							a[i][j] = 0;
							row[i][k] = false;
							col[j][k] = false;
							sqr[(i-1)/3*3+(j-1)/3+1][k] = false;
						}
					}
				}
				if (k == 10)
					return false;
			}
		}
		return true;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int i,j;
		memset(row,false,sizeof(row));
		memset(col,false,sizeof(col));
		memset(sqr,false,sizeof(sqr));
		getchar();
		for (i = 0; i < 9; ++i)
			cin >> c[i];
		for (i = 1; i < 10; ++i)
		{
			for (j = 1; j < 10; ++j)
			{
				
				a[i][j] = c[i-1][j-1] - '0';
				row[i][a[i][j]] = true;
				col[j][a[i][j]] = true;
				sqr[(i-1)/3*3+(j-1)/3+1][a[i][j]] = true;
			}
		}
		solve();
		for (i = 1; i < 10; ++i)
		{
			for (j = 1; j < 10; ++j)
				cout << a[i][j];
			cout << endl;
		}
	}
	return 0;
}

• Re:正着搜也过了，不过时间多了点 (2799) OSJake 2009-06-15 23:23:14