#1146 Sudoku

47  1 s   128 MB  

Description

Sudoku란 9행 9열의 칸에 1이상 9이하의 아래의 규칙에 따라 숫자를 알맞게 채워넣는 게임이다.
규칙은 다음과 같다.

임의의 sudoku 퍼즐이 주어졌을 때, 채워지지 않은 칸들에 대해 규칙을 지키며 채울 수 있는 숫자들을 출력해주는 프로그램을 작성하라. 만약 한 칸에 대해서 모든 숫자를 출력할 수 있을 경우 다음과 같이 출력해야 한다.

출력할 수 있는 모든 숫자로 채울 수 없고, 몇 가지 숫자로 채울 수 있는 경우에는 그 숫자에 대응되는 위치에 숫자를 출력하고, 채울 수 없는 숫자의 경우 출력하지 않는다. 예를 들어 맨 위의 그림에서 1행 1열의 경우 2, 3, 7중 하나로 채울 수 있으며, 이 경우는 다음과 같이 출력되어야 한다.

해당 칸에 숫자가 채워져 있을 경우에는 해당 숫자만 출력하도록 한다.

 

Input

입력의 맨 첫 번째 줄에는 테스트 케이스의 개수 T ( 1 ≤ T ≤ 20 )가 입력된다.
그 다음 줄부터 T개의 테스트 케이스가 들어오며, 테스트 케이스간의 사이에는 줄 바꿈 글자가 입력된다.
 
하나의 테스트 케이스에 대한 입력은 총 9줄에 걸쳐서 입력되며, 각 줄은 0이상 9이하의 정수 9개로 구성된다. 숫자 사이에는 공백이 반드시 한 칸이 존재한다. 테스트 케이스의 위에서 i번째 줄의 왼쪽부터 j 번째 입력되는 숫자는 sudoku 퍼즐의 해당 칸에 채워진 숫자를 뜻하며 0일 경우는 해당 칸이 채워지지 않음을 의미한다. 올바르게 채워지지 않은 sudoku 퍼즐은 들어오지 않는다.

 

Output

입력에 대해 각 칸에 대해 아래의 예시같이 출력하도록한다. 숫자가 차 있는 숫자에 대응하는 칸의 경우에는 '*'문자로 해당 칸을 채우고 이 가운데에 채워진 숫자를 출력하고, 숫자가 차 있지 않았던 칸의 경우에는 가능한 후보 숫자들을 알맞게 출력한다.

Sample Input

Sample Output

2
0 0 8 0 1 0 0 0 9
6 0 1 0 9 0 3 2 0
0 4 0 0 3 7 0 0 5
0 3 5 0 0 8 2 0 0
0 0 2 6 5 0 8 0 0
0 0 4 0 0 1 7 5 0
5 0 0 3 4 0 0 8 0
0 9 7 0 8 0 5 0 6
1 0 0 0 6 0 9 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
+---+---+---+---+---+---+---+---+---+
|.23|.2.|***|.2.|***|.2.|...|...|***|
|...|.5.|*8*|45.|*1*|456|4.6|4.6|*9*|
|7..|7..|***|...|***|...|...|7..|***|
+---+---+---+---+---+---+---+---+---+
|***|...|***|...|***|...|***|***|...|
|*6*|.5.|*1*|45.|*9*|45.|*3*|*2*|4..|
|***|7..|***|.8.|***|...|***|***|78.|
+---+---+---+---+---+---+---+---+---+
|.2.|***|...|.2.|***|***|1..|1..|***|
|...|*4*|...|...|*3*|*7*|..6|..6|*5*|
|..9|***|..9|.8.|***|***|...|...|***|
+---+---+---+---+---+---+---+---+---+
|...|***|***|...|...|***|***|1..|1..|
|...|*3*|*5*|4..|...|*8*|*2*|4.6|4..|
|7.9|***|***|7.9|7..|***|***|..9|...|
+---+---+---+---+---+---+---+---+---+
|...|1..|***|***|***|..3|***|1.3|1.3|
|...|...|*2*|*6*|*5*|4..|*8*|4..|4..|
|7.9|7..|***|***|***|..9|***|..9|...|
+---+---+---+---+---+---+---+---+---+
|...|...|***|.2.|.2.|***|***|***|..3|
|...|..6|*4*|...|...|*1*|*7*|*5*|...|
|.89|.8.|***|..9|...|***|***|***|...|
+---+---+---+---+---+---+---+---+---+
|***|.2.|...|***|***|.2.|1..|***|12.|
|*5*|..6|..6|*3*|*4*|...|...|*8*|...|
|***|...|...|***|***|..9|...|***|7..|
+---+---+---+---+---+---+---+---+---+
|.23|***|***|12.|***|.2.|***|1.3|***|
|4..|*9*|*7*|...|*8*|...|*5*|4..|*6*|
|...|***|***|...|***|...|***|...|***|
+---+---+---+---+---+---+---+---+---+
|***|.2.|..3|.2.|***|.2.|***|..3|.23|
|*1*|...|...|.5.|*6*|.5.|*9*|4..|4..|
|***|.8.|...|7..|***|...|***|7..|7..|
+---+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+
|123|123|123|123|123|123|123|123|123|
|456|456|456|456|456|456|456|456|456|
|789|789|789|789|789|789|789|789|789|
+---+---+---+---+---+---+---+---+---+

Source

2010 Ajou University Programming Contest