解题思路

由于数独最多只有 $81$ 个格子，所以可以用暴搜。

考虑定义三个数组，分别维护行，列，每个 $3×3$ 的方格里有哪几个数字出先过。在输入的时候就可以先预处理好已经填好的，其余在搜索里改变。

搜索时可以从上往下搜，从左往右搜，再用一个 $flag$ 记录有没有找到答案，然后枚举每一个格子能填哪个数，搜到最后直接输出。

注意有多组测试用例，然后要输出空格！！！

解题代码

#include <bits/stdc++.h>
using namespace std;

int a[10][10], t;
bool row[10][10], line[10][10], G[10][10], flag = 0; 

int m[10][10] = { 
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};

void init()
{
	memset(row, 0, sizeof(row));
	memset(line, 0, sizeof(line));
	memset(G, 0, sizeof(G));
	memset(a, 0, sizeof(a));
	flag = 0;
}

void dfs(int x, int y)
{
	if (flag) return;
	if (y == 9)
	{
		dfs(x + 1, 1);
		return;
	}
	if (a[x][y] != 0)
	{
		dfs(x, y + 1);
		return;
	}
	if (x > 9)
	{
		for (int i = 1; i <= 9; i++)
		{
			for (int j = 1; j <= 9; j++)
			{
				cout << a[i][j];
			}
			cout << endl;
		}
		flag = 1;
		return;
	}
	for (int k = 1; k <= 9; k++)
	{
		if (row[x][k] || line[y][k] || G[m[x][y]][k]) continue;
		row[x][k] = line[y][k] = G[m[x][y]][k] = 1;
		a[x][y] = k;
		dfs(x, y + 1);
		row[x][k] = line[y][k] = G[m[x][y]][k] = 0;
		a[x][y] = 0;
	}
}

int main()
{
	cin >> t; 
	while (t--)
	{
		init();
		for (int i = 1; i <= 9; i++)
		{
			for (int j = 1; j <= 9; j++)
			{
				char c;
				cin >> c;
				a[i][j] = c - '0';
				if (!a[i][j]) continue;
		    	row[i][a[i][j]] = true;
		    	line[j][a[i][j]] = true;
		    	G[m[i][j]][a[i][j]] = true;
			}
		}
		dfs(1, 1);
	}
	return 0;
}