|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 10;
|
|
|
int g[N][N]; // 棋盘
|
|
|
// 行，列，九宫格分别用的状态压缩桶
|
|
|
// 索引：行，列，九宫格是0~8的索引
|
|
|
// 内容值：1~9位，状态压缩,0位没有用，不用管它。
|
|
|
int r[N], c[N], w[N];
|
|
|
bool flag; // 是不是搜索到了第一个答案，如果是，则让其它搜索快速返回，剪一下枝
|
|
|
|
|
|
// 返回九宫格的编号
|
|
|
int get(int x, int y) {
|
|
|
x /= 3, y /= 3; // 注意两个都是/3，表示是第几个小方块，可以理解为0~8，共9个小方块
|
|
|
return x * 3 + y; // 通过上面的变换，映射到0~8数字上
|
|
|
}
|
|
|
|
|
|
// x,y这个坐标开始暴搜
|
|
|
// cnt:还有多少个点需要填充
|
|
|
void dfs(int x, int y, int cnt) {
|
|
|
if (flag) return; // 快速返回，剪枝
|
|
|
if (cnt == 0) { // 没有空格子了
|
|
|
// 输出答案
|
|
|
for (int i = 0; i < 9; i++)
|
|
|
for (int j = 0; j < 9; j++)
|
|
|
cout << g[i][j];
|
|
|
cout << endl;
|
|
|
// 修改第一次完成的标识
|
|
|
flag = true;
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int nx = x, ny = y + 1; // 下一个位置,默认是向右
|
|
|
if (ny == 9) nx++, ny = 0; // 越界了就从下一行开始
|
|
|
|
|
|
if (g[x][y] == 0) { // 如果此位置是空白
|
|
|
int u = get(x, y); // 这是第几号九宫格
|
|
|
for (int i = 1; i <= 9; i++) { // 尝试填充1~9
|
|
|
if (r[x] >> i & 1) continue;
|
|
|
if (c[y] >> i & 1) continue;
|
|
|
if (w[u] >> i & 1) continue;
|
|
|
// 修改状态，修改棋盘
|
|
|
r[x] += 1 << i, c[y] += 1 << i, w[u] += 1 << i, g[x][y] = i;
|
|
|
// 尝试下一个位置
|
|
|
dfs(nx, ny, cnt - 1);
|
|
|
// 恢复状态
|
|
|
r[x] -= 1 << i, c[y] -= 1 << i, w[u] -= 1 << i, g[x][y] = 0;
|
|
|
}
|
|
|
} else // 如果此位置不是空白，那么就尝试下一个位置
|
|
|
dfs(nx, ny, cnt);
|
|
|
}
|
|
|
int main() {
|
|
|
string str; // 输入的棋盘
|
|
|
while (cin >> str && str[0] != 'e') {
|
|
|
// 初始化
|
|
|
memset(g, 0, sizeof g); // 清空地图
|
|
|
memset(r, 0, sizeof r); // 清空行的标识
|
|
|
memset(c, 0, sizeof c); // 清空列的标识
|
|
|
memset(w, 0, sizeof w); // 清空9个小方块的标识
|
|
|
// 找到第一个方案的停止标识
|
|
|
flag = false;
|
|
|
|
|
|
// 记录需要填充的空位数量
|
|
|
int cnt = 0;
|
|
|
for (int i = 0; i < str.size(); i++) {
|
|
|
if (str[i] == '.') {
|
|
|
cnt++;
|
|
|
continue;
|
|
|
}
|
|
|
// 转换为行列坐标
|
|
|
int x = i / 9, y = i % 9; // x:行，y:列
|
|
|
int u = get(x, y); // 0~8哪个九宫格
|
|
|
g[x][y] = str[i] - '0'; // 棋盘上放上数字
|
|
|
r[x] += 1 << g[x][y]; // 本质上是一个状态压缩，用二进制方式描述 x行上 g[x][y]这个数字的占用情况，1表示已使用，0表示未使用
|
|
|
c[y] += 1 << g[x][y]; // 列也用状态压缩描述
|
|
|
w[u] += 1 << g[x][y]; // 九宫格也用状态压缩描述
|
|
|
}
|
|
|
// 从左上角暴搜,cnt描述还有多少个位置需要搜索，当cnt==0时停止
|
|
|
dfs(0, 0, cnt);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
