// Буняева В.

#include <iostream>
#include <vector>
#include <algorithm>

#include "ReadWriter.h"

namespace exact_cover
{

namespace
{
struct element
{
    element* left;
    element* right;

    element* up;
    element* down;

    int i_row = -1;

    element* col = nullptr;

    element() : left(this), right(this), up(this), down(this)
    {}

    void remove_hor()
    {
        // Remove the element from a horizontal (left-right) list

        left->right = right;
        right->left = left;
    }

    void remove_ver()
    {
        // Remove the element from a vertical (top-down) list

        up->down = down;
        down->up = up;
    }

    void put_back_hor()
    {
        // Undo the effect of `this->remove_hor()`

        left->right = this;
        right->left = this;
    }

    void put_back_ver()
    {
        // Undo the effect of `this->remove_ver()`

        up->down = this;
        down->up = this;
    }

    void cover_all_cols()
    {
        // (For a row element) cover all columns that other elements on this row are set for

        for(element* cel = right; cel != this; cel = cel->right) {
            cel->col->cover_this_col();
        }
    }

    void uncover_all_cols()
    {
        // Undo the effect of `this->cover_all_cols()`

        for(element* cel = left; cel != this; cel = cel->left) {
            cel->col->uncover_this_col();
        }
    }

    void cover_this_col()
    {
        // (For a column header) completely remove all rows that are set for this column

        remove_hor();

        for(element* rel = down; rel != this; rel = rel->down) {
            for(element* el = rel->right; el != rel; el = el->right) {
                el->remove_ver();
            }
        }
    }

    void uncover_this_col()
    {
        // Undo the effect of `this->cover_this_col()`

        for(element* rel = up; rel != this; rel = rel->up) {
            for(element* el = rel->left; el != rel; el = el->left) {
                el->put_back_ver();
            }
        }

        put_back_hor();
    }
};

struct solution
{
    std::vector<int> ix_rows;
    bool found_solution = false;

    element* root;

    explicit solution(element* root) : root(root)
    {}

    void search()
    {
        if(root == root->right) {
            found_solution = true;

            return;
        }

        element* col = root->right;

        col->cover_this_col();

        for(element* rel = col->down; rel != col; rel = rel->down) {
            ix_rows.push_back(rel->i_row);

            rel->cover_all_cols();

            search();

            rel->uncover_all_cols();

            if(found_solution) {
                break;
            }

            ix_rows.pop_back();
        }

        col->uncover_this_col();
    }
};
}

/**
 * Solve the exact cover problem
 * @param matrix A matrix where rows constitute subsets, and matrix[i][j] = { ith subset contains }
 * @return If the solution is found, indices in the original matrix of selected subsets. Otherwise, undefined
 */
std::vector<int> get_exact_cover(const std::vector<std::vector<bool>>& matrix)
{
    const size_t n_rows = matrix.size();
    const size_t n_cols = matrix[0].size();

    element* root = new element;

    {
        // Column headers
        std::vector<element*> cols;

        for(int i = 0; i < n_cols; i++) {
            element* col = new element;

            col->left = root->left;
            col->right = root;

            col->put_back_hor();

            cols.push_back(col);
        }

        // Leftmost (in order of column indices) element of every row
        std::vector<element*> rows((size_t)n_rows, nullptr);

        for(int i_row = 0; i_row < n_rows; i_row++) {
            for(int i_col = 0; i_col < n_cols; i_col++) {
                if(!matrix[i_row][i_col]) {
                    continue;
                }

                element* el = new element;

                el->i_row = i_row;

                // Connect the element with its column -- put at the bottom

                el->col = cols[i_col];

                el->up = cols[i_col]->up;
                el->down = cols[i_col];

                el->put_back_ver();

                // Connect the element with its row -- put at the right

                if(rows[i_row] == nullptr) {
                    rows[i_row] = el;

                    el->left = el;
                    el->right = el;
                }

                el->left = rows[i_row]->left;
                el->right = rows[i_row];

                el->put_back_hor();
            }
        }
    }

    solution s(root);

    s.search();

    {
        // Delete the whole data structure

        element* next_col;

        for(element* col = root->right; col != root; col = next_col) {
            element* next_el;

            for(element* el = col->down; el != col; el = next_el) {
                next_el = el->down;

                delete el;
            }

            next_col = col->right;

            delete col;
        }

        delete root;
    }

    return s.ix_rows;
}

}

