Cross

스도쿠 게임의 목표는 \(9 \times 9\) 격자에 \(1\) 이상 \(9\) 이하의 정수를 채워, 각 행, 각 열, 그리고 아홉 개의 \(3 \times 3\) 상자 각각에 아홉 개의 수가 모두 들어가게 하는 것이다. 시작 보드는 나머지 칸의 값을 논리적으로 추론할 수 있도록 부분적으로 채워져 있다. 스도쿠 퍼즐의 난이도는 다양하며, 가장 어려운 퍼즐을 풀려면 복잡한 분석 기법이 필요하다. 하지만 이 문제에서는 가장 단순한 기법 중 하나인 크로스해칭(cross-hatching)을 구현한다.

크로스해칭에서는 아홉 개의 수 중 하나를 골라, 그 수가 격자에 나타나는 각 위치에 대해 해당 행, 열, \(3 \times 3\) 상자를 지운다. 그런 다음 그 수를 놓을 수 있는 자리가 하나뿐인 \(3 \times 3\) 상자를 찾아 그 자리에 수를 놓는다.

부분적으로 채워진 격자가 주어진다. 여러분의 과제는 어떤 수에 대해서도 더 이상 추론할 수 없을 때까지, 여러 수에 대해 크로스해칭 기법을 반복해서 적용하는 것이다.

격자의 초기 배치는 유효하지 않을 수도 있다. 또한 어떤 \(3 \times 3\) 상자에서 어떤 수를 놓을 수 있는 칸이 없을 수도 있다. 두 경우 모두 오류를 보고해야 한다.

입력은 \(9\)개의 줄로 이루어지며, 각 줄에는 정확히 \(9\)개의 문자가 있다. 각 문자는 \(1\) 이상 \(9\) 이하의 숫자이거나, 빈 칸을 나타내는 마침표(.)이다.

입력이 유효하고 푸는 동안 모순이 없으면, 크로스해칭으로 값을 추론할 수 있는 칸을 채워서 격자를 입력과 같은 형식으로 출력한다. 그렇지 않으면 "ERROR"(따옴표는 표기의 명확성을 위한 것)를 출력한다.
Contest #3, \(13^{th}\) December 2008

riseoj 작성

출처 COCI 2008/2009 Contest 3