题解 | #Sudoku#

按顺序依次填写每个空位置，每次填写完分别判断横竖还有对应的9宫格是否符合条件，如果符合则继续往下填，最终输出填写好的表格。

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

void fillTable(vector<vector<int>> & table, deque<pair<int, int>> & blank);

int main() {
    vector<vector<int>> table(9, vector<int>(9));
    deque<pair<int, int>> blank;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> table[i][j];
            if (table[i][j] == 0) {
                blank.push_back({i, j});
            }
        }
    }
    fillTable(table, blank);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << table[i][j] << ' ';
        }
        cout << endl;
    }
}

bool check(const vector<vector<int>> & table, const pair<int, int> & position) {
    set<int> temp1;
    set<int> temp2;
    for (int i = 0; i < 9; i++) {
        if (table[position.first][i] != 0 && temp1.find(table[position.first][i]) != temp1.end()) {
            return false;
        }
        if (table[i][position.second] != 0 && temp2.find(table[i][position.second]) != temp2.end()) {
            return false;
        }
        temp1.insert(table[position.first][i]);
        temp2.insert(table[i][position.second]);
    }
    temp1.clear();
    int i, j;
    if (position.first <= 2) {
        i = 0;
    } else if (position.first <= 5) {
        i = 3;
    } else {
        i = 6;
    }
    if (position.second <= 2) {
        j = 0;
    } else if (position.second <= 5) {
        j = 3;
    } else {
        j = 6;
    }
    for (int k = i; k < i + 3; k++) {
        for (int l = j; l < j + 3; l++) {
            if (table[k][l] != 0 && temp1.find(table[k][l]) != temp1.end()) {
                return false;
            }
            temp1.insert(table[k][l]);
        }
    }
    return true;
}

void fillTable(vector<vector<int>> & table, deque<pair<int, int>> & blank) {
    if (blank.empty()) {
        return;
    }
    pair<int, int> position = blank.front();
    for (int i = 1; i <= 9; i++) {
        table[position.first][position.second] = i;
        if (check(table, position)) {
            blank.pop_front();
            fillTable(table, blank);
            if (!blank.empty()) {
                blank.push_front(position);
            } else {
                break;
            }
        }
        table[position.first][position.second] = 0;
    }
}
// 64 位输出请用 printf("%lld")