스도쿠
시간 제한1초메모리 제한256 MB
9x9 스도쿠 보드에서 빈 칸을 채워 각 행, 열, 3x3 박스에 1부터 9까지 숫자가 정확히 한 번씩 들어가도록 백트래킹으로 완성하는 문제입니다.
문제
스도쿠는 9x9 칸으로 이루어진 퍼즐이다. 일부 칸에는 1부터 9까지의 숫자가 미리 적혀 있고, 나머지 빈 칸을 규칙에 맞게 채워야 한다.
빈 칸을 채우는 규칙은 다음과 같다.
- 각 가로줄에는 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
- 각 세로줄에는 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
- 굵은 선으로 나뉜 각 3x3 정사각형에도 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
첫 번째 그림의 첫째 줄에는 1을 제외한 2부터 9까지의 숫자가 이미 있으므로, 첫째 줄의 빈 칸에는 1이 들어간다.
또 위쪽 가운데 3x3 정사각형에는 3을 제외한 숫자가 이미 있으므로, 가운데 빈 칸에는 3이 들어간다.
이렇게 모든 빈 칸을 채우면 다음과 같은 완성된 판을 얻을 수 있다.
게임 시작 전에 주어진 스도쿠 판을 규칙에 맞게 완성한 뒤 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 스도쿠 판의 현재 상태가 주어진다. 각 줄에는 9개의 정수가 공백으로 구분되어 주어지며, 스도쿠 판의 한 줄을 나타낸다. 이미 채워진 칸은 1부터 9까지의 숫자로, 빈 칸은 0으로 주어진다. 규칙에 맞게 완성할 수 없는 입력은 주어지지 않는다.
출력
완성된 스도쿠 판을 아홉 줄에 출력한다. 각 줄에는 9개의 숫자를 공백으로 구분해 출력한다.
완성하는 방법이 여러 가지라면 그중 하나만 출력하면 된다.
제한
입력은 항상 규칙에 맞게 완성할 수 있는 스도쿠 판이다.
기준 실행 시간은 다음과 같다.
- C++14: 80ms
- Java: 292ms
- PyPy3: 1172ms