스도쿠는 일반적으로 $n$ 개의 $\sqrt{n} \times \sqrt{n}$ 크기 격자로 구성된 $n$ 궁 격자판에서 진행됩니다.
모든 행과 모든 열에는 $1$부터 $n$까지의 숫자가 하나씩 포함되어야 하며, 중복되거나 빠져서는 안 됩니다. 각 궁(굵은 선으로 둘러싸인 영역, 일반적으로 $\sqrt{n} \times \sqrt{n}$ 크기) 또한 $1$부터 $n$까지의 숫자를 하나씩 포함해야 하며, 중복되거나 빠져서는 안 됩니다. 스도쿠를 완성하려면 이 세 가지 조건을 동시에 만족해야 합니다.
그림은 $n=9$인 스도쿠의 예시입니다.
불완전한 스도쿠 문제가 주어지면, 임의의 개수의 숫자를 채워 넣어 완성된 스도쿠가 정확히 두 개의 해, 즉 유이한 해(唯二解)를 갖도록 만들어야 합니다. 또한, 이러한 모든 채우기 방법 중에서 두 해의 차이가 최대가 되도록 해야 합니다. 여기서 차이란 두 해를 각 셀별로 비교했을 때 서로 다른 숫자가 적힌 셀의 개수로 정의합니다.
동시에, 스도쿠 내의 임의의 두 위치에 대하여, 두 유이한 해의 첫 번째 위치에 있는 숫자를 각각 $x_1, x_2$라 하고, 두 번째 위치에 있는 숫자를 각각 $y_1, y_2$라 할 때, $x_1\not=x_2, y_1\not=y_2, x_1\not=y_2, x_1 \not = y_1$ 조건을 동시에 만족하지 않습니다.
입력
첫 번째 줄에 스도쿠의 크기를 나타내는 정수 $n$이 주어집니다.
다음 $n$ 줄에는 각각 $n$ 개의 정수 ${a_i}_j$가 주어지며, 이는 불완전한 스도쿠 판을 나타냅니다. $0$은 숫자가 채워지지 않은 빈칸을 의미합니다.
출력
$n$ 줄에 걸쳐 $n$ 개의 정수를 출력하여 완성된 판을 나타냅니다. 유이한 해의 차이가 최대가 되는 채우기 방법이 여러 가지라면 그중 아무거나 출력해도 됩니다.
예제
입력 1
4 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 3
출력 1
3 0 0 0 0 0 0 2 0 3 0 0 2 0 0 3
참고
예제 출력에 대응하는 유이한 해는 다음과 같습니다:
3 2 1 4 1 4 3 2 4 3 2 1 2 1 4 3
와:
3 2 4 1 4 1 3 2 1 3 2 4 2 4 1 3
하나씩 비교하면 차이는 $8$이며, 이것이 해당 문제에서 차이가 최대값인 $8$에 도달하는 방법 중 하나임을 증명할 수 있습니다.
제한
| 서브태스크 번호 | 데이터셋 번호 | 점수 | 데이터 범위 | 추가 제한 |
|---|---|---|---|---|
| 1 | 1 | 8 | $n=4$ | 없음 |
| 1 | 11 | 8 | $n=4$ | 없음 |
| 1 | 12 | 8 | $n=4$ | 없음 |
| 1 | 13 | 8 | $n=4$ | 없음 |
| 2 | 2 | 6 | $n=9$ | 초기에 주어진 숫자 개수 $0$ |
| 2 | 3 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 4 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 5 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 6 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 7 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 8 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 9 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 2 | 10 | 6 | $n=9$ | 판에 주어진 $0$이 아닌 숫자가 최대 $11$개 |
| 3 | 14 | 7 | $n=16$ | 초기에 주어진 숫자 개수 $0$ |
| 4 | 15 | 7 | $n=16$ | 판에 주어진 $0$이 아닌 숫자가 최대 $20$개 |
서브태스크 1의 시간 제한은 2초이며, 그 외의 시간 제한은 30초입니다.
모든 데이터에 대하여: $a_{i,j} \in [0,n]$이며, 주어진 불완전한 스도쿠 판은 유이한 해를 갖도록 채울 수 있는 방법이 적어도 하나 존재함이 보장됩니다.
테스트 케이스 14
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
테스트 케이스 15
16 0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 7 0 0 7 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 8 0 0 0 12 11