题解 | #Sudoku#

#include <iostream>
#include <vector>
using namespace std;
int find_answer_ok = 0;

vector< vector<int>> sudo(9, vector<int>(9, 0));
vector< vector<int>> zerr;
int num;
bool check(int step, int k) {
    int m = zerr[step][0];
    int n = zerr[step][1];

    for (int i = 0; i < 9; i++) {
        if (sudo[m][i] == k)
            return false;
    }
    for (int i = 0; i < 9; i++) {
        if (sudo[i][n] == k)
            return false;
    }
    int m_start = m / 3 * 3;
    int n_start = n / 3 * 3;

    for (int i = m_start; i < m_start + 3; i++) {
        for (int j = n_start; j < n_start + 3; j++) {
            if (sudo[i][j] == k) {							//			存放需要填的位置
                return false;
            }
        }
    }
    return true;
}
void DFS(int step) {
    if (step == num) {
        find_answer_ok = 1;
        return;
    }

    int m = zerr[step][0];
    int n = zerr[step][1];

    for (int k = 1; k <= 9; k++) {
        if (check(step, k)) {
            sudo[m][n] = k;
            DFS(step + 1);
            if(find_answer_ok)     //找到直接return；
            {
                return;
            }
            sudo[m][n] = 0;			//找不到继续回溯
        }

    }
    return;
}
int main() {

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> sudo[i][j];
            if (sudo[i][j] == 0) {
                zerr.push_back({i, j});
            }
        }
    }
    num = zerr.size();

    DFS(0);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout<<sudo[i][j]<<' ';
        }
        cout<<endl;
    }



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