using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SudokuSolver
{
    public class Program
    {
        private static readonly string[] allowedNumbers = { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
        private static readonly string emptyBox = "x";

        private static string[,] sudoku = new string[9, 9];

        static void Main()
        {
            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                string input = Console.ReadLine();
                string[] sudokuRow = input.Trim().Split().ToArray();

                if (sudokuRow.Length != 9)
                {
                    throw new ArgumentException("Provided data contains more or less than 9 symbols");
                }

                foreach (var symbol in sudokuRow)
                {
                    isValidString(symbol);
                }

                for (int j = 0; j < sudoku.GetLength(1); j++)
                {
                    sudoku[i, j] = sudokuRow[j];
                }
            }

            // test printing
            var printSudoku = PrintSudoku(sudoku);
            Console.Write(printSudoku);

            SolveSudoku(sudoku, 0, 0);
        }

        static void isValidString(string str)
        {
            if (!allowedNumbers.Contains(str) && str.ToLower() != emptyBox.ToLower())
            {
                throw new ArgumentException("Provided data contains one or more invalid symbols!");
            }
        }

        static string PrintSudoku(string[,] sudoku)
        {
            var horizontalSeparator = "+-------+-------+-------+ ";
            var verticalSeparator = "| ";
            var stringBuilder = new StringBuilder();

            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                if (i == 0 || i % 3 == 0)
                {
                    stringBuilder.AppendFormat(horizontalSeparator + Environment.NewLine);
                }

                for (int j = 0; j < sudoku.GetLength(1); j++)
                {
                    if (j == 0 || j % 3 == 0)
                    {
                        stringBuilder.Append(verticalSeparator);
                    }

                    if (sudoku[i,j].ToLower() == emptyBox.ToLower())
                    {
                        stringBuilder.Append("  ");
                    }
                    else
                    {
                        stringBuilder.Append(sudoku[i, j] + " ");
                    }

                }

                stringBuilder.Append(verticalSeparator);
                stringBuilder.Append(Environment.NewLine);
            }

            stringBuilder.AppendFormat(horizontalSeparator + Environment.NewLine);

            var result = stringBuilder.ToString();
            return result;
        }

        static List<string> CheckRow(string[,] sudoku, int row)
        {
            List<string> rowAsList = new List<string>();
            for (int j = 0; j < sudoku.GetLength(1); j++)
            {
                if (sudoku[row,j] != emptyBox)
                {
                    rowAsList.Add(sudoku[row, j]);
                }
            }

            List<string> result = allowedNumbers.Except(rowAsList).ToList();

            return result;
        }

        static List<string> CheckCol(string[,] sudoku, int col)
        {
            List<string> colAsList = new List<string>();
            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                if (sudoku[i, col] != emptyBox)
                {
                    colAsList.Add(sudoku[i, col]);
                }
            }

            List<string> result = allowedNumbers.Except(colAsList).ToList();

            return result;
        }

        static List<string> CheckSquare(string[,] sudoku, int row, int col)
        {
            int startRow = ((row / 3) * 3);
            int startCol = ((col / 3) * 3);

            List<string> squareAsList = new List<string>();
            for (int i = startRow; i < startRow + 3; i++)
            {
                for (int j = startCol; j < startCol + 3; j++)
                {
                    if (sudoku[i,j] != emptyBox)
                    {
                        squareAsList.Add(sudoku[i, j]);
                    }
                }
            }

            List<string> result = allowedNumbers.Except(squareAsList).ToList();

            return result;
        }

        static List<string> CheckIntersection(List<string> checkRow, List<string> checkCol, List<string> checkSquare)
        {
            List<string> intersection = checkRow.Intersect(checkCol).Intersect(checkSquare).ToList();
            return intersection;
        }

        static void SolveSudoku(string[,] sudoku, int row = 0, int col = 0)
        {
            if (sudoku[row, col].ToLower() == emptyBox.ToLower())
            {
                var rowCheck = CheckRow(sudoku, row);
                var colCheck = CheckCol(sudoku, col);
                var squareCheck = CheckSquare(sudoku, row, col);
                var proposals = CheckIntersection(rowCheck, colCheck, squareCheck);

                if (proposals.Count == 0)
                {
                    return;
                }

                foreach (var proposal in proposals)
                {
                    sudoku[row, col] = proposal;
                    SolveSudoku(sudoku, row, col);
                    sudoku[row, col] = emptyBox;
                }
            }
            else
            {
                if (col + 1 < sudoku.GetLength(1))
                {
                    col += 1;

                    SolveSudoku(sudoku, row, col);
                }
                else if (row + 1 < sudoku.GetLength(0))
                {
                    col = 0;
                    row += 1;

                    SolveSudoku(sudoku, row, col);
                }
                else if (col == (sudoku.GetLength(1) - 1) && (row == sudoku.GetLength(0) - 1))
                {
                    Console.WriteLine(PrintSudoku(sudoku));

                }
            }
        }
    }
}