python/TangDou/LanQiaoBei/LanQiao14GuoSai/4_2.cpp

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

const int N = 9;
int g[N][N];

int check(int r, int c, int x) {
    // 同行，同列是不是存在同样的数字x
    for (int i = 0; i < 9; i++)
        if (g[r][i] == x || g[i][c] == x) return 0;

    // 找出3X3的小方块开始行和开始列,也就是所在块左上角坐标
    int row = r / 3 * 3;
    int col = c / 3 * 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (g[row + i][col + j] == x)
                return 0;
    return 1;
}

int dfs() {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (g[r][c] == 0) {
                for (int x = 1; x <= 9; x++) {
                    if (check(r, c, x)) {
                        g[r][c] = x;
                        if (dfs()) return 1;
                        g[r][c] = 0;
                    }
                }
                return 0;
            }
        }
    }
    return 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("4.in", "r", stdin);
#endif

    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) {
            char x;
            cin >> x;
            if (x != '.') g[i][j] = x - '0';
        }

    dfs();

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