스도쿠

스도쿠는 9x9 칸으로 이루어진 퍼즐이다. 일부 칸에는 1부터 9까지의 숫자가 미리 적혀 있고, 나머지 빈 칸을 규칙에 맞게 채워야 한다.

빈 칸을 채우는 규칙은 다음과 같다.

1. 각 가로줄에는 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
2. 각 세로줄에는 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
3. 굵은 선으로 나뉜 각 3x3 정사각형에도 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.

첫 번째 그림의 첫째 줄에는 1을 제외한 2부터 9까지의 숫자가 이미 있으므로, 첫째 줄의 빈 칸에는 1이 들어간다.

또 위쪽 가운데 3x3 정사각형에는 3을 제외한 숫자가 이미 있으므로, 가운데 빈 칸에는 3이 들어간다.

이렇게 모든 빈 칸을 채우면 다음과 같은 완성된 판을 얻을 수 있다.

게임 시작 전에 주어진 스도쿠 판을 규칙에 맞게 완성한 뒤 출력하는 프로그램을 작성하시오.

아홉 줄에 스도쿠 판의 현재 상태가 주어진다. 각 줄에는 9개의 정수가 공백으로 구분되어 주어지며, 스도쿠 판의 한 줄을 나타낸다. 이미 채워진 칸은 1부터 9까지의 숫자로, 빈 칸은 0으로 주어진다. 규칙에 맞게 완성할 수 없는 입력은 주어지지 않는다.

완성된 스도쿠 판을 아홉 줄에 출력한다. 각 줄에는 9개의 숫자를 공백으로 구분해 출력한다.

완성하는 방법이 여러 가지라면 그중 하나만 출력하면 된다.

입력은 항상 규칙에 맞게 완성할 수 있는 스도쿠 판이다.

기준 실행 시간은 다음과 같다.

• C++14: 80ms
• Java: 292ms
• PyPy3: 1172ms