스도쿠 풀이 알고리즘 (feat. dlx)

운영체제 프로젝트 1은 스도쿠 푸는 프로그램을 작성하는 과제였다. 운영체제 수업에서 왜 스도쿠를 푸는지는 잘 모르겠으나.. 프로젝트를 하면서 많은 것을 배우게 되었으니 정리해본다.

 

스도쿠는 단 한 가지의 정답만 가져야 한다는 있다는 말도 있는데, 꼭 필요한 조건은 아니라고 생각한다.

물론 손으로 풀 때 답이 여러가지이면 굉장히 열받겠지만, 진정한 프로그램이면 어떠한 경우에서도 해답을 찾아낼 수 있어야 한다고 생각한다.

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

참고로 백준 스도쿠 문제의 테스트 케이스 중에도 스도쿠 판을 채우는 방법이 여럿인 경우가 있다고 명시되어 있다.

 

답이 유일한 스도쿠를 찾는다면, http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php에 숫자가 17개만 들어있는 답이 유일한 스도쿠 문제 49151개가 있다.

 

 

기본적인 스도쿠 풀이 전략

스도쿠를 한 번이라도 풀어본 사람이라면 기본적으로 스도쿠를 어떻게 접근해야 하는지는 잘 알 것이다.

사실 우리가 암묵적으로 쓰는 전략들은 스도쿠 매니아들에 의해, 전부 각자의 이름을 가지고 있다.

대표적으로 사용하는 전략은 다음과 같다.

가장 흔하게 볼 수 있는 상황. 3이 들어갈 자리는 첫 번째 상자의 (3, 3)밖에 없다. 이러한 상황을 hidden single이라고 한다.

 

또 하나의 흔하게 볼 수 있는 상황. 동그라미 친 부분에는 1~8은 들어갈 수 없으므로 9일 수밖에 없다. 이러한 상황을 naked single이라고 한다.

 

그 외에 intersection, naked pair, x-wing 등 여러 가지 고급 전략들이 존재하지만, 자주 등장하는 상황은 아니며 구현이 복잡하고 시간이 많이 소요되기 때문에 생략하도록 한다.

다양한 전략은 https://blog.naver.com/dydrogud22/220697379898에 잘 정리되어 있다.

 

이러한 전략을 컴퓨터로 구현하려면, 스도쿠의 각 81칸마다 들어갈 수 있는 후보를 모두 표시해놓는 방법이 가장 편리하다.

보통 이런 경우 비트마스크로 구현한다. 9비트이므로 한 칸당 2바이트, 총 162바이트로 모두 표시 가능하다. (물론, 편의상 int를 사용할 것이다)

예를 들어 1, 3, 8만 들어갈 수 있는 칸의 경우 ...010000101로 표시가 될 것이다. 뒤에서부터 표시하는 것이 << 연산자를 이용할 수 있어 편리하다.

 

naked single은 특정 칸에 들어갈 수 있는 후보가 단 하나밖에 없는 경우로, 비트가 단 하나 켜져있는 상태이다.

이 경우 __builtin_popcount(mask) == 1로 검출할 수도 있지만, 비트 연산자에 대한 이해가 어느 정도 있다면 mask && (mask & (mask - 1)) == 0으로도 작성할 수 있다. 비트의 위치는 __builtin_ctz로 알아낼 수 있다.

 

hidden single의 경우, 각 행/열/상자의 9개 mask 중에, 해당 위치에 켜진 비트가 단 한군데에만 존재해야 한다.

이를 찾을 기막힌 비트 연산이 있다.

찾을 위치의 mask들을 int mask[9]에 저장해놓았다고 할 때,

int result = (1 << 9) - 1, x = 0;
for (int i = 0; i < 9; ++i) {
   result &= ~(x & mask[i]);
   x |= mask[i];
}

 

로 계산하면 result에 한군데에만 켜진 비트가 저장된다. 단, 위치는 한 번 더 찾아내야 한다.

 

여기까지가 deterministic한 과정이다.

이 부분까지의 코드는 다음과 같이 작성할 수 있다. 중간에 com과 last는 해답을 찾은 게 있는지 확인해서 break하는 용도이고, goto문은 루프를 한방에 탈출하는 용도이다.

 

int t[9][9];
int mask[9][9];
 
