문제

#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;
}

아이디어

문제에서 주어진 코드는 스도쿠에서 좌상단부터 1~9까지 차례로 대입하는 백트래킹을 이용해서 스도쿠 문제를 풀어내고 있다. 따라서 좌상단부터 높은 숫자들로 채워준다면 높은 cnt값을 유도할 수 있다.
우선 좌상단에서부터 시작해 큰 숫자를 입력하며 완성된 스도쿠 판을 만들어준다.

이후 적절한 위치의 값들을 0으로 바꿔주며 정답을 제출해본다. 이 때, 너무 많거나 적은 위치의 숫자를 비워둔다면 오답이 나올 수 있으니 제출 결과에 따라 조정해주자.

소스코드

0 0 0 0 0 4 3 0 0
0 0 0 3 0 0 0 0 0
0 2 1 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0
0 0 0 0 4 0 1 3 2
0 0 0 2 1 3 0 0 0
1 0 2 0 0 0 0 0 0

채점결과