题解 | #Sudoku#

#include <iostream>
#include <map>
#include <ostream>
#include <unordered_set>
#include <vector>
using namespace  std;
struct pair_hash {
    template <typename T1, typename T2>
    std::size_t operator()(const std::pair<T1, T2>& pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T1>()(pair.second);
    }
};

bool completesudoku(vector<vector<int>>& suduku,
                    map<std::pair<int, int>, int>& uncom) {
    if (uncom.empty()) {
        return true;
    }
    bool isfind = true;
    for (auto&& keyvalue : uncom) {
        if (keyvalue.second || suduku[keyvalue.first.first][keyvalue.first.second]) {
            unordered_set<int> sumrow;
            std::unordered_set<int> cols;
            auto row_sum = 0;
            auto cols_sum = 0;
            for (int i = 0; i < 9; ++i) {
                if (suduku[keyvalue.first.first][i] != 0) {
                    ++row_sum;
                    sumrow.insert(suduku[keyvalue.first.first][i]);
                } else if (uncom.count({keyvalue.first.first, i})) {
                    if (uncom[ {keyvalue.first.first, i}]) {
                        ++row_sum;
                        sumrow.insert(uncom[ {keyvalue.first.first, i}]);
                    }
                }
                if (suduku[i][keyvalue.first.second] != 0) {
                    ++cols_sum;
                    cols.insert(suduku[i][keyvalue.first.second]);
                } else if (uncom.count({i, keyvalue.first.second})) {
                    if (uncom[ {i, keyvalue.first.second}]) {
                        ++cols_sum;
                        cols.insert(uncom[ {i, keyvalue.first.second}]);
                    }
                }
            }
            std::unordered_set<int> block;
            auto block_sum = 0;
            for (int i = (keyvalue.first.first / 3) * 3;
                    i < (keyvalue.first.first / 3) * 3 + 3; ++i) {
                for (int j = (keyvalue.first.second / 3) * 3;
                        j < (keyvalue.first.second / 3) * 3 + 3; ++j) {
                    if (uncom.count({i, j})) {
                        if (uncom[ {i, j}]) {
                            ++block_sum;
                            block.insert(uncom[ {i, j}]);
                        }
                    } else if (suduku[i][j] != 0) {
                        ++block_sum;
                        block.insert(suduku[i][j]);
                    }
                }
            }
            if (block_sum > static_cast<int>(block.size()) ||
                    cols_sum > static_cast<int>(cols.size()) ||
                    row_sum > static_cast<int>(sumrow.size())) {
                return false;
            }
            if (block.size() == 9 && cols.size() == 9 && sumrow.size() == 9) {
			  	//注意这里的局部最优不一定是全局最优
                //suduku[keyvalue.first.first][keyvalue.first.second] = keyvalue.second;
            } else {
                isfind = false;
            }
        } else {
            isfind = false;
        }
    }
    if (isfind) {
        return true;
    }
    for (auto &[fst, snd] : uncom) {
        if (!snd) {
            for (int i = 1; i <= 9; ++i) {
                auto cc = uncom;
                cc[fst] = i;
                if (completesudoku(suduku, cc)) {
                    uncom = cc;
                    return true;
                }
            }
            break;
        }
    }
    return false;
}

int main() {
    while (true) { // 注意 while 处理多个 case
        vector<vector<int>> sudoku(9, vector<int>(9, 0));
        std::map<std::pair<int, int>, int> uncom;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                cin >> sudoku[i][j];
                if (!sudoku[i][j]) {
                    uncom[ {i, j}] = 0;
                }
            }
        }
        if (completesudoku(sudoku, uncom)) {
            for (auto&& keyvalue : uncom) {
                sudoku[keyvalue.first.first][keyvalue.first.second] = keyvalue.second;
            }
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    cout << sudoku[i][j] << ' ';
                }
                cout << endl;
            }
        }

        break;
    }
}
// 64 位输出请用 printf("%lld")

递归好写，终止条件难写，一直以为数独局部像拼图拼好就可以不动了，记录一下