시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 5 4 30.769%

문제

스도쿠는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 퍼즐을 푸는 방법은 각 가로줄과 세로줄에 1에서 9까지의 숫자를 한 번만 넣고, 3*3칸의 작은 격자에도 1에서 9까지의 숫자를 겹치지 않게 넣어야 한다.

스도쿠를 푸는 방법에는 여러가지 방법이 있다. 그 중 한가지 방법은 Cross-hatching이다.

Cross-hatching방법을 이용할 때는, 먼저 숫자를 하나 골라야 한다. 그런 뒤에, 그 숫자가 등장하는 가로줄이나 세로줄 또는 3*3 박스에 선을 긋는다. 이렇게 선을 그었을 때, 3*3박스에 고른 숫자가 들어갈 수 있는 칸이 한 칸일 때, 그 숫자를 채우는 것이다.

아래 그림 중 왼쪽 그림은 매우 조금만 숫자가 채워진 스도쿠이고, 오른쪽 그림은 cross-hatching 방법을 이용해서 4가 들어갈 수 있는 곳을 찾은 한가지 예이다.

부분적으로 숫자가 채워진 스도쿠 퍼즐이 주어졌을 때, cross-hatching방법만을 이용해서 스도쿠를 푸는 프로그램을 작성하시오. 더이상 이 방법을 이용해서 풀 수 없을 때 까지 스도쿠를 풀어야 한다. 다른 방법을 이용하면 안된다.

입력으로 주어지는 스도쿠 퍼즐이 규칙을 지키지 않는 경우가 입력으로 주어질 수 있다. (예, 한 가로줄에 1이 2개 있는 경우, 숫자 1이 어떤 가로줄, 3*3박스, 세로줄에 있을 수 있는 곳이 전혀 없는 경우) 이런 경우도 판별해야 한다.

입력

입력은 9개줄로 이루어지며, 각 줄은 9개 문자로 이루어져 있다. 문자는 1~9 숫자 또는 '.'이다. 마침표는 빈 칸을 나타낸다.

출력

올바른 스도쿠 퍼즐이고, 모순이 일어나지 않는다면, 입력과 같은 형식으로 cross-hatching만을 이용해서 푼 결과를 출력한다. 그렇지 않다면 "ERROR"를 출력한다. (쌍따옴표는 출력하지 않는다)

예제 입력

..9......
.....4...
.......4.
.........
.4.......
.........
.........
.........
.........

예제 출력

4.9......
.....4...
.......4.
.........
.4.......
.........
.........
.........
.........

힌트