#include <stdio.h>
#include <stdbool.h>

struct coord{
	int x;
	int y;
};

/* structure of parameters for play_sudoku function */
struct __sudoku_param {
	int grid[9][9];
	struct coord ulc[81]; /* ulc : unassigned 'location candidates' */
	int ulc_size;
	int ulc_idx; /* next ulc index */
};

bool play_sudoku(struct __sudoku_param*);
void find_avail_number(struct coord, struct __sudoku_param*, bool*);
void print_grid(struct __sudoku_param);

int main(void)
{
	struct __sudoku_param sudoku_param;

	/* Initialization */
	int ulc_size = 0;
	for(int i=0; i<9; i++){
		for(int j=0; j<9; j++){
			scanf("%d",&sudoku_param.grid[i][j]);

			if (!sudoku_param.grid[i][j]) {
				sudoku_param.ulc[ulc_size].x = i;
				sudoku_param.ulc[ulc_size].y = j;
				ulc_size ++;
			}
		}
	}
	sudoku_param.ulc_size = ulc_size;
	sudoku_param.ulc_idx = 0;

	/* Run */
	play_sudoku(&sudoku_param);

	/* Print the result */
	print_grid(sudoku_param);

	return 0;
}

// Backtracking
bool play_sudoku(struct __sudoku_param* sudoku_param)
{
	struct coord point;

	if (sudoku_param->ulc_idx == sudoku_param->ulc_size)
		return true;

	point.x = sudoku_param->ulc[sudoku_param->ulc_idx].x;
	point.y = sudoku_param->ulc[sudoku_param->ulc_idx].y;
	sudoku_param->ulc_idx++;

	bool is_avail[10];
	for (int i = 1; i < 10; i++)
		is_avail[i] = true;
	find_avail_number(point, sudoku_param, is_avail);

	for (int i = 1; i < 10; i++) {
		if(is_avail[i]) {
			sudoku_param->grid[point.x][point.y] = i;
			if(play_sudoku(sudoku_param)) return true;
			sudoku_param->grid[point.x][point.y] = 0;
		}
	}

	sudoku_param->ulc_idx--;
	return false;
}

/* Find available numbers at the point */
void find_avail_number(struct coord point, struct __sudoku_param* sudoku_param, bool* is_avail)
{
	for(int idx = 0; idx < 9; idx++){
		is_avail[sudoku_param->grid[idx][point.y]] = false;
		is_avail[sudoku_param->grid[point.x][idx]] = false;
	}

	int start_x = (point.x/3)*3;
	int start_y = (point.y/3)*3;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			is_avail[sudoku_param->grid[start_x+i][start_y+j]] = false;
		}
	}
}

void print_grid(struct __sudoku_param sudoku_param)
{
	for(int i=0; i<9; i++){
		for(int j=0; j<9; j++){
			printf("%d ", sudoku_param.grid[i][j]);
		}
		printf("\n");
	}
}