python/TangDou/LanQiaoBei/LanQiao14GuoSai/4_1.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;
}

void dfs(int u) {
    if (u == 81) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << g[i][j];
            cout << endl;
        }
        exit(0);
    }

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

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(0);
    return 0;
}