/* Class: COP3530
 * Date: Feb 17, 2006
 * Instructor: Arup Guha
 * TA: Adam Campbell
 *
 * Homework #2
 **/

import java.io.*;
import java.util.*;

public class Hw2{

	private static boolean solved;
	private static int[][] solution = new int[9][9];

	/* I have main throw exception so I don't need the try/catch blocks everywhere when reading in from the file.
	 * In general, this is not good programming practice, but for these simple problems we are more interested in the
	 *   algorithm.
	 **/
	public static void main(String[] args) throws Exception{

		// keeps track of which values can be used in each row, column and square
		boolean[][][] used = new boolean[9][9][10];

		int[][] board = new int[9][9]; // keeps track of the current state of the board
		int n; // the number of input cases
		BufferedReader userInputReader, fileReader;
		String fileName;
		StringTokenizer tokenizer;
		int curValue;

		// initialize the BufferedReader to read from standard input
		userInputReader = new BufferedReader(new InputStreamReader(System.in));

		// prompt the user for the file name, and get the file name from the user
		System.out.print("Please enter the file name: ");
		fileName = userInputReader.readLine();

		// open up the input file
		fileReader = new BufferedReader(new FileReader(fileName));

		// read n and initialize the matrix
		n = Integer.parseInt(fileReader.readLine());

		for(int testCase = 1; testCase <= n; testCase++){

			// initialize the used 3D matrix
			for(int i = 0; i < 9; i++){
				for(int j = 0; j < 9; j++){
					for(int k = 0; k < 10; k++){
						used[i][j][k] = false;
					}
				}
			}

			// read in the board
			for(int row = 0; row < 9; row++){

				tokenizer = new StringTokenizer(fileReader.readLine());

				for(int col = 0; col < 9; col++){

					curValue = Integer.parseInt(tokenizer.nextToken());

					board[row][col] = curValue;

					Hw2.useValueOnBoard(used, row, col, curValue);

				}

			}

			System.out.println("Test case " + testCase + ":");
			
			/* First check for invalid boards.
			 * If the board is OK, then try to solve it
			 **/
			if(Hw2.boardIsInvalid(board)){
				System.out.println("No solution possible.");
			}else{

				Hw2.solved = false;

				Hw2.solveSudoku(board, used);

				if(!Hw2.solved){
					System.out.println("No solution possible.");
				}else{

					for(int row = 0; row < 9; row++){
						System.out.print(solution[row][0]);
						for(int col = 1; col < 9; col++){
							System.out.print(" " + solution[row][col]);
						}
						System.out.println();
					}

				}

			}

			System.out.println();

		}

	}

	/* Throughout the algorithm, we keep track of which values can (and have been) used at
	 *   specific locations on the board.  This allows us to quickly decide which values a
	 *   particular, unplayed board location can take.  This function sets the row, column,
	 *   and 3x3 box locations in used to true for the particular value, that way when we try
	 *   to fill out the board, we do not use duplicate values in a row, column, or 3x3 box.
	 **/
	private static void useValueOnBoard(boolean[][][] used, int row, int col, int value){

		// if the value is 0, we can just exit out of here
		if(value == 0) return;

		// set the row and column
		for(int i = 0; i < 9; i++){
			used[row][i][value] = true;
			used[i][col][value] = true;
		}

		// Set the 3x3 square
		for(int i = (row/3)*3; i < (row/3)*3+3; i++){
			for(int j = (col/3)*3; j < (col/3)*3+3; j++){
				used[i][j][value] = true;
			}
		}

	}

	/* This function returns true if the given board is invalid.
	 * A board is invalid if it has a duplicate number in a single row, column, or 3x3 box
	 **/
	private static boolean boardIsInvalid(int[][] board){

		boolean[] valuesUsed = new boolean[10];

		// first check all of the rows
		for(int row = 0; row < 9; row++){

			Arrays.fill(valuesUsed, false);

			for(int col = 0; col < 9; col++){
				if(board[row][col] != 0 && valuesUsed[board[row][col]]) return true;
				valuesUsed[board[row][col]] = true;
			}

		}

		// next check all of the columns
		for(int col = 0; col < 9; col++){

			Arrays.fill(valuesUsed, false);

			for(int row = 0; row < 9; row++){
				if(board[row][col] != 0 && valuesUsed[board[row][col]]) return true;
				valuesUsed[board[row][col]] = true;
			}

		}

		// finally check all of the 3x3 squares
		for(int rowOffset = 0; rowOffset < 9; rowOffset += 3){
			for(int colOffset = 0; colOffset < 9; colOffset += 3){

				Arrays.fill(valuesUsed, false);

				for(int rowIndex = 0; rowIndex < 3; rowIndex++){
					for(int colIndex = 0; colIndex < 3; colIndex++){
						if(board[rowOffset+rowIndex][colOffset+colIndex] != 0 && valuesUsed[board[rowOffset+rowIndex][colOffset+colIndex]]) return true;
						valuesUsed[board[rowOffset+rowIndex][colOffset+colIndex]] = true;
					}
				}

			}
		}

		// no errors were found, so return false
		return false;

	}

