#include <iostream>
#include <string>
#include <sstream>
#include <array>


void printMatrix(int grid[9][9]);
bool possible(int y, int x, int n, int grid[9][9]);
void solve(int grid[9][9]);

int main() {
    int sudoku[9][9] = {
        { 5, 3, 0, 0, 7, 0, 0, 0, 0},
        { 6, 0, 0, 1, 9, 5, 0, 0, 0},
        { 0, 9, 8, 0, 0, 0, 0, 6, 0},
        { 8, 0, 0, 0, 6, 0, 0, 0, 3},
        { 4, 0, 0, 8, 0, 3, 0, 0, 1},
        { 7, 0, 0, 0, 2, 0, 0, 0, 6},
        { 0, 6, 0, 0, 0, 0, 2, 8, 0},
        { 0, 0, 0, 4, 1, 9, 0, 0, 5},
        { 0, 0, 0, 0, 8, 0, 0, 7, 9},
    };

    printMatrix(sudoku);
    std::cout << std::endl;
    solve(sudoku);
}

void solve(int grid[9][9]) {
    for (int x = 0; x < 9; ++x) {
        for (int y = 0; y < 9; ++y) {
            if (grid[x][y] == 0) {

                for (int n = 1; n < 10; ++n) {
                    if (possible(y, x, n, grid)) {
                        grid[x][y] = n;
                        solve(grid);
                        grid[x][y] = 0;
                    }
                }

                return;
            }
        }
    }

    printMatrix(grid);
}

bool possible(int y, int x, int n, int grid[9][9]) {
    for (int i = 0; i < 9; ++i) { if (grid[i][y] == n) { return false; } }
    for (int i = 0; i < 9; ++i) { if (grid[x][i] == n) { return false; } }

    int x0 = (x / 3) * 3;
    int y0 = (y / 3) * 3;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (grid[x0 + i][y0 + j] == n) {
                return false;
            }
        }
    }

    return true;
}

void printMatrix(int grid[9][9]) {
    for (int i = 0; i < 9; ++i) {
        std::stringstream ss;
        for (int j = 0; j < 9; ++j) {
            ss << grid[i][j] << " ";
        }
        std::cout << ss.str() << std::endl;
    }
}