LYD蓝书做法整理。位运算优化 165ms 完美通过。如果交到 P10481，可以 4ms AC。

//常数优化
//1.对于每行每列每个九宫格，分别用一个 9 位二进制保存有哪些数能用。
//2.对于每个数字，把它所在的行、列、九宫格的三个二进制数做按位与运算，
//就可以知道该位置可以填哪些数，再用 lowbit 运算就可以将能填的数字取出。
//3.当一个位置上填上某个数后，把该位置所在行、列、九宫格的二进制数对应位改为 0 更新装态，
//回溯时改为 1 还原现场。可以利用异或的性质来省去判断是搜索还是回溯。
//4.用 lowbit 运算预处理每个 9 位二进制数有几位 1 ，即可快速确定能填的合法数字最少的位置。
//5.打表确定用 lowbit 运算取出来的位置对应的数字。例如f['0001']=1，f['0100']=3。
#include <iostream>
#include <cstdio>
using namespace std;

int s[9][9]; // 记录数独题面
int x[9], y[9], z[9]; // 记录每行、每列、每宫的填写情况
// 例如 x[3][0] 为1，表示第3行还能填数字1（=0+1）

const int N = 1 << 9;
int cnt[N], f[N]; // 打表用的
void init() {
	for (int i = 1; i < N; i++) cnt[i] = __builtin_popcount(i); // 优化4
	for (int i = 0; i < 9; i++) f[1 << i] = i + 1; // 优化5
}

inline int gong(int i, int j) {
	return i / 3 * 3 + j / 3;
}

void fill(int i, int j, int v) {
	int t = 1 << v;
	x[i] ^= t;
	y[j] ^= t;
	z[gong(i, j)] ^= t; // 异或，就不用判断是搜索还是回溯在改状态了
}

// rest表示剩下还要填的数的个数
bool dfs(int rest) {
	if (!rest) return true;
	// 优化搜索顺序：寻找能填的合法数字最少的位置。
	// nx、ny记录位置，tmp记录最少个数。
	int nx = 0, ny = 0, min_cnt = 10;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			if (!s[i][j]) {
				int t = x[i] & y[j] & z[gong(i, j)]; // 优化2
				if (cnt[t] < min_cnt)
					nx = i, ny = j, min_cnt = cnt[t];
//				printf("dbg: x=%d y=%d min_cnt=%d\n", nx, ny, min_cnt);
			}
		}
	int t = x[nx] & y[ny] & z[gong(nx, ny)];
	// 可填的数字一个个尝试
	while (t) {
		int now = f[t & -t]; // now就是lowbit(t)这个状态对应的数字
//		printf("dbg: now=%d\n", now);
		s[nx][ny] = now;
		fill(nx, ny, now - 1);
		if (dfs(rest - 1)) return true;
		// 回溯
		s[nx][ny] = 0;
		fill(nx, ny, now - 1); // 撤销上面dfs(rest-1)更深层的递归造成的修改
		t -= (t & -t); // t-=lowbit(t)
	}
	return false;
}

int main() {
	init();

	string str;
	cin >> str;
	while (str != "end") {
		// 注意多测的全局变量设置
		for (int i = 0; i < 9; i++) x[i] = y[i] = z[i] = N - 1; // 优化1
		int tot = 0; // 记录需要填的空的数量
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) {
				char ch = str[i * 9 + j];
				if (ch == '.') s[i][j] = 0;
				else s[i][j] = ch - '0';
				if (s[i][j]) fill(i, j, s[i][j] - 1);
				else tot++;
			}

		if (dfs(tot)) {
			for (int i = 0; i < 9; i++)
				for (int j = 0; j < 9; j++)
					cout << s[i][j];
			cout << '\n';
		}

		cin >> str;
	}
	return 0;
}