2239번 스도쿠

https://www.acmicpc.net/problem/2239

풀이: 스도쿠 퍼즐 해결을 위한 백트래킹 접근 방식

스도쿠 문제는 9x9 격자판에 숫자를 채워넣는 전형적인 제약 만족(Constraint Satisfaction) 문제로, 백트래킹(Backtracking) 알고리즘을 사용하여 효과적으로 해결할 수 있습니다. 백트래킹은 해를 찾기 위해 모든 가능한 경우의 수를 탐색하는 방법으로, 특정 시점에서 해가 될 수 없다고 판단되면 즉시 이전 상태로 돌아가 다른 경로를 탐색합니다.

백트래킹(Backtracking) 접근 방식:

1. 상태 정의: 스도쿠 보드 board[9][9]와 각 행, 열, 3x3 박스에 어떤 숫자가 사용되었는지 추적하기 위한 비트마스크 배열 usedInRow[9], usedInCol[9], usedInBox[9]를 사용합니다. isFind 변수는 해를 찾았는지 여부를 나타냅니다.
2. 재귀 함수 sudoku(board, x, y): 현재 (x, y) 위치에 숫자를 채우는 함수입니다. x는 행 인덱스, y는 열 인덱스를 의미합니다.
3. 종료 조건:
   • 만약 isFind가 true이면 (이미 해를 찾은 경우), 더 이상 탐색할 필요가 없으므로 즉시 함수를 종료합니다.
   • 현재 열 y가 9에 도달하면 다음 행(x++)으로 이동하고 y를 0으로 초기화합니다.
   • 현재 행 x가 9에 도달하면 (모든 칸을 채운 경우), isFind를 true로 설정하고 함수를 종료하여 백트래킹을 멈춥니다.
4. 이미 채워진 칸 처리: board[x][y]가 0이 아니면 (이미 숫자가 채워져 있다면), 이 칸은 건너뛰고 다음 칸 (x, y+1)에 대해 재귀 호출합니다.
5. 숫자 채우기 시도: board[x][y]가 0인 경우, 1부터 9까지의 숫자를 반복문으로 시도합니다.
   • 각 숫자 i에 대해 usedInCol[y], usedInRow[x], usedInBox[(x/3)*3 + y/3] 비트마스크를 확인하여 i가 현재 행, 열, 3x3 박스에 사용되지 않았는지 검사합니다.
   • !(usedInCol[y] & (1<<i))는 y열에 i가 사용되지 않았음을, !(usedInRow[x] & (1<<i))는 x행에 i가 사용되지 않았음을, !(usedInBox[(x/3)*3 + y/3] & (1<<i))는 해당 3x3 박스에 i가 사용되지 않았음을 의미합니다.
   • 만약 i가 유효한 숫자라면:
     • board[x][y]에 i를 채웁니다.
     • 해당 비트마스크에 i가 사용되었음을 표시합니다 (|= (1<<i)).
     • 다음 칸 (x, y+1)에 대해 sudoku 함수를 재귀 호출합니다.
6. 백트래킹: 재귀 호출 후 isFind가 true가 아니라면, 현재 경로에서 해를 찾지 못했거나 불가능하다는 의미이므로, board[x][y]를 0으로 되돌리고 해당 비트마스크에서 i 사용 표시를 해제합니다 (&= ~(1<<i)). 이는 이전 상태로 돌아가 다른 숫자를 시도하기 위함입니다.

시간 복잡도

스도쿠 문제의 시간 복잡도는 탐색 공간의 크기에 따라 결정됩니다. 최악의 경우, 모든 빈 칸에 대해 1부터 9까지의 숫자를 시도해야 할 수 있습니다. 9x9 스도쿠에서 빈 칸의 최대 개수는 81개이므로, 이론적으로는 $O(9^{N^2})$ (여기서 N=9)와 같이 매우 큰 지수적 복잡도를 가집니다. 즉, $O(9^{81})$ 입니다.

하지만 실제 스도쿠 문제에서는 제약 조건(행, 열, 박스에 중복 숫자 불가)이 강력하여 많은 경로가 빠르게 가지치기(pruning)됩니다. 따라서 실제 실행 시간은 이보다 훨씬 빠르지만, 여전히 본질적으로는 지수적 복잡도를 가집니다.

공간 복잡도

• board 배열: $O(N^2)$ (여기서 N=9이므로 $O(81)$)
• usedInCol, usedInRow, usedInBox 배열: 각각 $O(N)$ (여기서 N=9이므로 $O(9)$)
• 재귀 호출 스택: 최대 깊이는 빈 칸의 개수와 같으므로 최악의 경우 $O(N^2)$ (여기서 N=9이므로 $O(81)$)

코드

2239.cpp

#include <bits/stdc++.h>
using namespace std;
auto usedInCol = array<int, 9>();
auto usedInRow = array<int, 9>();
auto usedInBox = array<int, 9>();
bool isFind = false;
void sudoku(array<array<int, 9>, 9>& board, int x, int y){
    if(isFind)
        return;
    if(y == 9){
        x++;
        y = 0;
    }
    if(x == 9){
        isFind = true;
        return;
    }
    if(board[x][y] != 0){
        sudoku(board, x, y+1);
        return;
    }
    for(int i = 1;i<10;i++){
        if(!(usedInCol[y] & (1<<i)) && !(usedInRow[x] & (1<<i)) && !(usedInBox[(x/3)*3 + y/3] & (1<<i))){
            board[x][y] = i;
            usedInBox[(x/3)*3 + y/3] |= (1<<i);
            usedInRow[x] |= (1<<i);
            usedInCol[y] |= (1<<i);
            sudoku(board, x, y+1);
            if(isFind)
                return;
            board[x][y] = 0;
            usedInBox[(x/3)*3 + y/3] &= ~(1<<i);
            usedInRow[x] &= ~(1<<i);
            usedInCol[y] &= ~(1<<i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto board = array<array<int, 9>, 9>();
    string s;
    for(int i = 0; i < 9; i++){
        cin >> s;
        for(int j = 0; j < 9; j++){
            board[i][j] = s[j] - '0';
            if(board[i][j] != 0){
                usedInCol[j] |= (1<<board[i][j]);
                usedInRow[i] |= (1<<board[i][j]);
                usedInBox[(i/3)*3 + j/3] |= (1<<board[i][j]);
            }
        }
    }
    sudoku(board, 0, 0);
    for(const auto& c: board){
        for(const auto& e: c){
            cout << e;
        }
        cout << '\n';
    }
    return 0;
}

Standard Input (stdin): 003020600 900305001 001806400 008102900 700000008 006708200 002609500 800203009 005010300

⏳ Running... C++