최근 인터넷 상에 재미있는 수학 짤이 돌아다니길래 해설을 작성해서 올린다.

1부터 32까지의 정수를 한 번씩 이용해 원형으로 나열했을 때, 이웃한 두 수를 더하면 제곱수가 되는 배치이다.

말을 조금 바꿔서, 퍼즐 문제로 만들어보자.

1부터 32까지의 정수를 한 번씩 이용해 이웃한 두 수를 더하면 제곱수가 되도록 하는 원형 배치를 제시하여라

이는 사실 해밀턴 순환을 찾는 문제다.

해밀턴 순환은 해밀턴 경로 중 순환인 것으로, 해밀턴 경로는 어릴 때 많이 해본 '한 붓 그리기'와 비슷하다. 그래프의 한 점에서 출발하여 모든 점을 한 번씩 방문하는 경로가 해밀턴 경로다. 그 중에서 첫번째 점과 마지막 점이 같은 경로가 해밀턴 순환이다.

1번은 해밀턴 순환이고, 2번은 해밀턴 경로이기는 하지만 해밀턴 순환이 아니다.

자 그러면 퍼즐을 한 번 풀어보자.

• 1과 더했을 때 제곱수가 되는 수는 3, 8, 15, 24이므로, 1의 양 옆에 올 수 있는 수는 3, 8, 15, 24다.
• 2와 더했을 때 제곱수가 되는 수는 7, 14, 23이므로, 2의 양 옆에 올 수 있는 수는 7, 14, 23이다.
• …
• 32와 더했을 때 제곱수가 되는 수는 4, 17이므로 32의 양 옆에 올 수 있는 수는 4, 17이다.

이렇게 1부터 32까지 각각의 옆에 올 수 있는 수를 찾을 수 있고, 1부터 32까지를 정점으로하여 그래프를 그리면 아래와 같은 모습이 나온다.

해당 그래프에서 해밀턴 경로를 찾으면 우리가 원하는 배치를 찾을 수 있다. 짤에서의 경로를 표시해보면 다음 그림과 같다.

그렇다면 다른 경로들은 어떻게 찾을 수 있을까?

딱 봐도 사람이 하기에는 힘들어보이니 기계의 힘을 빌리자.

다음은 정수 N이 주어졌을 때, 문제의 조건에 맞는 모든 해밀턴 경로를 찾는 프로그램이다.

동일한 경로나 순서만 뒤집힌 경로는 제외하고 출력하도록 하였다.

#include <stdio.h>
#define MAX 1000

int n;
int arr[MAX][MAX];
int mem[MAX][MAX]; // to memorize
int mem_cursor = 0;
int visited[MAX];
int path[MAX];
int path_cursor = 0;

int is_square(int k) {
    for(int i=1; i*i <= k; i++) {
        if(i*i == k) return 1;
    }
    return 0;
}

int is_equal(int* a, int* b, int direction) {
    //find starting point
    int i=0, j=0;
    for(; j<n; j++)
        if(a[0]==b[j])
            break;
    int count = n;
    while(count) {
        if (a[i] != b[j])
            return 0;
        i++;
        j+=direction;
        if(i>=n) i =0;
        if(j>=n) j = 0;
        if(i<0) i = n-1;
        if(j<0) j = n-1;
        count--;
    }
    return 1;
}

int is_found(int* p) {
    for(int i=0; i<mem_cursor; i++) {
        if(is_equal(mem[i], p, 1) || is_equal(mem[i], p, -1))
            return 1;
    }
    return 0;
}

int is_visited_all() {
    for(int i=1; i<=n; i++) {
        if(!visited[i]) return 0;
    }
    return 1;
}

