题解 | #Sudoku#

#include <iostream>
#include <vector>
#include <array>
using namespace std;

bool dfs(vector<vector<int> >& m, vector<array<int, 2>>& toFill, int k) {
    if (k >= toFill.size())
        return true;
    array<int, 9> t = {0};
    auto pos = toFill[k];
    vector<int> val;
    //同一行
    for (auto& c : m[pos[0]])
        if (c) t[c - 1]++;
    //同一列
    for (auto& r : m)
        if (r[pos[1]]) t[r[pos[1]] - 1]++;
    //小方框内
    for (int i = pos[0] - pos[0] % 3; i < pos[0] - pos[0] % 3 + 3; ++i)
        for (int j = pos[1] - pos[1] % 3; j < pos[1] - pos[1] % 3 + 3; ++j)
            if (m[i][j])
                t[m[i][j] - 1]++;
    //所有可能的取值
    for (int i = 0; i < t.size(); ++i)
        if (!t[i]) val.push_back(i + 1);
    if (val.empty())
        return false;
    for (int v : val) {
        m[pos[0]][pos[1]] = v;
        if (dfs(m, toFill, k + 1)) {
            return true;
        }
        m[pos[0]][pos[1]] = 0;
    }
    return false;
}

int main() {

    vector<vector<int>> m(9, vector<int>(9, 0));
    vector<array<int, 2>> toFill;

    for (int i = 0; i < m.size(); ++i)
        for (int j = 0; j < m[0].size(); ++j) {
            cin >> m[i][j];
            if (!m[i][j])
                toFill.push_back({i, j});
        }
    dfs(m, toFill, 0);
    for (int i = 0; i < m.size(); ++i) {
        for (int j = 0; j < m[0].size(); ++j)
            cout << m[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

dfs深度优先搜索