void add_elem(int i, int j, int n) {
    t[i][j] = n + 1;
 
    mask[i][j] = 0;
    for (int p = 0; p < 9; ++p) {
        mask[i][p] &= ~(1 << n);
        mask[p][j] &= ~(1 << n);
    }
    int x = i / 3 * 3, y = j / 3 * 3;
    for (int p = 0; p < 3; ++p) for (int q = 0; q < 3; ++q) mask[x + p][y + q] &= ~(1 << n);
}
 
void single() {
    int com = 0, last = 0;
    while (1) {
        if (com - last == 4) break;
        for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
            if (mask[i][j] && !(mask[i][j] & (mask[i][j] - 1))) {
                add_elem(i, j, __builtin_ctz(mask[i][j]));
                last = com + 1;
            }
        }
        com++;
 
        if (com - last == 4) break;
        for (int i = 0; i < 9; ++i) {
            int check = (1 << 9) - 1, x = 0;
            for (int j = 0; j < 9; ++j) {
                check &= ~(x & mask[i][j]);
                x |= mask[i][j];
            }
            while (check) {
                int k = __builtin_ctz(check);
                for (int j = 0; j < 9; ++j) if (mask[i][j] & (1 << k)) {
                    add_elem(i, j, k);
                    last = com + 1;
                    break;
                }
                check &= check - 1;
            }
        }
        com++;
         
        if (com - last == 4) break;
        for (int i = 0; i < 9; ++i) {
            int check = (1 << 9) - 1, x = 0;
            for (int j = 0; j < 9; ++j) {
                check &= ~(x & mask[j][i]);
                x |= mask[j][i];
            }
            while (check) {
                int k = __builtin_ctz(check);
                for (int j = 0; j < 9; ++j) if (mask[j][i] & (1 << k)) {
                    add_elem(j, i, k);
                    last = com + 1;
                    break;
                }
                check &= check - 1;
            }
        }
        com++;
         
        if (com - last == 4) break;
        for (int p = 0; p < 9; p += 3) for (int q = 0; q < 9; q += 3) {
            int check = (1 << 9) - 1, x = 0;
            for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
                check &= ~(x & mask[p + i][q + j]);
                x |= mask[p + i][q + j];
            }
            while (check) {
                int k = __builtin_ctz(check);
                for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
                    if (mask[p + i][q + j] & (1 << k)) {
                        add_elem(p + i, q + j, k);
                        last = com + 1;
                        goto l1;
                    }
                }
                l1:;
                check &= check - 1;
            }
        }
        com++;
    }
}

 

 

가정하기

여기까지 진행했을 때 풀리는 스도쿠라면, 감사를 표하면 된다.

하지만 보통 고난이도 스도쿠일 경우, 위의 방법만으로 풀기는 어림도 없다.

 

이럴때는 이제 숫자 하나를 가정하고, 풀이를 계속해나가야 한다.

숫자를 가정하는 방법에는 여러 가지가 있을 수 있다.

켜져 있는 비트 수가 가장 적은 곳을 분기점으로 고를 수도 있고, 그냥 가장 앞의 것을 분기점으로 고를 수도 있다. 이는 구현하기 나름.

 

이 방법으로 구현한 코드는 아래와 같다. 가장 앞의 것을 분기점으로 골랐다.

https://www.acmicpc.net/source/share/a75fc00ced3b408d9037a6b5f069829b

백준 테스트케이스 기준 0ms로 가장 빠른 속도를 내므로, 상당히 빠르게 동작하는 코드라고 할 수 있다.

 

하지만, 가정하는 방법의 본질적인 문제점은 nondeterministic하다는 것. 즉, 가정이 틀릴 수도 있다는 점이다.

다행히 컴퓨터는 꽤 빠르므로 어느 정도 빠른 성능을 낼 수 있지만, 만약 분기점의 깊이가 15~20개 정도 되는데, 맨 처음 분기점이 잘못된 것이라면?

이럴 경우, 3*3 스도쿠임에도 최악의 성능을 내는 프로그램이 탄생한다.

 

랜덤 데이터를 만들어가며, worst case를 찾아보았다. 참고로 컴파일시 -O2 옵션을 주었다.

0 0 0 8 0 6 0 1 0

0 6 0 0 0 0 0 0 0

