[C/C++] 백준 #2580 스도쿠 (백트래킹)

스도쿠는 머리를 많이 사용하는 퍼즐로 유명합니다.

기본적으로 문제를 풀기 위해서 여러가지 경우를 머리속에 담고서 진행해야 하기 때문에 쉽게 풀지를 못 하지만,

컴퓨터 프로그램의 경우는 모든 경우를 살펴볼 수 있는 알고리즘 중 대표적인 백트래킹으로 이 문제를 손쉽게 풀 수 있습니다.

 

대중교통을 이용해서 여행을 다닐 때, 버스 터미널 등에서 손쉽게 살 수 있는 스도쿠 문제지가 있었죠.  지금은 귀찮아서라도 잘 안 풀게 되지만요.

 

sudoku

 

백준 사이트에서 문제는 다음과 같습니다.

 

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

2580번: 스도쿠

 

백트래킹 알고리즘은 재귀함수를 이용하여 문제를 해결하는 가장 기초적인 방법을 담고 있습니다.  기본은 깊이우선탐색과 비슷하지만, 다른 점은 조건을 검사해서 조건을 통과하지 않으면 바로 이전단계로 돌아간다는 것입니다.  이 과정이 없다면, 매우 많은 상태를 순회해야 하기 때문에 매우 오랜시간이 걸리게 됩니다.  빈 숫자가 10개만 되어도 순회해야할 것들은 무려 34억가지가 넘으니까요.  빈칸이 몇개이면 프로그램적으로도 많은 시간이 걸리지 않겠지만요.

 

그래서 조건검사하는 것이 가장 중요하며, 조건을 검사하기 위해서는 효율적인 검사방법을 사용해야 합니다.  저는 비트플래그를 사용했는데, 비트플래그는 사용된 숫자를 비트 하나씩 할당해서 기록하는 방식입니다.  1이 사용되었다면, 최하위비트를 1로 설정하고, 2가 사용되었다면, 두번째 하위비트를 1로 설정합니다.  스도쿠는 가로 9줄, 세로 9줄, 그리고 3x3 블럭이 9개 있습니다.  이것들을 각각 비트플래그 변수 하나씩에 할당하면 총 27개의 비트플래그 변수가 있으면 됩니다.  검사하는 방법도 쉽고, 손쉽게 클리어할 수 있는 장점이 있습니다.  만약 비트 플래그를 사용하는 것이 싫으면, 9개의 불린자료를 가지고 있는 배열을 사용해도 무방합니다.

 

제가 작성한 소스입니다.

//--------------------------------------------------------------------
//    baekjoon #2580 - Sudoku
//        - by Aubrey Choi
//        - created at 2019-06-15
//--------------------------------------------------------------------
#include <stdio.h>

const int d[9] = {0, 1, 2, 9, 10, 11, 18, 19, 20};
bool check(int sudoku[], int s, int v)
{
    int r = s / 9, i;
    for(i = r * 9; i < r * 9 + 9; i++)
    {
        if(i != s && sudoku[i] == v) return false;
    }
    int c = s % 9;
    for(i = c; i < 81; i += 9)
    {
        if(i != s && sudoku[i] == v) return false;
    }
    r = (r / 3) * 3; c = (c / 3) * 3;
    for(i = 0; i < 9; i++)
    {
        if((r*9+c+d[i]) != s && sudoku[r*9+c+d[i]] == v) return false;
    }
    return true;
}

bool solve(int sudoku[], int cand[], int mask[], int c, int n)
{
    if(c == n) return true;
    int s = cand[c], i;
    if(sudoku[s] != 0) return solve(sudoku, cand, mask, c + 1, n);
    for( i = 1; i <= 9; i++)
    {
        if(mask[c] & (1 << i)) continue;
        if(!check(sudoku, s, i)) continue;
        sudoku[s] = i;
        if(solve(sudoku, cand, mask, c + 1, n)) return true;
        sudoku[s] = 0;
    }
    return false;
}

int main()
{
    int sudoku[81], s, r, c, cand[81], mask[81], n = 0, i, j;
    for(i = 0; i < 81; i++)
    {
        scanf("%d", &s);
        sudoku[i] = s;
        if(!s) { cand[n] = i; mask[n] = 0; n++; }
    }
    for(i = 0; i < n; i++)
    {
        s = cand[i];
        r = s / 9;
        for(j = r*9; j < r*9+9; j++) mask[i] |= 1<<sudoku[j];
        c = s % 9;
        for(j = c; j < 81; j += 9) mask[i] |= 1 << sudoku[j];
        r = (r / 3) * 3;
        c = (c / 3) * 3;
        for(j = 0; j < 9; j++) mask[i] |= 1 << sudoku[r * 9 + c + d[j]];
        c = 0;
        for(j = 1; j <= 9; j++)
        {
            if(mask[i] & (1 << j)) c++;
            else r = j;
        }
        if(c == 8) { sudoku[s] = r; mask[i] = 0x3ff; }
    }
    solve(sudoku, cand, mask, 0, n);
    for(i = 0; i < 81; i++)
    {
        printf("%d ", sudoku[i]);
        if(i % 9 == 8) putchar('\n');
    }
}