	/* We can deduce the value of some locations.  For example, if 8 of the 9
	 *   values on a row have been filled in, we know what that last value must be.
	 * This function will set those values, and then call the checkRowColBoxForce
	 *   function which is described below.
	 **/
	private static void forceNoChoice(int[][] board, boolean[][][] used){

		boolean changed = true;
		boolean changedAtLeastOnce = false;

		// repeat this process until the board has reached a fixed point
		while(changed){

			changed = false;

			for(int row = 0; row < 9; row++){
				for(int col = 0; col < 9; col++){

					// The location does not have a value, and only one choice exists, so we set it
					if(board[row][col] == 0 && Hw2.numChoicesAt(used, row, col) == 1){

						for(int actualChoice = 1; actualChoice <= 9; actualChoice++){

							if(!used[row][col][actualChoice]){

								board[row][col] = actualChoice;

								Hw2.useValueOnBoard(used, row, col, actualChoice);

							}

						}

						changedAtLeastOnce = true;
						changed = true;

					}

				}

			}

		}

		/* These functions keep calling eachother until a fixed point has been reached
		 **/
		if(changedAtLeastOnce){
			Hw2.checkRowColBoxForce(board, used);
		}

	}

	/* This function optimizes the program a lot.  Let's imagine a row on the board with three
	 *   blank locations.  One location can take the values 1,2 while the other one can take 2,3
	 *   and the third can take 2,3.  Then, we know that the first location must take the value 1
	 *   because no one else in its row can take the value 1.
	 **/
	private static void checkRowColBoxForce(int[][] board, boolean[][][] used){

		// set each row/column/box we can
		boolean changed = true;
		boolean changedAtLeastOnce = false;

		// repeat this process until the board has reached a fixed point
		while(changed){

			changed = false;

			// check the rows
			for(int row = 0; row < 9; row++){
				for(int col = 0; col < 9; col++){
					for(int value = 1; value <= 9; value++){
						if(board[row][col] == 0 && !used[row][col][value]){
							boolean noOneElseInRow = true;
							for(int i = 0; i < 9; i++){
								if(row != i && !used[i][col][value] && board[i][col] == 0) noOneElseInRow = false;
							}

							if(noOneElseInRow){

								board[row][col] = value;

								Hw2.useValueOnBoard(used, row, col, value);

								changed = true;
								changedAtLeastOnce = true;

								break;
							}

						}
					}
				}
			}

			// check the columns
			for(int row = 0; row < 9; row++){
				for(int col = 0; col < 9; col++){
					for(int value = 1; value <= 9; value++){
						if(board[row][col] == 0 && !used[row][col][value]){
							boolean noOneElseInCol = true;
							for(int i = 0; i < 9; i++){
								if(col != i && !used[row][i][value] && board[row][i] == 0) noOneElseInCol = false;
							}

							if(noOneElseInCol){

								board[row][col] = value;

								Hw2.useValueOnBoard(used, row, col, value);

								changed = true;
								changedAtLeastOnce = true;

								break;
							}

						}
					}
				}
			}

			// check the 3x3 squares
			for(int row = 0; row < 9; row++){
				for(int col = 0; col < 9; col++){
					for(int value = 1; value <= 9; value++){
						if(board[row][col] == 0 && !used[row][col][value]){

							boolean noOneElseInBox = true;

							for(int i = (row/3)*3; i < (row/3)*3+3; i++){
								for(int j = (col/3)*3; j < (col/3)*3+3; j++){
									if(row==i&&col==j) continue;
									if(!used[i][j][value] && board[i][j] == 0){
										noOneElseInBox = false;
									}
								}
							}

							if(noOneElseInBox){

								board[row][col] = value;

								Hw2.useValueOnBoard(used, row, col, value);

								changed = true;
								changedAtLeastOnce = true;

								break;
							}

						}
					}
				}
			}

		}
		/* These functions keep calling eachother until a fixed point has been reached
		 **/
		if(changedAtLeastOnce){
			Hw2.forceNoChoice(board, used);
		}
		
	}

