스도쿠
시간 제한2초메모리 제한256 MB
주어진 9x9 스도쿠 퍼즐을 백트래킹으로 풀고, 해가 여러 개면 사전순으로 가장 작은 완성된 보드를 출력합니다.
문제
스도쿠는 9×9 격자를 채우는 숫자 퍼즐이다. 각 행, 각 열, 그리고 굵은 선으로 나뉜 9개의 3×3 격자에는 1부터 9까지의 숫자가 정확히 한 번씩 들어가야 한다.
일부 칸이 비어 있는 스도쿠가 주어진다. 빈칸을 모두 채워 완성된 스도쿠를 출력하시오.
입력
9개의 줄에 걸쳐 스도쿠 보드가 주어진다. 각 줄은 9개의 숫자로 이루어져 있으며, 아직 채워지지 않은 칸은 0으로 표시된다.
출력
완성된 스도쿠 보드를 9개의 줄에 출력한다. 답이 여러 개라면, 9개의 줄을 위에서부터 이어 붙여 만든 81자리 문자열이 사전순으로 가장 앞서는 답을 출력한다.
제한
- 입력은 제한 시간 안에 해결할 수 있는 스도쿠만 주어진다.
- 시간 제한: 2초
- 메모리 제한: 256 MB