스도쿠

시간 제한3초메모리 제한128 MB

요약

16x16 스도쿠 퍼즐에서 각 행, 열, 4x4 박스가 A부터 P까지 정확히 한 번씩 나오도록 빈칸을 채워 완성된 보드를 출력합니다.

난이도: 보통10점 중 6점
유형: 백트래킹, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

$16 \times 16$ 크기의 스도쿠 보드가 주어진다. 각 행, 각 열, 그리고 $4 \times 4$ 크기의 작은 보드 $16$ 개마다 알파벳 대문자 A부터 P까지가 중복 없이 정확히 한 번씩 나타나도록 보드를 모두 채워야 한다.

스도쿠의 초기 상태가 주어졌을 때, 완성된 보드를 출력하는 프로그램을 작성하시오. 입력으로는 항상 정답이 정확히 하나인 경우만 주어진다.

원본 그림에서 왼쪽 그림은 스도쿠의 초기 상태를, 오른쪽 그림은 스도쿠를 푼 상태를 나타낸다.

입력

스도쿠 퍼즐의 초기 상태가 주어진다. $16$ 개의 줄에 각각 $16$ 개의 문자가 주어진다. 각 문자는 채워진 칸을 나타내는 A부터 P까지의 대문자이거나, 빈 칸을 나타내는 -이다.

출력

완성된 스도쿠 퍼즐을 $16$ 개의 줄에 각각 $16$ 개의 문자로 출력한다.

예제1

예제 1

입력

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-

예상 출력

FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK