仿照 OI Wiki 写了一份，在某些数据上速度较慢。

把第 120 行的 < 改成 <= 就能过 #1，但是会在 #4 TLE。

#include <cstdio>
#include <bitset>
#include <vector>
#include <utility>
#include <map>
#include <iostream>
#include <unordered_set>
#include <cstdint>
#include <cstdlib>
#include <vector>
// numbers used
namespace num { std::bitset<10> row[9], col[9], mat[9]; }
unsigned mat[9][9];
inline unsigned point_to_mat_id(unsigned row, unsigned col) { return (row / 3) * 3 + col / 3; }
unsigned filled = 0;
bool load_matrix() {
    bool ok = true;
    for (unsigned i = 0; i < 9; i++) for (unsigned j = 0; j < 9; j++) if (mat[i][j]) {
        bool ok_this = true;
        num::row[i][mat[i][j]] ? (ok_this = false) : (num::row[i][mat[i][j]] = true);
        num::col[j][mat[i][j]] ? (ok_this = false) : (num::col[j][mat[i][j]] = true);
        num::mat[point_to_mat_id(i, j)][mat[i][j]] ? (ok_this = false) : (num::mat[point_to_mat_id(i, j)][mat[i][j]] = true);
        ok &= ok_this;
        if (ok_this) filled++;
    }
    return ok;
}
void remove() {
    while (true) {
        bool removed = false;
        for (unsigned i = 0; i < 9; i++) for (unsigned j = 0; j < 9; j++) if (!mat[i][j]) {
            std::bitset<10> mask = num::row[i] | num::col[j] | num::mat[point_to_mat_id(i, j)];
            if (mask.count() == 8) {
                for (unsigned _ = 1; _ <= 9; _++) if (!mask[_]) {
                    mat[i][j] = _;
                    break;
                }
                num::row[i][mat[i][j]] = true;
                num::col[j][mat[i][j]] = true;
                num::mat[point_to_mat_id(i, j)][mat[i][j]] = true;
                removed = true;
                ++filled;
            }
        }
        if (!removed) break;
    }
}
struct dlx_node {
    size_t num_row, num_col;
    dlx_node *left, *right, *up, *down;
};
/*
head   col[1] col[2] col[3] ...
row[1]
row[2]
row[3]
...
*/
class dlx {
    dlx_node **col;
    size_t *size_col;
    dlx_node **first;
    size_t num_col;
public:
    dlx() : col(nullptr), size_col(nullptr), first(nullptr), pool(), num_col(0) {}
    dlx(size_t num_row, size_t num_col_) : num_col(num_col_ + 1) {
        col = new dlx_node*[num_col_ + 1];
        size_col = new size_t[num_col_ + 1];
        first = new dlx_node*[num_row + 1];
        for (size_t i = 1; i <= num_col_; i++) col[i] = new dlx_node;
        for (size_t i = 0; i <= num_row; i++) first[i] = nullptr, size_col[i] = 0;
        size_col[0] = 0;
        col[0] = new dlx_node;
        *col[0] = {0, 0, col[num_col_], col[1], col[0], col[0]};
        for (size_t i = 1; i < num_col_; i++) *col[i] = {0, i, col[i - 1], col[i + 1], col[i], col[i]};
        *col[num_col_] = {num_col_, 0, col[num_col_ - 1], col[0], col[num_col_], col[num_col_]};
    }
    void insert(size_t num_row, size_t num_col) {
        dlx_node* tar = new dlx_node{num_row, num_col, nullptr, nullptr, nullptr, nullptr};
        pool[std::make_pair(num_row, num_col)] = tar;
        tar->down = col[num_col]->down;
        tar->up = col[num_col];
        col[num_col]->down->up = tar;
        col[num_col]->down = tar;
        ++size_col[num_col];
        if (!first[num_row]) first[num_row] = tar->left = tar->right = tar;
        else {
            tar->left = first[num_row];
            tar->right = first[num_row]->right;
            first[num_row]->right->left = tar;
            first[num_row]->right = tar;
        }
    }
private:
    std::map<std::pair<size_t, size_t>, dlx_node*> bin;
public:
    void erase(size_t num_col) {
        dlx_node *i, *j;
        (col[num_col]->left->right = col[num_col]->right)->left = col[num_col]->left;
        for (i = col[num_col]->down; i != col[num_col]; i = i->down) for (j = i->right; j != i; j = j->right) {
            (j->down->up = j->up)->down = j->down;
            --size_col[j->num_col];
        }
    }
    void recover(size_t num_col) {
        dlx_node *i, *j;
        for (i = col[num_col]->up; i != col[num_col]; i = i->up) for (j = i->left; j != i; j = j->left) {
            j->down->up = j->up->down = j;
            ++size_col[j->num_col];
        }
        col[num_col]->right->left = col[num_col]->left->right = col[num_col];
    }
    std::vector<size_t> sol;
    bool dance() {
        if (col[0]->right == col[0]) return true;
        size_t target_col = col[0]->right->num_col;
        for (dlx_node *cur = col[0]->right->right; cur != col[0]; cur = cur->right)
            if (size_col[cur->num_col] && size_col[cur->num_col] < size_col[target_col]) target_col = cur->num_col;
        erase(target_col);
        for (dlx_node *cur = col[target_col]->down; cur != col[target_col]; cur = cur->down) {
            sol.push_back(cur->num_row);
            for (dlx_node *i = cur->right; i != cur; i = i->right) erase(i->num_col);
            if (dance()) return true;
            for (dlx_node *i = cur->right; i != cur; i = i->right) recover(i->num_col);
            sol.pop_back();
        }
        recover(target_col);
        return false;
    }
};
size_t get_id(size_t row, size_t col, size_t num) { return row * 81 + col * 9 + num; }
int main() {
    for (unsigned i = 0; i < 9; i++) for (unsigned j = 0; j < 9; j++) scanf("%u", mat[i] + j);
    load_matrix();
    remove();
    dlx solver(729, 324);
    for (unsigned i = 0; i < 9; i++) for (unsigned j = 0; j < 9; j++) for (unsigned v = 0; v < 9; v++) {
        if (mat[i][j] && mat[i][j] != v + 1) continue;
        size_t id = get_id(i, j, v) + 1;
        solver.insert(id, i * 9 + v + 1);
        solver.insert(id, 81 + j * 9 + v + 1);
        solver.insert(id, 81 * 2 + point_to_mat_id(i, j) * 9 + v + 1);
        solver.insert(id, 81 * 3 + i * 9 + j + 1);
    }
    if (!solver.dance()) {
        puts("no solution");
        return 0;
    }
    for (auto v : solver.sol) mat[(v - 1) / 81][((v - 1) / 9) % 9] = (v - 1) % 9 + 1;
    for (unsigned i = 0; i < 9; i++, putchar('\n')) for (unsigned j = 0; j < 9; j++) printf("%u ", mat[i][j]);
}