Time Limit: 1s
Memory Limit: 128MB
주어진 Triple sum 스도쿠 판의 빈 칸을 채워보자.
Triple sum 스도쿠:
1. 모든 가로줄에 1에서 9까지의 수가 전부 있어야 한다.
2. 모든 세로줄에 1에서 9까지의 수가 전부 있어야 한다.
3. 가로와 세로를 각각 3등분씩하여 나눠진 모든 3*3 작은 정사각형에 1에서 9까지의 수가 전부 있어야 한다.
4. 각 가로줄에 Triple sum 이 주어진다.
* Triple sum: 가로줄의 1~4번째 수로 만든 네 자리수 + 가로줄의 5~7번째 수로 만든 세 자리 수 + 가로줄의 8~9번째 수로 만든 두 자리 수
예를 들어 빈 칸이 없는 Triple sum 스도쿠의 예시는 다음과 같다.
| 6444 | 5 | 6 | 8 | 2 | 7 | 4 | 9 | 1 | 3 | 5682+749+13 = 6444 |
| 4104 | 3 | 4 | 2 | 1 | 5 | 9 | 6 | 8 | 7 | 3421+596+87 = 4104 |
| 2394 | 1 | 9 | 7 | 8 | 3 | 6 | 2 | 5 | 4 | 1978+362+54 = 2394 |
| 7146 | 6 | 8 | 5 | 3 | 2 | 1 | 4 | 7 | 9 | 6853+214+79 = 7146 |
| 8262 | 7 | 3 | 4 | 9 | 8 | 5 | 1 | 6 | 2 | 7349+851+62 = 8262 |
| 2709 | 2 | 1 | 9 | 6 | 4 | 7 | 5 | 3 | 8 | 2196+475+38 = 2709 |
| 9495 | 9 | 2 | 6 | 7 | 1 | 8 | 3 | 4 | 5 | 9267+183+45 = 9495 |
| 9477 | 8 | 5 | 1 | 4 | 9 | 3 | 7 | 2 | 6 | 8514+937+26 = 9477 |
| 5454 | 4 | 7 | 3 | 5 | 6 | 2 | 8 | 9 | 1 | 4735+628+91 = 5454 |
Line 1~9: Triple sum 스도쿠 판이 한 줄에 10개씩 9줄로 주어진다. (각 가로줄의 가장 왼쪽에 있는 수는 Triple sum이며, 나머지는 0~9 사이의 수가 주어진다. 이 때 0은 빈 칸을 의미한다.)
Line 1~9: Triple sum 스도쿠 판의 빈 칸을 채운 답을 출력한다.
9477 0 0 0 0 0 0 0 0 0 3474 0 0 0 0 0 0 0 0 0 7074 0 0 0 0 0 0 0 0 0 5202 0 0 0 0 0 0 0 0 0 2646 0 0 0 0 0 0 0 0 0 6048 0 0 0 0 0 0 2 0 0 4203 0 0 0 0 0 0 0 0 0 7812 0 0 0 0 0 0 0 0 0 9549 0 0 0 0 0 0 0 0 0
9 1 3 4 2 7 5 6 8 2 5 4 6 8 3 1 9 7 6 8 7 9 1 5 3 4 2 4 7 9 1 3 2 6 8 5 1 6 2 5 9 8 7 3 4 5 3 8 7 6 4 2 1 9 3 4 5 8 7 1 9 2 6 7 2 6 3 4 9 8 5 1 8 9 1 2 5 6 4 7 3
* 이 문제를 풀기 위해서는 백트래킹을 알아야 하지만 백트래킹은 컴퓨터프로그래밍1에서는 다루지 않으므로 아직 못푸셔도 괜찮습니다.