포스트

[종만북] 문제: KAKURO2

게시 업데이트
By 정승우
13 분읽는 시간

문제

카쿠로라는 게임이 있습니다. 카쿠로의 입력이 주어지면, 정답 보드를 출력하는 프로그램을 작성하시오.

보드의 최대 크기는 20x20입니다.

문제 링크

서론

최적화 문제를 넘어 CSP(ConStraint Satisfaction Problem)의 일종인 카쿠로를 풀어봅시다.

카쿠로

카쿠로의 규칙은 다음과 같습니다.

  • 모든 흰 칸에는 1 부터 9 까지의 정수를 써넣어야 한다.
  • 세로로 연속한 흰 칸들의 수를 모두 더하면, 그 칸들의 바로 위에 있는 힌트 칸의 왼쪽 아래에 씌인 숫자가 나와야 한다.
  • 가로로 연속한 흰 칸들의 수를 모두 더하면, 그 칸들의 바로 왼쪽에 있는 힌트 칸의 오른쪽 위에 씌인 숫자가 나와야 한다.
  • 이 때 한 줄을 이루는 연속된 흰 칸들에는 같은 수를 두 번 넣을 수 없다.

제약 충족 문제

제약 충족 문제(ConStraint Satisfaction Problem)는 변수 집합, 변수의 도메인, 그리고 이 변수들에 적용되는 제약 조건을 만족시키는 해를 찾는 문제를 의미합니다.

CSP의 구성 요소는 다음과 같습니다.

  1. 변수 (Variables):
    • 문제에 포함된 요소. 보통 $X_1, X_2, \dots, X_n$ 형태로 나타냅니다.
  2. 도메인 (Domains):
    • 각 변수에 할당될 수 있는 값들의 집합을 의미합니다.
    • 예:
      • $X_1 \in {1, 2, 3}$
      • $X_2 \in {\text{Red}, \text{Green}, \text{Blue}}$
  3. 제약 (Constraints):
    • 변수들 간의 관계를 정의하며, 만족되어야 하는 조건.
    • 예: $X_1 \neq X_2$ (서로 다른 값을 가져야 함).

스도쿠, n-Queen 문제, 노노그램 등이 CSP에 속합니다.

제약 전파

제약 전파는 CSP에서 제약 조건을 활용해 도메인을 축소하여 해를 더 효율적으로 찾는 기법입니다.

답의 일부를 생성한 뒤 여기서 얻을 수 있는 정보를 최대한 많이 찾아내서, 제 공간을 줄여 탐색 시간을 단축시킵니다.

답의 일부를 생성한다는 것은, 변수 $X_n$ 의 제약 조건을 만족시키는 도메인의 원소를 하나 택한다는 것과 동일합니다.

그러면, 제약 전파를 효율적으로 하기 위해서는 답의 일부를 어떻게 생성할 건지에 대해 고민해봐야합니다.

익숙한 수리 퍼즐인 스도쿠를 예시로 들어봅시다. 생각해보면 숫자를 채울 때 숫자가 채워진 행, 열이 많은 칸부터 채우지 비워진 칸부터 채우진 않습니다.

마찬가지로 제약 전파도, 어떤 변수부터 값을 채워야 하는지 순서를 정해야 합니다.

이후에는 변수의 도메인 중 어느 값을 먼저 할당해야하는지 순서를 정하면 됩니다.

알고리즘 구상

카쿠로의 조건

  1. 변수 \(X = \{ \text{value}[y][x] \mid (y, x) \text{는 흰 칸} \}\)
  2. 도메인 \(D(X) = \{ 1, 2, 3, \dots, 9 \}\)
  3. 조건
    • 합 제약 \(\sum_{(y, x) \in hint} \text{value}[y][x] = \text{sum}[hint]\)
    • 중복 없는 값 제약 \(\forall (y_1, x_1), (y_2, x_2) \in hint, \quad \text{value}[y_1][x_1] \neq \text{value}[y_2][x_2]\)

칸의 숫자를 어떻게 선정하지?

변수 $X$에 들어갈 숫자를 선정해야 합니다. 앞서 살펴본 합 제약과 중복 없는 값 제약을 만족시켜야 합니다.

이 제약에서 추론할 수 있는 것은, 한 줄의 최대 칸 개수는 9개, 최대 합의 크기는 45라고 볼 수 있습니다.

$sum$: 칸의 합과 $len$: 칸의 개수, $known$: 사용된 숫자

따라서 $sum$과 $len$, $known$가 주어지면 사용 가능한 숫자 집합을 표현하는 배열 $candidates[len][sum][known]$로 나타낼 수 있습니다.

$known$은 1부터 9까지의 숫자를 택하는지, 택하지 않는지로 생각할 수 있습니다. 따라서 경우의 수는 $2^9$ 이므로 비트마스크로 표현이 가능합니다.

입력 전처리

이제 칸의 좌표 $(y,x)$가 주어지면 후보의 수를 어떻게 계산해야 하나요?

각 $(y,x)$가 속한 $hint_i(0 \leq i \leq q-1)$를 매핑하여, 해당 힌트의 조건$(sum, length, known)$을 참조할 수 있게 합니다.

  • $hint[y][x][0]$: 좌표 $(y, x)$가 속한 가로 힌트의 인덱스$(hint_i)$.
  • $hint[y][x][1]$: 좌표 $(y, x)$가 속한 세로 힌트의 인덱스$(hint_i)$.
  • $sum[hint_i]$: $hint_i$의 목표 합.
  • $length[hint_i]$: $hint_i$에 포함된 칸의 개수.
  • $known[hint_i]$: $hint_i$에서 이미 사용된 숫자를 비트마스크로 표현.

