题解：P10482 Sudoku 2

神仙酱 · 2024-06-22 00:35:10 · 题解

借此机会整理一下剪枝相关的技巧，希望读者能从中举一反三（~~不是因为这题题解少所以好通过~~）。此外，我在文末附了一些剪枝相关的好题，可以据本文技巧进行运用和练习。

基本剪枝技巧

考虑一个简单的选数求和问题：从一些给定的、有重复的数 a_1, a_2, \ldots , a_n 中，允许选最少的几个数，使之和为一个定值 s。

1. 搜索顺序优化

在大部分搜索问题中，搜索树并不是完全树，这意味着有的分支浅，有的分支深，而且无论是深的分支还是浅的分支都有可能搜到结果上相同的状态，这启示我们应该先从较浅的分支探索。例如在选数求和问题中，一条可行的经验是，先排序，然后从较大的数开始试。在本题中的优化也是基于此。

2. 重复性剪枝

搜索过程中，如果可以判定几条分支是完全等效的，那么只需要对其中一条分支搜索即可。例如在选数问题中，对于相同的数，一旦判定其中一个不符合要求，那么之后遇到这个数就也可以跳过了。

3. 最优性剪枝

常见于要求最大/最小/最优的搜索问题中，如果当前花费的代价已经大于目前搜到的最优解，那么无论如何都不可能再得到更优的结果，因此应当停止对当前分支的搜索，立刻回溯。例如在选数求和问题中，目前凑出 k 需要最少的数是 3 个，而当前搜索已经用了 3 个数还未能达到 k，那么就可以回溯了。

4. 可行性剪枝

如果发现分支无法到达递归边界，则应当回溯。遇到一个搜索问题，先考虑能否在搜索前通过预处理剪枝，再考虑搜索时如何检查能否到达递归边界。例如在选数求和问题中，如果存在一些数大于 k，那么应当将这些数排除。在搜索时，如果发现当前和已经大于 k 或当前和加上之后数的和仍然小于 k，则应当回溯。

本题

依次审视上述四条剪枝技巧：

搜索顺序优化：在同一状态下，是否存在某些搜索分支比另一些浅？也就是说，我们有很多空要填，那么是否存在一个空，先填它可以让我们更少步数地知道这个填法是否可行？具体而言，假设有两个空，在分别检查完行、列和九宫格之后，它们分别还可以填两个数和五个数，那么先从只能填两个数的空开始搜索是较优的。
重复性剪枝：是否存在某些重复的状态？否，并不存在等效冗余。
最优性剪枝：我们只需要探索是否可行或求出一个解，因此不需要最优性剪枝。
可行性剪枝：怎么判定当前状态还能不能继续搜下去？如果发现这个空所有数都试完了，或者这个空已经没有可填的数了，那么这一定是个不可行的填法，因此需要回溯。

更多实现细节见代码注释。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 9;
using cell_t = bitset<N>;
/*
 使用 bitset 表示已经用掉的数。例如如果已经用了 1，那么bitset[0] = true。
 hor: 同一行已经用掉的数。
 ver: 同一列已经用掉的数。
 square：九宫格内已经用掉的数。
*/
cell_t hor[N], ver[N], square[N];
char str[N][N];
int root;

// cnt：还需要填写多少数
bool dfs(int cnt) {
    if (cnt == 0)
        return true;
    int min_avail = N + 1, x, y;
    cell_t avail{};
    // 找到还能填的数最少的位置
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            if (str[i][j] == '.') {
                int k = i / root * root + j / root;
                avail = ~(hor[i] | ver[j] | square[k]);
                if (avail.count() < min_avail) {
                    min_avail = avail.count();
                    x = i, y = j;
                }
            }
    }
    int k = x / root * root + y / root;
    // 如果 avail[i] 为 true，则意味着 i + 1 还可用。
    avail = ~(hor[x] | ver[y] | square[k]);
    for (int i = 0; i < N; ++i) {
        if (avail[i]) {
            str[x][y] = '1' + i;
            hor[x][i] = ver[y][i] = square[k][i] = true;
            if (dfs(cnt - 1))
                return true;
            str[x][y] = '.';
            hor[x][i] = ver[y][i] = square[k][i] = false;
        }
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    root = sqrt(N);
    string data;
    while (cin >> data, data != "end") {
        memcpy(str, data.c_str(), sizeof str);
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            hor[i].reset(), ver[i].reset(), square[i].reset();
            // 维护该行已经用掉的数。
            for (int j = 0; j < N; ++j)
                if (str[i][j] != '.')
                    hor[i][str[i][j] - '1'] = true;
            cnt += N - hor[i].count();
        }
        // 维护该列已经用掉的数。
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (str[j][i] != '.')
                    ver[i][str[j][i] - '1'] = true;
    // 维护每一个九宫格已经用掉的数。
        for (int i = 0, idx = 0; i < N; i += root)
            for (int j = 0; j < N; j += root, ++idx)
                for (int k = 0; k < root; ++k)
                    for (int l = 0; l < root; ++l)
                        if (str[i + k][j + l] != '.')
                            square[idx][str[i + k][j + l] - '1'] = true;
        dfs(cnt);
        for (int i = 0; i < N; ++i)
            copy_n(str[i], N, ostream_iterator<char>(cout));
        cout << "\n";
    }
    return 0;
}