今天温习搜索
有题深搜卡了很久，改了一种思路直接AC

数独游戏

题目描述

数独是一种传统益智游戏，你需要把99的数独补充完整，使得图中每行、每列、每个33的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。

输入格式

输入包含多组测试用例。
每个测试用例占一行，包含81个字符，表达数独的81个格内数据（顺序总体由上到下，同行由左到右）。每个字符都是一个数字或一个 .（表示尚未填充）。您可以假设输入中的每一个谜题都只有一个解决方案文件。结尾处包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，表示填充完全后的数独。

样例

样例输入

4…..8.5.3……….7……2…..6…..8.4……1…….6.3.7.5..2…..1.4……
……52..8.4……3…9…5.1…6..2..7……..3…..6…1……….7.4…….3.
end

样例输出

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

最开始代码很有问题就不放了，改了一下直接再次爆掉

#include <bits/stdc++.h>
using namespace std;
string s;
bool h[10][100], l[10][100], g[10][100], d;
void dfs(int t) {
    char i;
    int x = t / 9, y = t % 9, z = x / 3 * 3 + y / 3;
    if (t == 81) {
        cout << s, d = true;
        return;
    }
    if (s[t] == &#039;.&#039;) {
        for (i = &#039;1&#039;; i <= &#039;9&#039;; i++) {
            if (h[x][i] && l[y][i] && g[z][i]) {
                h[x][i] = l[y][i] = g[z][i] = 0, s[t] = i, dfs(t + 1);
                if (d)
                    return;
                h[x][i] = l[y][i] = g[z][i] = 1, s[t] = &#039;.&#039;;
            }
        }
    } else
        dfs(t + 1);
    return;
}
void fi() {
    memset(h, true, sizeof(h)), memset(l, true, sizeof(l)), memset(g, true, sizeof(g));
    return;
}
int main(void) {
    int i;
    for (cin >> s; s != "end"; cin >> s) {
        fi();
        for (d = 0, i = 0; i < 81; i++)
            if (s[i] != &#039;.&#039;)
                h[i / 9][s[i]] = l[i % 9][s[i]] = g[i / 9 / 3 * 3 + i % 9 / 3][s[i]] = 0;
        dfs(0);
    }

    return 0;
}

在我九天九夜的冥思苦想+废寝忘食+头发发白后，终于AC啦
话不多说，直接上代码

#include <bits/stdc++.h>
using namespace std;
string s;
int a[9][9], fx[3][3], fy[9], fz[9];
bool dfs(int K) {
    if (K == 81) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) cout << a[i][j];
        cout << endl;
        return true;
    }
    int x = K / 9, y = K % 9;
    if (a[x][y])
        return dfs(K + 1);
    for (int i = 1; i <= 9; i++) {
        if ((fx[x / 3][y / 3] >> i) & 1)
            continue;
        if ((fy[x] >> i) & 1)
            continue;
        if ((fz[y] >> i) & 1)
            continue;
        fx[x / 3][y / 3] |= (1 << i), fy[x] |= (1 << i), fz[y] |= (1 << i), a[x][y] = i;
        if (dfs(K + 1))
            return true;
        a[x][y] = 0, fx[x / 3][y / 3] ^= (1 << i), fy[x] ^= (1 << i), fz[y] ^= (1 << i);
    }
    return false;
}
int main(void) {
    while (cin >> s && s != "end") {
        memset(a, 0, sizeof(a)), memset(fx, 0, sizeof(fx)), memset(fy, 0, sizeof(fy)),
            memset(fz, 0, sizeof(fz));
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (s[i * 9 + j] != &#039;.&#039;)
                    a[i][j] = s[i * 9 + j] - &#039;0&#039;, fx[i / 3][j / 3] |= (1 << (s[i * 9 + j] - &#039;0&#039;)),
                    fy[i] |= (1 << (s[i * 9 + j] - &#039;0&#039;)), fz[j] |= (1 << (s[i * 9 + j] - &#039;0&#039;));
        dfs(0);
    }
    return 0;
}

差不多就这样
本蒟蒻就到这，明天见