8 0 9 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0

0 0 0 0 5 0 0 9 0

0 5 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 7

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

 

0이 조금 많기는 하지만, 이 테스트케이스는, 무려 29초라는 시간이 소요된다.

물론 이 케이스는 가정을 뒤에서부터 하면 금방 되긴 한다. 101번, 102번 줄을

for (int i = 0; i < 9; ++i)에서 for (int i = 8; i >= 0; --i)로 바꾸기만 하면 된다.

 

하지만 언제까지나 이렇게 운빨에 의존할 수는 없다.

이럴 때 사용할 수 있는 방법이 바로 dlx 알고리즘이다.

 

 

dlx 알고리즘

dlx 알고리즘은 Dancing Link algorithm X의 약자를 딴 것으로, 스도쿠 뿐 아니라 많은 곳에 활용될 수 있는 유용한 알고리즘이다.

Kunth's algorithm X는 exact cover을 찾는 알고리즘이다.

exact cover란 예시를 보면 바로 알 수 있는데, 전체집합 {1, 2, 3, 4, 5, 6, 7} 하에,

 

A = {1, 4, 7};

B = {1, 4};

C = {4, 5, 7};

D = {3, 5, 6};

E = {2, 3, 6, 7};

F = {2, 7}.

와 같이 A~F 집합이 있을 때, 전체집합인 1~7까지의 모든 숫자를 단 한번만, 모두 덮는 집합을 찾아내는 문제이다.

이 문제의 경우 B, D, F가 정답이 될 것이다. 물론 정답이 여러 개 있을 수도 있다.

 

그렇다면 exact cover와 스도쿠가 무슨 연관이 있을까?

놀랍게도, 스도쿠를 exact cover로 나타낼 수 있다. 정말 창의적인 생각이다. 다음과 같이 cover를 설정하면 된다.

(1, 1, 1): {grid11, row11, column11, box11}

(1, 1, 2): {grid11, row12, column12, box12}

...

(7, 8, 1): {grid78, row71, column81, box91}

...

(9, 9, 9): {grid99, row99, column99, box99}

 

이렇게 하면 사이즈 729x324짜리 cover matrix가 완성된다. 너무 커서 나타내기가 힘든데, 설명을 하자면 이렇다.

(1, 1, 1)은 (1, 1)에 숫자 1을 넣는 경우이다. (7, 8, 1)은 (7, 8)에 숫자 1을 넣는 경우가 된다.

이렇게 총 9^3 = 729개가 matrix의 row를 이룬다.

 

그럼 matrix의 column은?

각 칸별로 숫자는 하나만 들어갈 수 있으므로, 이를 grid11로 표시해둔다. 칸 (1, 1)에 들어간다는 의미이다.

스도쿠의 각 row, column, box별로는 숫자가 하나씩만 들어갈 수 있으므로 이를 row11과 같이 표시한다. 이는 row1에 숫자 1이 들어간다는 의미이다.

이럴 경우 총 9*9*4 = 324가지의 제약조건이 생긴다. 이 조건들이 column을 이룬다.

 

이미 숫자가 들어가 있을 경우에는, 9가지의 숫자 경우를 모두 만들 필요 없이 하나만 만들면 된다.

 

이 상태에서 dlx 알고리즘을 통해 exact cover를 찾으면 가볍게 완성된다.

구현은 상당히 까다로운 편인데, https://arxiv.org/pdf/cs/0011047.pdf를 참고하길 바란다.

 

이를 이용한 스도쿠 풀이는 https://www.acmicpc.net/source/share/61cd00213c6e4e0abfeeb9135edd6241에서 볼 수 있다.

마찬가지로 0ms이다. 물론 matrix를 만드는 데 전체적인 오버헤드가 큰 편이지만, worst case가 없다는 장점이 있다.

 

마찬가지로 랜덤으로 데이터를 생성해서 돌려본 결과, 가장 오래 걸리는 케이스가 46ms 정도 걸린 것을 확인할 수 있었다.

 

이를 이용하면 4*4짜리 스도쿠도 풀 수 있다. 이는 https://www.acmicpc.net/problem/3763에서 풀어볼 수 있다.

스도쿠 외에도 펜토미노라던가, N-Queen 등 무언가를 덮는 문제에 두루 활용이 가능하다.