스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이란 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다.
이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
또한 위쪽 가운데 위치한 3×3 정사각형의 경우에는 3 을 제외한 나머지 숫자들이 이미 쓰여 있으므로 가운데 빈 칸에는 3 이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
입력 035469278 782105609 060278135 321046897 804913506 596820413 917652080 603701952 258394761 출력 135469278 782135649 469278135 321546897 874913526 596827413 917652384 643781952 258394761
출처:southeastern Europe 2005■ 2014.11.25 일 sj 가 잘못되어 수정 했습니다