문제1146--Sudoku

1146: Sudoku

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 104  통과: 50
[제출] [채점기록] [묻고답하기]

문제 설명

Sudoku란 9행 9열의 칸에 1이상 9이하의 아래의 규칙에 따라 숫자를 알맞게 채워넣는 게임이다.
규칙은 다음과 같다.
  • 각 행에는 1 부터 9 까지의 숫자가 하나씩 들어가야 한다.
  • 각 열에는 1 부터 9 까지의 숫자가 하나씩 들어가야 한다.
  • 굵은 테두리를 두른, 가로 세로 3칸인 작은 정사각형에도 1부터 9까지의 숫자가 하나씩 들어가야 한다.

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

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

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

 

입력 설명

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

 

출력 설명

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

입력 예시 Copy

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

출력 예시 Copy

+---+---+---+---+---+---+---+---+---+
|.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|
+---+---+---+---+---+---+---+---+---+

출처/분류