public class Sudoku {

	public static boolean DEBUG = false;
	public static int MATRIX_SIZE = 9;		// matrix Å©±â
	public int[][] fix = new int[MATRIX_SIZE][MATRIX_SIZE];		// °íÁ¤µÈ °ª
	public int[][] matrix= new int[MATRIX_SIZE][MATRIX_SIZE];	// °è»ê¿ë matrix
	
	public static void main(String [] args)
	{
		Sudoku sudoku = new Sudoku();
		
		sudoku.init();
		
		sudoku.find();
	}
	
	public void init()
	{
		// 6122
		fix[0][0] = 1;
		fix[8][0] = 9;
		
		fix[2][1] = 5;
		fix[5][1] = 1;
		
		fix[7][2] = 8;
		
		fix[1][3] = 7;
		fix[4][3] = 4;
		
		fix[3][4] = 3;
		fix[5][4] = 8;
		
		fix[4][5] = 6;
		fix[7][5] = 2;
		
		fix[1][6] = 2;
		
		fix[3][7] = 8;
		fix[6][7] = 6;
		
		fix[0][8] = 7;
		fix[8][8] = 5;

		
		
		/* 6121
		fix[8][0] = 7;
		
		fix[2][1] = 3;
		fix[8][1] = 9;
		
		fix[2][2] = 6;
		fix[3][2] = 5;
		
		fix[1][3] = 5;
		fix[4][3] = 4;
		
		fix[1][4] = 8;
		fix[7][4] = 9;
		
		fix[4][5] = 1;
		fix[7][5] = 4;
		
		fix[5][6] = 7;
		fix[6][6] = 4;
		
		fix[0][7] = 3;
		fix[6][7] = 7;
		
		fix[0][8] = 8;
		*/
		
		
	}
	
	public void matrix_init()
	{
		for(int i=0; i<MATRIX_SIZE; i++) {
			
			for(int j=0; j<MATRIX_SIZE; j++) {
				
				matrix[i][j]=fix[i][j];
			}
		}
	}
	
	public void find()
	{
		matrix_init();

		long loopCnt = 0;
		int current_position = 0;	// ÇöÀç À§Ä¡
		int x,y;	// ÇöÀç À§Ä¡ÀÇ x,y ÁÂÇ¥
		int number = 0;
		
		do {

			
			if(current_position>80) {
				System.out.println("find solution 2.");
				break;
			}
			// x,y ÁÂÇ¥ º¯È¯
			x = current_position % 9;
			y = current_position / 9;
			
			if(DEBUG) System.out.println("position : "+current_position+" ("+x+","+y+")");
			
			if(fix[x][y]!=0) {		// °íÁ¤µÈ °æ¿ì

				matrix[x][y]=fix[x][y];
				current_position++;
				continue;
			}
			
			number = matrix[x][y]+1;
			
			if(number>9) {			// ÇØ´ç À§Ä¡ÀÇ ¼ýÀÚ¸¦ 9±îÁö üũÇÑ °æ¿ì ÀÌÀüÄ­À¸·Î ÀÌÀü
				matrix[x][y]=0;
				current_position=get_before(current_position);
				continue;
			}
				
			if(number_available(x, y, number)==true) {		// ÇØ´ç ¼ýÀÚ°¡ µé¾î°¥¼ö ÀÖÀ¸¸é ´ÙÀ½Ä­À¸·Î ÁøÇà
				
				if(current_position==80) {		// ¸¶Áö¸·Ä­ÀÌ °¡´ÉÇÑ °æ¿ì ok
					matrix[x][y]=number;
					System.out.println("find solution");
					break;
				}
				if(DEBUG) System.out.println("available ("+x+","+y+") : "+number);
				current_position++;
			}
			
			matrix[x][y]=number;
					
			loopCnt++;
			if(loopCnt%100000==0) {
				System.out.println("loopCnt : "+loopCnt);
				print_matrix();
			}
				
			
		}while(current_position<MATRIX_SIZE*MATRIX_SIZE);

		/*
		if(current_position >= MATRIX_SIZE*MATRIX_SIZE) {
			System.out.println("No Solution.");
			return;
		}
		*/
		
		print_matrix();
	}
	
	// ÀÌÀü À§Ä¡¸¦ ã´Â´Ù.
	public int get_before(int current_position) 
	{
		int x,y;
		
		// x,y ÁÂÇ¥ º¯È¯
		do {
			current_position--;
			x = current_position % 9;
			y = current_position / 9;
			
			if(fix[x][y]==0) break;		// ÀÌÀüÄ­ÀÌ °íÁ¤Ä­ÀÌ ¾Æ´Ï¸é ¹Ýȯ
										// ÀÌÀüÄ­ÀÌ °íÁ¤Ä­ÀÌ¸é ±× ÀÌÀüÀ¸·Î À̵¿
			
		}while(true) ;
		
		return current_position;
	}
	
	// ÇØ´ç À§Ä¡¿¡ ±× ¼ýÀÚ°¡ µé¾î°¥¼ö ÀÖ´ÂÁö ÆÇ´Ü
	public boolean number_available(int x, int y, int number) 
	{
		
		if(fix[x][y]!=0) {			// °ªÀÌ °íÁ¤µÇ¾î ÀÖ´Â °æ¿ì
			if(fix[x][y]==number)	// °íÁ¤µÈ °ª°ú °°À¸¸é true
				return true;
			else					// °íÁ¤µÈ °ª°ú ´Ù¸£¸é false
				return false;
		}
		
		if(DEBUG) System.out.println("(x,y) : ("+x+","+y+")");
		
		for(int i=0; i<MATRIX_SIZE; i++) {
			
			if(DEBUG) System.out.println("--("+i+","+y+") : "+matrix[i][y]);
			if(matrix[i][y]==number) {	// °°Àº xÃà¿¡ µ¿ÀÏ ¼ýÀÚ°¡ ÀÖ´ÂÁö üũ
				if(DEBUG) System.out.println("match 1");
				return false;
			}
			
			if(matrix[x][i]==number) {	// °°Àº yÃà¿¡ µ¿ÀÏ ¼ýÀÚ°¡ ÀÖ´ÂÁö üũ
				if(DEBUG) System.out.println("match 2");
				return false;
			}
			
			if(x==y && matrix[i][i]==number) {	// ´ë°¢¼±¿¡ ÀÖ´Â °æ¿ì µ¿ÀϼýÀÚ°¡ ÀÖ´ÂÁö üũ
				if(DEBUG) System.out.println("match 3");
				return false;
			}
			
			if((x+y+1)%9==0 && matrix[MATRIX_SIZE-i-1][i]==number) {	// ´ë°¢¼±¿¡ ÀÖ´Â °æ¿ì µ¿ÀϼýÀÚ°¡ ÀÖ´ÂÁö üũ
				if(DEBUG) System.out.println("match 4");
				return false;
			}
			
		}

		// ÀÛÀº ¹Ú½º¾È¿¡ µ¿ÀϼýÀÚ°¡ ÀÖ´ÂÁö üũ
		int gx = x/3;
		gx = gx * 3;
		int gy = y/3;
		gy = gy * 3;
		
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				
				if(matrix[gx+i][gy+j]==number) {
					if(DEBUG) System.out.println("match 5");
					return false;
				}
			}
		}
		
		return true;

	}
	
	public void print_matrix()
	{
		for(int i=0; i<MATRIX_SIZE; i++) {
			
			for(int j=0; j<MATRIX_SIZE; j++) {
				
				if(matrix[j][i]==0)
					System.out.print(". ");
				else
					System.out.print(matrix[j][i]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
}