//
// The following code is public domain (written in 2005 by Nick Smallbone)
// It can be found at http://www.8325.org/sudoku/
//

// It works by keeping track of which numbers can be used to fill the remaining
// cells in each row, column and block. It then will only fill a cell with a
// number that is valid for that row, column and block.

// On every recursion, it chooses the cell with the least possible number
// available to choose from. This has the rather nice effect that impossible
// cells are noticed straight away without any special cases, and cells with
// only one possibility are filled in straight away.

#include <iostream>
#include <cassert>

using namespace std;

// The size of the Sudoku game
static const unsigned blockSize = 3;
static const unsigned gridSize = blockSize * blockSize;

//
// Some functions for representing sets as bitfields
// (counting from 0)
//

typedef unsigned long bitfield;

// No bit we'll be using is above this
static const bitfield maskMax = 1 << gridSize;

// A bitfield with all bits set
static const bitfield allSet = maskMax - 1;

// Returns the size of the set
static unsigned bitCount(bitfield bits) {
	unsigned result = 0;
	bitfield mask = 1;

	while(mask != maskMax) {
		if (bits & mask)
			result++;
		mask *= 2;
	}

	return result;
}

// Returns a bitfield representing {num}
static inline bitfield bitFor(unsigned num) {
	return 1 << (num - 1);
}

class Puzzle {
	// The value of any empty cell (i, j) comes from
	// rows[i] & cols[j] & blocks[i/3][j/3]
	bitfield rows[gridSize];
	bitfield cols[gridSize];
	bitfield blocks[blockSize][blockSize];

	// This contains invalid if the cell is empty,
	// its value otherwise.
	unsigned cells[gridSize][gridSize];

public:
	// This number is invalid, and represents an empty cell
	static const unsigned invalid = gridSize + 1;

	Puzzle() {
		// Better initialise the arrays
		unsigned i, j;

		for (i = 0; i < gridSize; i++) rows[i] = allSet;
		for (i = 0; i < gridSize; i++) cols[i] = allSet;

		for (i = 0; i < blockSize; i++)
			for (j = 0; j < blockSize; j++)
				blocks[i][j] = allSet;

		for (i = 0; i < gridSize; i++)
			for (j = 0; j < gridSize; j++)
				cells[i][j] = invalid;
	}

	// Return the set of values which could be at (i, j)
	inline bitfield candidates(unsigned i, unsigned j) {
		assert(cells[i][j] == invalid);

		return rows[i] & cols[j] & 
			blocks[i/blockSize][j/blockSize];
	}

	// Fill in the cell at (i, j)
	inline void set(unsigned i, unsigned j, unsigned n) {
		bitfield bit = bitFor(n);

		// Check this is a valid value for the cell
		assert((candidates(i, j) & bit) != 0);

		// No other cells in the row, column or block
		// can now have this value
		rows[i] &= ~bit;
		cols[j] &= ~bit;
		blocks[i/blockSize][j/blockSize] &= ~bit;
		cells[i][j] = n;
	}

	// Erase the cell at (i, j)
	inline void unset(unsigned i, unsigned j, unsigned n) {
		bitfield bit = bitFor(n);

		// Make sure it was already set
		assert(cells[i][j] == n);

		rows[i] |= bit;
		cols[j] |= bit;
		blocks[i/blockSize][j/blockSize] |= bit;
		cells[i][j] = invalid;
	}

	// Find the cell with the lowest number of candidates
	// in the specified rectangular area.
	// It searches in iMin <= i < iMax
	// and jMin <= j < jMax
	// Return false if the grid is full.
	bool findMin(unsigned iMin, unsigned iMax, unsigned jMin, unsigned jMax,
		unsigned &outI, unsigned &outJ)
	{
		bool found = false;
		unsigned count = 0;

		for (unsigned i = iMin; i < iMax; i++)
			for (unsigned j = jMin; j < jMax; j++)
				if (cells[i][j] == invalid &&	
					(!found || bitCount(candidates(i, j)) < count))
				{
					count = bitCount(candidates(i, j));
					outI = i;
					outJ = j;
					found = true;
				}

		return found;
	}

	// Returns the value of a certain cell, or invalid
	inline unsigned getCell(unsigned i, unsigned j) { return cells[i][j]; }
};

// Tries to solve the puzzle in-place. It returns true if it could fill in
// all the squares between iMin and iMax and jMin and jMax, false otherwise.
// If destructive is false it will reverse all its changes once it
// finds a solution or gives up.
// If checkBlocks is true it will try to fill in each 3x3 block separately
// before it starts - if it can't do that then it can't solve the puzzle

bool solve(Puzzle &puzzle, unsigned iMin, unsigned iMax,
	unsigned jMin, unsigned jMax, bool destructive, bool checkBlocks)
{
	// Check that each block can be filled if we've been asked to
	if (checkBlocks) {
		for (unsigned i = 0; i < blockSize; i++)
			for (unsigned j = 0; j < blockSize; j++)
				if (!solve(puzzle,
					i*blockSize, i*blockSize + blockSize,
					j*blockSize, j*blockSize + blockSize, 
					false, false))
						return false;
	}

	// Guess a good cell to brute-force with
	unsigned i;
	unsigned j;

	if (!puzzle.findMin(iMin, iMax, jMin, jMax, i, j))
		// We must have finished
		return true;

	// Iterate through the possible values this cell could have
	unsigned num = 1;
	unsigned mask = bitFor(num);

	while(mask != maskMax) {
		if (puzzle.candidates(i, j) & mask) {

			// Try this number
			puzzle.set(i, j, num);

			bool solved = (solve(puzzle, iMin, iMax, jMin, jMax, 
				destructive, checkBlocks));

			// Reverse the changes if needed
			if (!solved || !destructive)
				puzzle.unset(i, j, num);

			if (solved)
				return true;

		}
			

		// Advance to the next number
		mask *= 2;
		num++;
	}

	// None of the possibilities for cell (i,j) work
	return false;
}

// Reads in a puzzle from standard input
void readPuzzle(Puzzle &p) {
	for (unsigned i = 0; i < gridSize; i++) {
		for (unsigned j = 0; j < gridSize; j++) {
			char c;
			cin >> c;
			if (c >= '1' && c <= '9') {
				c = c - '0';
				// Refuse to input an invalid puzzle

				if ((p.candidates(i, j) & bitFor(c)) == 0)
					exit(1);
				else
					p.set(i, j, c);
			} else if (c == '.') {
			} else exit(1);
		}

		//cin >> endl;
	}
}

// Prints out a (hopefully) completed puzzle
void printPuzzle(Puzzle &p) {
	for (unsigned i = 0; i < gridSize; i++) {
		for (unsigned j = 0; j < gridSize; j++) {
			if (p.getCell(i, j) == p.invalid)
				cout << " ";
			else
				cout << p.getCell(i, j);
		}

		cout << endl;
	}
}

// Solve and print out a puzzle
void outputSolution(Puzzle &p) {
	if (solve(p, 0, gridSize, 0, gridSize, true, true))
		printPuzzle(p);
}

int main() {
	Puzzle p;

	readPuzzle(p);
	outputSolution(p);
	
	return 0;
}