조합 탐색의 순서

이제, 어떤 칸부터 채워나가면 될까요?

가장 제약이 강한 칸을 선택하면 됩니다. 카쿠로 문제에서 가장 제약이 강하다는 것은, 선택할 도메인의 개수가 적다는 것입니다. 도메인의 개수가 적은 것부터 채워나가면 됩니다.

알고리즘 설계

  1. 후보 테이블 $candidates[len][sum][known]$을 생성합니다.
  2. 입력을 처리합니다.
    • 퍼즐의 크기(n)와 흰 칸(color 배열)을 입력받음.
    • 각 힌트의 시작 위치와 조건(sum)을 입력받아 hint, sum, length, known 배열 초기화.
  3. 백트래킹 탐색:
    • search()를 호출하여 가능한 해를 탐색. 이때, 도메인이 작은 칸부터 채운다.
    • 칸의 가능한 숫자가 없을 때까지 백트래킹.
    • 모든 칸을 채웠으면, 보드 출력 이후 종료

알고리즘 구현

사용할 배열들

앞서 설명한 값들을 전처리하기 위해 선언한 배열들입니다.

1
2
3
4
5

static const int MAXN = 21;

int n, color[MAXN][MAXN], value[MAXN][MAXN], hint[MAXN][MAXN][2];
int q, sum[MAXN * MAXN], length[MAXN * MAXN], known[MAXN * MAXN];
int candidates[10][46][1024];

generateCandidates()

int candidates[10][46][1024]를 계산해주는 함수입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13

void generateCandidates() {
    for (int set = 2; set < (1 << 10); set += 2) {
        int setSize = __builtin_popcount(set);
        int setSum = 0;
        for (int i = 1; i <= 9; i++) {
            if (set & (1 << i)) setSum += i;
        }
        for (int usedMask = 0; usedMask < (1 << 10); usedMask += 2) {
            if ((set | usedMask) != set) continue;
            candidates[setSize][setSum][usedMask] |= (set & ~usedMask);
        }
    }
}

유틸리티 함수

백트래킹 함수 search()를 쉽게 구현하기 위한 유틸리티 함수들입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// put
void put(int y, int x, int val) {
    for (int h = 0; h < 2; h++) {
        known[hint[y][x][h]] += (1 << val);
    }
    value[y][x] = val;
}

// remove
void remove(int y, int x, int val) {
    for (int h = 0; h < 2; h++) {
        known[hint[y][x][h]] -= (1 << val);
    }
    value[y][x] = 0;
}

// 힌트 번호가 주어지면, 후보의 bitmask를 반환
int getCandHint(int h) { return candidates[length[h]][sum[h]][known[h]]; }

// 좌표가 주어지면, 후보의 bitmask를 반환
int getCandCoord(int y, int x) {
    return getCandHint(hint[y][x][0]) & getCandHint(hint[y][x][1]);
}

int getSize(int mask) {
    int count = 0;
    while (mask) {
        count += (mask & 1);
        mask >>= 1;
    }
    return count;
}
  1. 이 후 보드를 처음부터 끝까지 탐색하며 도메인의 범위가 가장 작은 칸을 선정합니다. 이때 탐색 시 가능한 숫자가 없는 칸이 존재한다면, 탐색을 종료합니다.
  2. 모든 칸이 채워져있으면, 답을 출력합니다.
  3. 그렇지 않으면, 앞서 선정한 칸을 도메인의 범위 내에 있는 숫자를 임의로 넣고 재귀호출합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

bool search() {
    int y = -1, x = -1, minCands = 1023;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 빈 칸에 대해
            if (color[i][j] == 1 && value[i][j] == 0) {
                int cands = getCandCoord(i, j);
                if (cands == 0) {
                    return false; // 가능한 숫자가 없음
                }
                if (getSize(cands) < getSize(minCands)) {
                    minCands = cands;
                    y = i;
                    x = j;
                }
            }
        }
    }

    // base case, 출력 이후 종료
    if (y == -1) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << value[i][j] << " ";
            }
            cout << "\n";
        }
        return true;
    }

    // recursive case
    for (int num = 1; num <= 9; num++) {
        if (minCands & (1 << num)) {
            put(y, x, num);
            if (search()) return true;
            remove(y, x, num);
        }
    }
    return false;
}

main()내 답 전처리 부분

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

for (int hintIndex = 0; hintIndex < q; hintIndex++) {
    int Y, X, Dir, S;
    cin >> Y >> X >> Dir >> S;

    sum[hintIndex] = S;
    known[hintIndex] = 0;
    length[hintIndex] = 0;

    if (Dir) {
        int row = Y + 1;
        while (row <= n && color[row][X] == 1) {
            hint[row][X][1] = hintIndex;
            length[hintIndex]++;
            row++;
        }
    } else {
        int col = X + 1;
        while (col <= n && color[Y][col] == 1) {
            hint[Y][col][0] = hintIndex;
            length[hintIndex]++;
            col++;
        }
    }
}

최종 코드

여기에서 확인하세요!

알고리즘 개선

데이터의 관리 개선?

현재 입력 데이터들을 $(y,x)$ -> hindID -> len, sum, known이렇게 매핑하고 있습니다. struct를 만들어서 깔끔하게 정리해보는 것도 나쁘지 않을 듯 싶습니다.

알고리즘, 종만북
알고리즘 종만북
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.