크로스 해칭으로 스도쿠 풀기

스도쿠는 가로 9칸, 세로 9칸으로 이루어진 표에 1부터 9까지의 숫자를 채우는 퍼즐이다. 각 행과 열, 그리고 각 3x3 작은 격자에는 1부터 9까지의 숫자가 한 번씩만 들어가야 한다.

이 문제에서는 여러 풀이 방법 중 크로스 해칭만 사용할 수 있다. 크로스 해칭은 숫자 하나를 고른 뒤, 그 숫자가 이미 들어 있는 행, 열, 3x3 격자를 제외하는 방법이다. 어떤 3x3 격자에서 그 숫자를 놓을 수 있는 빈 칸이 정확히 하나라면, 그 칸에 숫자를 채운다.

부분적으로 채워진 스도쿠 퍼즐이 주어진다. 더 이상 이 방법으로 채울 수 없을 때까지 크로스 해칭만 반복해서 적용한 결과를 출력하라. 다른 방법으로 빈 칸을 채우면 안 된다.

입력으로 주어지는 퍼즐이 처음부터 스도쿠 규칙을 어기거나, 어떤 행, 열, 3x3 격자에서 필요한 숫자를 놓을 수 있는 칸이 하나도 없는 모순 상태일 수 있다. 이런 경우도 판별해야 한다.

입력은 9개의 줄로 이루어진다. 각 줄은 9개의 문자로 이루어져 있으며, 각 문자는 1부터 9까지의 숫자 또는 .이다. 마침표는 아직 채워지지 않은 빈 칸을 뜻한다.

퍼즐이 스도쿠 규칙을 지키고 모순이 없다면, 입력과 같은 9줄 형식으로 크로스 해칭만 적용한 결과를 출력한다. 그렇지 않다면 ERROR를 출력한다.