#include <iostream>
#include <string>
#include <vector>
#include <set>

const int SIZE = 9;

typedef std::vector< std::vector<int> > Matrix;

Matrix read_puzzle()
{
    Matrix puzzle(SIZE, std::vector<int>(SIZE, 0)); // this line initializes 9x9 board filled with zeros
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            std::cin >> puzzle[i][j];
        }
    }
    return puzzle;
}

void print_puzzle(Matrix puzzle) // a better way to pass a puzzle is pass-by-reference(instead of pass-by-value)
{
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            std::cout << puzzle[i][j] << " ";
        }
        std::cout << std::endl;
    }

}

bool is_valid_puzzle(Matrix puzzle, bool zeros_are_valid)
{
    std::vector< std::set<int> > rowNums(SIZE, std::set<int>());
    std::vector< std::set<int> > colNums(SIZE, std::set<int>());
    std::vector< std::set<int> > squareNums(SIZE, std::set<int>());
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            if (puzzle[i][j] == 0) {
                if (!zeros_are_valid) {
                    return false;
                }
                continue;
            }

            // TODO remove copypasta
            if (!rowNums[i].count(puzzle[i][j])) {
                rowNums[i].insert(puzzle[i][j]);
            } else {
                return false;
            }

            if (!colNums[j].count(puzzle[i][j])) {
                colNums[j].insert(puzzle[i][j]);
            } else {
                return false;
            }

            if (!squareNums[(i/3)*3 + (j/3)].count(puzzle[i][j])) {
                squareNums[(i/3)*3 + (j/3)].insert(puzzle[i][j]);
            } else {
                return false;
            }
        }
    }
    // debug output
    std::cout << "DEBUG" << std::endl;
    print_puzzle(puzzle);
    std::cout << "/DEBUG" << std::endl;
    return true;
}

Matrix solve_puzzle(Matrix puzzle)
{
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            if (puzzle[i][j] == 0) {
                for (int candidate_number = 1; candidate_number <= SIZE; ++candidate_number) {
                    puzzle[i][j] = candidate_number;
                    if (is_valid_puzzle(puzzle, true)) {
                        Matrix candidate_puzzle = solve_puzzle(puzzle);
                        if (is_valid_puzzle(candidate_puzzle, false)) {
                            return candidate_puzzle;
                        }
                    }
                }
            }
        }
    }
    return puzzle;
}

int main()
{
    Matrix puzzle = read_puzzle();
    print_puzzle(puzzle);
    Matrix solved_puzzle = solve_puzzle(puzzle);
    std::cout << "~~~~~~~~~~~~" << std::endl;
    print_puzzle(solved_puzzle);
}