PKU 3074. Sudoku

스도쿠

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5294		Accepted: 1578

설명

스도쿠에서는 9 × 9 크기의 격자가 3 × 3 크기의 더 작은 격자들로 나뉘어져있습니다. 예를 들면,

.	2	7	3	8	.	.	1	.
.	1	.	.	.	6	7	3	5
.	.	.	.	.	.	.	2	9
3	.	5	6	9	2	.	8	.
.	.	.	.	.	.	.	.	.
.	6	.	1	7	4	5	.	3
6	4	.	.	.	.	.	.	.
9	5	1	8	.	.	.	7	.
.	8	.	.	6	5	3	4	.

격자 안에 몇몇개의 숫자가 주어졌을 때,  당신은 남은 칸들에 1부터 9까지의 숫자들을 집어넣어야 하는데 이때 1부터 9까지의 각 숫자들은 (1) 9개의 3 × 3 격자 안에 1개씩, (2) 9개의 가로 줄 안에 1개씩, (3) 9개의 세로 줄 안에 1개씩 들어가야 합니다.

입력

테스트 파일의 입력은 복수의 테스트 케이스들로 구성될 수 있습니다. 각 테스트 케이스는 81개의 문자를 한 줄로 나타내는데 이것은 스도쿠 격자의 81개의 칸을 나타내며, 위에서부터 가로 한 줄씩 표기합니다. 각 문자는 1부터 9까지의 숫자 혹은 채워지지 않은 칸을 나타내는 점으로 나타냅니다. 입력된 스도쿠에 대해 단 하나의 정답만이 존재한다는 것을 명심하세요. 파일의 끝을 표기할 때는 한 줄에 “end” 라고 입력하시면 됩니다.

출력

각 테스트 케이스에 대해, 완성된 스도쿠 퍼즐을 한 줄로 출력하시면 됩니다.

입력 예시

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

출력 예시

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

Stanford Local 2006