import java.util.Scanner;

public class Sudoku {

	private static final int SIZE = 9;

	//solver//
	public static boolean solve(int[][] b) {
		if(b.length != SIZE) return false;
		for(int k = 0; k < SIZE; k++) {
			for(int l = 0; l < SIZE; l++) {
				if(b[k][l] != 0) continue;
				for(int m = 1; m < 10; m++) {
					if(valid(b, m, k, l)) {
						b[k][l] = m;
						if(solve(b)) {
							return true;
						} else {
							b[k][l] = 0;
						}
					}
				} return false;
			}
		} System.out.println(toString(b));
		return true;
	}


	//check valid move//
	public static boolean valid(int[][] b, int number, int row, int col) {
		if(number == 0) return true;
		if((row<0||row>8)||(col<0||col>8)) return false;

		//check row//
		for(int k = 0; k < SIZE; k++) {
			if(k != col) {
				if(b[row][k] == number) return false;
			}
		}

		//check column//
		for(int k = 0; k < SIZE; k++) {
			if(k != row) {
				if(b[k][col] == number) return false;
			}
		}

		//check grids//
		for(int k = (row/3)*3; k < (row/3)*3+3; k++) {
			for(int l = (col/3)*3; l < (col/3)*3+3; l++) {
				if(k != row && l != col) {
					if(b[row][col] == number) return false;
				}
			}
		} return true;
	}

	//show board//
	public static String toString(int[][] b) {
		String result = "";
		if(b.length != SIZE || b[0].length != SIZE) return null;
		for(int k = 0; k < 9; k++) {
			if(k%3 == 0) result+=("+++++++++++++++++++++++++\n");
			for(int l = 0; l < 9; l++) {
				if(l == 0) result+=("+ "+b[k][l]+" ");
				else if(l == 8) result+=(b[k][l]+" +\n");
				else if((l+1)%3 == 0) result+=(b[k][l]+" + ");
				else result+=(b[k][l]+" ");
			}
		} result+=("+++++++++++++++++++++++++");
		return result;
	}



	//tester//
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int[][] board = {
			{6, 9, 3, 0, 5, 7, 1, 2, 0},
			{0, 0, 0, 0, 0, 0, 3, 0, 0},
			{0, 0, 2, 4, 0, 0, 0, 0, 6},
			{0, 0, 0, 7, 0, 0, 2, 5, 0},
			{4, 0, 5, 9, 0, 8, 6, 0, 1},
			{0, 7, 8, 0, 0, 6, 0, 0, 0},
			{8, 0, 0, 0, 0, 4, 7, 0, 0},
			{0, 0, 1, 0, 0, 0, 0, 0, 0},
			{0, 6, 7, 1, 8, 0, 4, 3, 2},
		};

		System.out.println(toString(board));
		System.out.println("solving");
		solve(board);

		scan.close();

	}

}