가장 오래 걸리는 스도쿠

준이는 스도쿠를 풀려고 아래 코드를 작성했다.

#include <iostream>
using namespace std;
int a[10][10];
bool c[10][10];
bool c2[10][10];
bool c3[10][10];
int n = 9;
int cnt = 0;
int square(int x, int y) {
    return (x / 3) * 3 + (y / 3);
}
bool go(int z) {
    cnt += 1;
    if (cnt >= 10000000) {
        return true;
    }
    if (z == 81) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    int x = z / n;
    int y = z % n;
    if (a[x][y] != 0) {
        return go(z + 1);
    } else {
        for (int i = 1; i <= 9; i++) {
            if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x, y)][i] == 0) {
                c[x][i] = c2[y][i] = c3[square(x, y)][i] = true;
                a[x][y] = i;
                if (go(z + 1)) {
                    return true;
                }
                a[x][y] = 0;
                c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;
            }
        }
    }
    return false;
}
int main() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                c[i][a[i][j]] = true;
                c2[j][a[i][j]] = true;
                c3[square(i, j)][a[i][j]] = true;
            }
        }
    }
    go(0);
    return 0;
}

함수 go를 호출할 때마다 변수 cnt가 1씩 증가한다. cnt가 $10000000$ 이상이 되면 탐색을 멈추고 참을 반환한다.

원래 과제에서는 cnt가 가장 커지는 스도쿠 퍼즐을 출력했고, 점수는 cnt에 저장된 값이었다. 이 문제에서는 출력을 하나로 고정한다. 출력해야 하는 퍼즐은 유일하게 정해져 있다.

풀 수 없는 퍼즐을 출력하면 오답이다.

이 문제는 입력이 없다.

아홉 줄에 스도쿠 퍼즐을 출력한다. 빈 칸은 0이다. 각 줄은 공백으로 구분한 아홉 개의 정수이다.

출력은 다음 아홉 줄이어야 한다.

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0