和蓝桥杯以前一个题一样，但是数据加强了，博主水平有限，没做出来，先在这里记录一下，这里正解，下面是博主的超时做法。最近准备考研，不能深入学习了。
题目描述
数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词“end”的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
样例
输入样例：
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int m[10][10],kx[10][10],ky[10][10],kk[10][10]; //kx：行 ky：列 kk：方格
int ans;
void dfs(int x, int y) {
if (ans)return;
if (x == 9) {
ans = 1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << m[i][j];
}
cout << "
";
}
if (m[x][y] == 0) {
for (int i = 1; i < 10; i++) {
if (kx[x][i]==0&&ky[y][i]==0&& kk[3 * (x / 3) + (y / 3)][i]==0) {
kx[x][i] = 1;
ky[y][i] = 1;
kk[3 * (x/3) + (y/3)][i] = 1;
m[x][y] = i;
if (y == 8)dfs(x + 1,0);
else dfs(x, y + 1);
kx[x][i] = 0;
ky[y][i] = 0;
kk[3 * (x / 3) + (y / 3)][i] = 0;
m[x][y] = 0;
}
}
return;
}
else {
if (y == 8)dfs(x + 1, 1);
else dfs(x, y + 1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
string a;
while (cin >> a&&a[0] != 'e') {
memset(m, 0, sizeof(m));
memset(kx, 0, sizeof(kx));
memset(ky, 0, sizeof(ky));
memset(kk, 0, sizeof(kk));
ans = 0;
int len = a.size();
for (int i = 0; i < len; i++)
{
if (a[i] != '.') {
m[i / 9][i % 9] = a[i] - '0'; //终于把地图做好了。。
kx[i / 9][a[i] - '0'] = 1;
ky[i % 9][a[i] - '0'] = 1;
kk[3 * (i / 9 / 3) + (i % 9 / 3)][a[i] - '0'] = 1; //初始化
}
}
dfs(0, 0);
}
return 0;
}