题解 | #Sudoku#DFS 回溯

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int row = 9;
const int column = 10;
array<array<bool, column>, row> checkr = {false};
array<array<bool, column>, row> checkc = {false};
array<array<bool, column>, row> checksub = {false};

bool dfs(vector<vector<int>>& arr, vector<pair<int, int>>& indexs, int index) {
    if (index == indexs.size()) {
        return true;
    }
    int i = indexs[index].first;
    int j = indexs[index].second;
    int subnum = i / 3 * 3 + j / 3;
    for (int num = 1; num <= 9; num++) {
        if (!checkr[i][num] && !checkc[j][num] && !checksub[subnum][num]) {
            checkr[i][num] = checkc[j][num] = checksub[subnum][num] = true;
            if (dfs(arr, indexs, index + 1)) {
                arr[i][j] = num;
                return true;
            }
            checkr[i][num] = checkc[j][num] = checksub[subnum][num] = false;
        }
    }
    return false;
}


int main() {
    vector<vector<int>> arr(9, vector<int>(9, 0));
    vector<pair<int, int>> indexs;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            int n;
            cin >> n;
            arr[i][j] = n;
            if (n != 0) {
                checkr[i][n] = true;
                checkc[j][n] = true;
                checksub[i / 3 * 3 + j / 3][n] = true;
            } else {
                indexs.emplace_back(i, j);
            }
        }
    }
    dfs(arr, indexs, 0);
    for (auto& row : arr) {
        for (auto& col : row) {
            cout << col << ' ';
        }
        cout << endl;
    }

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