???????????????????

#include <iostream>
using namespace std;

#define N 9

// 检查在 (row, col) 位置放置 num 是否安全
bool isSafe(int grid[N][N], int row, int col, int num) {
    // 检查行
    for (int x = 0; x < N; x++) {
        if (grid[row][x] == num) {
            return false;
        }
    }

    // 检查列
    for (int x = 0; x < N; x++) {
        if (grid[x][col] == num) {
            return false;
        }
    }

    // 检查 3x3 子网格
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[i + startRow][j + startCol] == num) {
                return false;
            }
        }
    }

    return true;
}

// 求解数独
bool solveSudoku(int grid[N][N]) {
    int row = -1, col = -1;
    bool isEmpty = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                row = i;
                col = j;
                isEmpty = false;
                break;
            }
        }
        if (!isEmpty) {
            break;
        }
    }

    // 没有空位表示成功填充
    if (isEmpty) {
        return true;
    }

    // 尝试1到9的数字
    for (int num = 1; num <= 9; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;
            if (solveSudoku(grid)) {
                return true;
            }
            grid[row][col] = 0; // 回溯
        }
    }

    return false; // 触发回溯
}

// 打印数独
void printGrid(int grid[N][N]) {
    for (int r = 0; r < N; r++) {
        for (int d = 0; d < N; d++) {
            cout << grid[r][d] << " ";
        }
        cout << endl;
    }
}

// 用户输入数独
void inputGrid(int grid[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
        }
    }
}

int main() {
    int grid[N][N];
    inputGrid(grid);

    if (solveSudoku(grid)) {
        printGrid(grid);
    } else {
        cout << "无解" << endl;
    }

    return 0;
}