백준[2239, 2580] 스도쿠

문제 설명

문제 링크

http://icpc.me/2239

2239번: 스도쿠

풀이

2239번과 2580번이 아예 똑같은 문제인데 왜 두 문제가 있는지는 잘 모르겠다.

한번 풀고 복습까지 하라는 백준님의 말씀이실지도...

이 문제는 백트레킹을 사용하여 풀 수 있다.

모든 행, 열, 박스들에 무슨 수가 들어있는지 미리 저장해 두고 빈칸에 백트레킹을 하며 1~9까지 넣어보면 된다.

row [n][k] : n열에 숫자 k가 있다는 의미이다. 

그리고 끝까지 도달하면 출력을 하고 더 이상 백트레킹을 멈춰야 최솟값인 결과 하나만 나온다. 이때 백트레킹을 멈추기 위해 그냥 return을 사용하면 멈추지 않는다. 그렇기 때문에 exit()을 이용하여 프로그램을 종료시켜야 한다.

만약 백트래킹을 멈추지 않는다면 가능한 모든 채울 수 있는 경우의 수가 출력될 것이다.

코드

#include <cstdio>
#include <cstdlib>

int arr[10][10];
bool row[10][10], col[10][10], box[10][10];

void solve(int y, int x) {
    if (y == 9 && x == 0) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) printf("%d", arr[i][j]);
            printf("\n");
        }
        exit(0);
    }
    if (!arr[y][x]) {
        for (int i = 1; i <= 9; i++) {
            if (row[y][i] || col[x][i] || box[(y / 3) * 3 + x / 3][i]) continue;
            row[y][i] = true;
            col[x][i] = true;
            box[(y / 3) * 3 + x / 3][i] = true;
            arr[y][x] = i;
            solve(y + (x + 1) / 9, (x + 1) % 9);
            row[y][i] = false;
            col[x][i] = false;
            box[(y / 3) * 3 + x / 3][i] = false;
            arr[y][x] = 0;
        }
    } else {
        solve(y + (x + 1) / 9, (x + 1) % 9);
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%1d", &arr[i][j]);
            row[i][arr[i][j]] = true;
            col[j][arr[i][j]] = true;
            box[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
        }
    }
    solve(0, 0);
}