	/* Here is where the board actually gets solved
	 *
	 * 1. The first thing we do is set each 
	 **/
	private static void solveSudoku(int[][] board, boolean[][][] used){

		if(Hw2.solved) return;

		boolean changed;
		boolean[][][] origUsed = new boolean[9][9][10];
		int[][] origBoard = new int[9][9];
		boolean[][][] usedBeforeChoice = new boolean[9][9][10];
		int[][] boardBeforeChoice = new int[9][9];

		/* Keep a copy of the board and used matrices so they can be reset when the current
		 *   path of our backtracking does not work.
		 **/
		for(int i = 0; i < 9; i++){
			for(int j = 0; j < 9; j++){
				origBoard[i][j] = board[i][j];
				for(int k = 0; k < 10; k++){
					origUsed[i][j][k] = used[i][j][k];
				}
			}
		}

		/* We can really reduce the runtime of this algorithm by calling this function
		 * forceNoChoice sets the values of board locations to ones that must be true.
		 **/
		Hw2.forceNoChoice(board, used);

		// When the whole board is full, the game is done!
		boolean allFull = true;

		// check to see if the board is full
		for(int i = 0; i < 9; i++){
			for(int j = 0; j < 9; j++){

				if(board[i][j] == 0){
					allFull = false;
				}

			}
		}

		/* The game is over! We have found a completely full board
		 **/
		if(allFull && !Hw2.solved){
			Hw2.solved = true;
			for(int i = 0; i < 9; i++){
				for(int j = 0; j < 9; j++){
					Hw2.solution[i][j] = board[i][j];
				}
			}
			return;
		}

		int bestRow, bestCol, minChoices;

		minChoices = bestRow = bestCol = Integer.MAX_VALUE;

		/* First find the row, column location that does not yet have a value and has the
		 *   smallest number of possible choices.
		 **/
		for(int row = 0; row < 9; row++){
			for(int col = 0; col < 9; col++){
				if(board[row][col] == 0 && Hw2.numChoicesAt(used, row, col) < minChoices){
					bestRow = row;
					bestCol = col;
					minChoices = Hw2.numChoicesAt(used, row, col);
				}
			}
		}

		/* try out each valid value for the location found above.
		 **/
		for(int choice = 1; choice <= 9; choice++){

			if(!used[bestRow][bestCol][choice]){

				/* Keep a copy of the used and board matrices before we start recursing
				 * This allows us to backtrack if we find that the choice we made was
				 *   not a good one.
				 **/
				for(int i = 0; i < 9; i++){
					for(int j = 0; j < 9; j++){
						boardBeforeChoice[i][j] = board[i][j];
						for(int k = 0; k < 10; k++){
							usedBeforeChoice[i][j][k] = used[i][j][k];
						}
					}
				}

				board[bestRow][bestCol] = choice;
	
				Hw2.useValueOnBoard(used, bestRow, bestCol, choice);

				Hw2.solveSudoku(board, used);

				/* We need to reset our board and used matrices so we can try
				 *   another choice for the current location.
				 **/
				for(int i = 0; i < 9; i++){
					for(int j = 0; j < 9; j++){
						board[i][j] = boardBeforeChoice[i][j];
						for(int k = 0; k < 10; k++){
							used[i][j][k] = usedBeforeChoice[i][j][k];
						}
					}
				}

			}

		}

		/* Get the values of the board and used matrices that were originally input to this function
		 **/
		for(int i = 0; i < 9; i++){
			for(int j = 0; j < 9; j++){
				board[i][j] = origBoard[i][j];
				for(int k = 0; k < 10; k++){
					used[i][j][k] = origUsed[i][j][k];
				}
			}
		}

	}

	/* returns the number of values that could be placed at the location (row,col)
	 **/
	private static int numChoicesAt(boolean[][][] used, int row, int col){

		int count = 0;

		for(int value = 1; value <= 9; value++){
			if(!used[row][col][value]) count++;
		}

		return count;

	}

}