题解 | #Sudoku#

#include <iostream>
using namespace std;

int a[9][9];
int temp[9][9];

bool check(int m, int n) {

    for (int i = 0; i < m; i++)
        if (temp[i][n] == temp[m][n])
            return false;

    for (int j = 0; j < n; j++)
        if (temp[m][j] == temp[m][n])
            return false;

    for (int i = m + 1; i < 9; i++)
        if (a[i][n] == temp[m][n])
            return false;

    for (int j = n + 1; j < 9; j++)
        if (a[m][j] == temp[m][n])
            return false;

    for (int i = m / 3 * 3; i < m / 3 * 3 + 3; i++) {
        for (int j = n / 3 * 3; j < n / 3 * 3 + 3; j++) {
            if (i < m && temp[i][j] == temp[m][n])
                return false;
            if (i > m && a[i][j] == temp[m][n])
                return false;
        }
    }
    return true;//填法可行返回true
}

void dfs(int m, int n) {
    if (a[m][n] != 0) {
        if (n < 8)
            dfs(m, n + 1);
        else if (m < 8)
            dfs(m + 1, 0);
        else {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++)
                    cout << temp[i][j] << " ";
                cout << endl;
            }
            exit(0);
        }
    }
    else for (int i = 1; i <= 9; i++) {
        temp[m][n] = i;
        if (check(m, n)) {
            if (n < 8)
                dfs(m, n + 1);
            else if (m < 8)
                dfs(m + 1, 0);
            else {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++)
                        cout << temp[i][j] << " ";
                    cout << endl;
                }
                exit(0);
            }
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> a[i][j];
            temp[i][j] = a[i][j];
        }
    }

    dfs(0, 0);
}