void hamilton(int arr[][MAX], int node) {
    if(is_visited_all()) {
        if(arr[path[0]][path[n-1]] && !is_found(path)) {
            printf("\ncycle %d: ", mem_cursor);
            for(int i=0; i<n; i++) {
                mem[mem_cursor][i] = path[i];
                printf("%02d ",path[i]);
            }
            mem_cursor++;
        }
        return;
    };
    for(int i=1; i<=n; i++) {
        if(arr[node][i] && !visited[i]) {
            visited[i] = 1;
            path[path_cursor++] = i;
            hamilton(arr, i);
            visited[i] = 0;
            path[path_cursor--] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);

    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) 
            arr[i][j] = 0;

    for(int i=1; i<=n; i++) {
        for(int j=i; j<=n; j++) {
            if(is_square(i+j)) {
                arr[i][j] = arr[j][i] = 1;
            }
        }
    }

    hamilton(arr, 1);
}

입력 32에 대한 출력은 다음과 같다.

cycle 0: 03 06 30 19 17 32 04 21 28 08 01 15 10 26 23 02 14 22 27 09 16 20 29 07 18 31 05 11 25 24 12 13

순서를 잘 살펴보면 우리가 제일 처음 봤던 사진의 경로와 같다는 것을 알 수 있다.

즉, n이 32일때는 경로가 유일하다.

cycle 0: 03 06 30 19 17 32 04 21 28 08 01 15 10 26 23 02 14 22 27 09 16 33 31 18 07 29 20 05 11 25 24 12 13

n이 33일 때에도 경로는 유일하다. n이 34이면?

cycle 0: 03 01 08 28 21 04 32 17 19 06 30 34 15 10 26 23 02 14 22 27 09 16 33 31 18 07 29 20 05 11 25 24 12 13 
cycle 1: 03 01 08 28 21 15 10 26 23 02 34 30 06 19 17 32 04 05 20 29 07 18 31 33 16 09 27 22 14 11 25 24 12 13 
cycle 2: 03 01 08 28 21 15 10 26 23 13 12 24 25 11 05 04 32 17 19 06 30 34 02 14 22 27 09 16 20 29 07 18 31 33 
cycle 3: 03 01 08 28 21 15 10 26 23 13 12 24 25 11 14 02 34 30 06 19 17 32 04 05 20 29 07 18 31 33 16 09 27 22 
cycle 4: 03 01 08 28 21 15 34 02 14 11 25 24 12 13 23 26 10 06 30 19 17 32 04 05 20 29 07 18 31 33 16 09 27 22 
cycle 5: 03 01 08 28 21 15 34 02 14 22 27 09 16 33 31 18 07 29 20 05 11 25 24 12 04 32 17 19 30 06 10 26 23 13 
cycle 6: 03 01 08 28 21 15 34 02 23 26 10 06 30 19 17 32 04 05 20 29 07 18 31 33 16 09 27 22 14 11 25 24 12 13 
cycle 7: 03 01 15 21 28 08 17 32 04 05 11 25 24 12 13 23 26 10 06 19 30 34 02 14 22 27 09 16 20 29 07 18 31 33 
cycle 8: 03 01 15 21 28 08 17 32 04 12 24 25 11 05 20 29 07 18 31 33 16 09 27 22 14 02 34 30 19 06 10 26 23 13 
cycle 9: 03 01 24 25 11 05 20 29 07 18 31 33 16 09 27 22 14 02 23 26 10 06 19 30 34 15 21 28 08 17 32 04 12 13 
cycle 10: 03 06 10 26 23 02 14 22 27 09 16 33 31 18 07 29 20 05 11 25 24 01 08 28 21 15 34 30 19 17 32 04 12 13

가능한 경로의 수가 11가지나 된다.

n이 32보다 작을 때는 해밀턴 경로가 존재하지 않는데, 이에 대해서는 직접 32보다 작은 수에 대해서 그래프를 그려보고 생각해보면 좋을 것이다.

레퍼런스

1. 서울대 에브리타임 자유게시판 게시글
2. "Puzzle 1: Neighboring Square Numbers", 2016, Havard University, https://people.math.harvard.edu/~knill/puzzles/examples/puzzle01.pdf
3. "Hamiltonian Path", Wikipedia, https://en.wikipedia.org/wiki/Hamiltonian_path