namespace sudoku
{

namespace
{
/**
 * Size of the Sudoku problem -- which is undefined for anything other than 9
 */
const int N = 9;

/**
 * Length of a box's side in the Sudoku problem
 */
const int N_BOX = 3;

/**
 * Represents the action of setting a specific Sudoku cell to a specific value
 */
struct possibility
{
    /**
     * Coordinates of the cell that the value is assigned to
     */
    const int i_row, i_col;

    /**
     * The value that is assigned to the specified cell
     */
    const char value;

    /**
     * Apply the possibility to the specified Sudoku field
     * @param field The Sudoku field (an `N` by `N` array)
     */
    void apply(char** const field) const
    {
        field[i_row][i_col] = value;
    }
};

/**
 * Calculate whether each Sudoku constraint applies for the specified possibility
 * @param p The possibility
 * @return The values of the constraints' predicates in a specific, but opaque order
 */
std::vector<bool> calculate_constraints(const possibility& p)
{
    std::vector<bool> values;

    // Cell constraints (i.e. only one of any digit in every cell)
    for(int i_row = 0; i_row < N; i_row++) {
        for(int i_col = 0; i_col < N; i_col++) {
            values.push_back(p.i_row == i_row && p.i_col == i_col);
        }
    }

    // Row constraints (i.e. one of each digit in every row)
    for(int i_row = 0; i_row < N; i_row++) {
        for(char c = '1'; c <= '9'; c++) {
            values.push_back(p.i_row == i_row && p.value == c);
        }
    }

    // Column constraints
    for(int i_col = 0; i_col < N; i_col++) {
        for(char c = '1'; c <= '9'; c++) {
            values.push_back(p.i_col == i_col && p.value == c);
        }
    }

    // Box constraints
    for(int i_brow = 0; i_brow < N / N_BOX; i_brow++) {
        for(int i_bcol = 0; i_bcol < N / N_BOX; i_bcol++) {
            for(char c = '1'; c <= '9'; c++) {
                values.push_back(
                        p.i_row / N_BOX == i_brow && p.i_col / N_BOX == i_bcol && p.value == c
                );
            }
        }
    }

    return values;
}
}

/**
 * Fill the empty cells on the specified Sudoku field such that the field is solved. If the field is not solvable, the
 * behavior is undefined
 * @param field The Sudoku field -- a 9 by 9 array of ASCII characters '1' through '9' and '+' for empty cells
 */
void solve_sudoku_field(char** const field)
{
    std::vector<possibility> possibilities;

    for(int i_row = 0; i_row < N; i_row++) {
        for(int i_col = 0; i_col < N; i_col++) {
            if(field[i_row][i_col] != '+') {
                possibilities.push_back({ i_row, i_col, field[i_row][i_col] });
            }
            else {
                for(char c = '1'; c <= '9'; c++) {
                    possibilities.push_back({ i_row, i_col, c });
                }
            }
        }
    }

    std::vector<std::vector<bool>> constraint_values(possibilities.size());

    std::transform(possibilities.begin(), possibilities.end(), constraint_values.begin(), calculate_constraints);

    std::vector<bool> is_selected(possibilities.size(), false);

    for(int i_p : exact_cover::get_exact_cover(constraint_values)) {
        is_selected[i_p] = true;
    }

    for(int i_p = 0; i_p < possibilities.size(); i_p++) {
        if(!is_selected[i_p]) {
            continue;
        }

        possibilities[i_p].apply(field);
    }
}

}

//Основной метод решения задачи, параметры:
//n - размер исходной задачи и результата (NxN)
//field - матрица NxN, не до конца заполненное поле, содержит цифры и символы '+', как пустое место, которое надо заполнить
//Если так будет удобнее, то можно удалить этот массив, создать новый(такого же размера) и перенаправить указатель (для этого указатель передается как char**&)
//Требуется не допускать утечек памяти! Проверьте перед сдачей, так как в одной из работ это была наиболее частая ошибка.
void solve_sudoku(char**& field, int n)
{
    sudoku::solve_sudoku_field(field);
}

int main()
{
    using namespace std;

    ReadWriter rw;
    //Входные параметры
    int n = rw.readInt();
    //Массив для матрицы
    char** arr = new char*[n];
    for (int i = 0; i < n; i++)
        arr[i] = new char[n];

    //Чтение матрицы
    rw.readMatrix(arr, n, n);

    //Алгоритм решения судоку, ответ в тот же массив, где и была разреженная матрица
    solve_sudoku(arr, n);

    //Выводим результаты
    rw.writeInt(n);
    rw.writeMatrix(arr, n, n);

    //Освободим память
    for (int i = 0; i<n; i++)
        delete[] arr[i];
    delete[] arr;

    return 0;
}