d라이브러리

오늘 소개할 게임은 1부터 15까지의 숫자가 적힌 타일을 크기 순서대로 배열하는 ‘15 퍼즐’이에요. 규칙이 쉬워서 금방 풀 수 있을 것 같지만, 수학으로 분석해 보면 애초에 순서대로 배열할 수 없는 경우도 있어요. 기사를 열심히 읽으면 헛고생하는 일이 없을 거예요!

15 퍼즐은 1874년경 미국 카나스토타 마을의 우체국장이었던 노예스 채프먼이 개발한 게임이에요. 1880년에 미국과 유럽에서 선풍적인 인기를 끌었고, 이후 전 세계에 퍼져 나가 약 130년이 지난 지금도 많은 사람에게 사랑을 받고 있어요.

15 퍼즐을 보면 액자처럼 생긴 정사각형 틀 안에 1부터 15까지의 숫자가 적힌 사각형 타일이 나란히 놓여있어요. 가로세로 4개씩 총 16개 타일이 들어갈 수 있지만, 1칸을 비워둬서 다른 타일을 빈칸으로 움직일 수 있도록 했어요. 그러면 옮긴 타일이 있던 자리가 비니까 또 다른 타일을 옮길 수 있지요. 무작위로 배열된 타일을 옮겨 타일에 적힌 숫자를 오름차순으로 배열하면 게임이 끝나는 거예요.

숫자가 순서대로 배열된 상태를 ‘표준 배열’이라고 합니다. 아래 가운데 그림을 보면 6, 7, 10, 11, 12번 타일을 옮겨야 표준 배열을 만들 수 있어요. 무턱대고 아무 타일이나 옮기면 배열이 더 복잡해질 수 있으므로 어떤 타일을 먼저 옮기고 어떤 타일을 나중에 옮길지부터 생각한 뒤 옮겨야 합니다. 이 경우 10번 타일을 먼저 아래로 옮긴 뒤 6번 타일을 10번 타일이 있던 자리로 옮기고, 이어서 7번, 11번, 12번 타일을 각각 6번, 7번, 11번 자리로 옮기면 표준 배열을 만들 수 있어요.

1878년, 퍼즐리스트로 잘 알려진 미국의 체스 선수 샘 로이드는 표준 배열에서 14, 15번 타일의 자리만 바꾼 배열을 표준 배열로 만드는 사람에게 당시 돈으로 1000달러(약 109만 원)를 준다고 했어요. 그런데 수학 이론을 이용해 분석하면 이 배열을 표준 배열로 바꾸는 것은 불가능 합니다. 그 이유를 알아보기 전에 우선 15 퍼즐을 수학적으로 표현해 보도록 하죠.

순열로 나타내라!

어떤 배열을 표준 배열로 바꿀 수 있는지 없는지 알아내려면 우선 배열을 ‘순열’로 나타내야 합니다. 순열은 숫자나 알파벳 같은 원소 n개의 배열을 나타내는 함수로, 보통 n개 원소는 총 n!(=n×(n-1)×(n-2)×…×2×1)개 순열을 가집니다.

예를 들어 n=3이고 원소가 1, 2, 3인 경우를 생각해 봅시다. 1, 2, 3을 배열하는 모든 경우를 따져보면 1-2-3 그대로 놓는 경우와 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1로 배열하는 경우까지 총 6가지 순열이 있어요. 15 퍼즐에서 빈자리를 16번 타일이라고 생각하면 숫자가 총 16개 있는 셈이므로, 16!=20,922,789,888,000개 순열이 있는 거지요.

이제 여러 순열 중 한 개를 골라 구체적으로 어떤 숫자가 어디에 있는지 좀 더 자세하게 나타내 볼 거예요. 우선 오른쪽 위에 있는 15 퍼즐의 타일 배열을 표준 배열과 비교하면 아래 표로 나타 낼 수 있어요.

위 표를 보면 6, 7, 10, 11, 12, 15, 16번 타일을 제외한 나머지 타일은 모두 표준 배열에 맞게 놓여 있고, 어떤 타일이 어디에 놓여있는지도 알 수 있어요. 표준 배열과 비교해 보면 6번 타일이 있어야 할 자리에 7번 타일이 있고, 7번 타일 자리에는 10번 타일이 놓여있습니다. 위치가 바뀌지 않은 숫자는 굳이 표시 안 해도 되니까 더 간단한 기호로 나타내 볼게요.

우선 표준 배열에서 6, 7, 10번 타일 자리에 어떤 숫자가 놓여있는지 화살표로 나타내면 6→7, 7→10, 10→6으로 나타낼 수 있어요. 이제 중복되는 숫자와 화살표를 제외하고 (6 7 10)이라고 쓴 뒤, 왼쪽부터 시작해서 오른쪽으로 가면서 6번 타일 자리에 7번, 7번 타일 자리에 10번, 10번 타일 자리에 다시 6번 타일이 있다고 생각하면 됩니다. 비슷하게 나머지 타일을 11→16, 16→15, 15→12, 12→11로 나타낼 수 있으니 (11 16 15 12)라고 쓰면 되지요. 그러면 (6 7 10), (11 16 15 12)만 적어도 배열을 나타낼 수 있어요.

홀순열은 NO! 짝순열은 YES!

배열을 순열로 나타냈을 때, 괄호 안의 숫자가 홀수 개면 짝순열, 짝수 개면 홀순열이라고 해요. 숫자가 홀수 개인데 왜 홀순열이 아니고 짝순열이냐고요? 그 이유는 짝, 홀이 괄호 안에 있는 숫자의 개수가 아니라 순열을 이루는 ‘호환’의 개수를 나타내기 때문이에요.

호환은 (6 7)처럼 숫자 2개로 이뤄진 홀순열로, 6→7, 7→6으로 나타낼 수 있으므로 괄호 안에 있는 두 숫자의 위치를 바꾸라는 기호입니다. 모든 짝순열, 혹은 홀순열은 호환의 조합으로 표현할 수 있어요.

예를 들어 (6 7 10)은 호환 두 개를 이용해 (6 10)(6 7)로 나타냅니다. 이 기호는 표준 배열에서 오른쪽에 있는 호환을 먼저 적용해 6과 7의 자리를 바꾸고, 다시 6과 10의 자리를 바꾸라는 뜻입니다. 비슷하게 (11 16 15 12)는 호환 세 개를 이용해 (11 12)(11 15)(11 16)으로 나타낼 수 있지요. 결국, (6 7 10)(11 16 15 12)로 나타낸 순열은 각각 짝수, 홀수 개 호환을 가지고 있으므로 전체는 짝순열+홀순열=홀순열인 셈입니다.

모든 준비가 끝났어요. 이제 어떤 배열을 표준 배열로 바꿀 수 있는지 알 수 있는 정리를 소개 할게요.

이 정리는 미국의 수학자 윌리엄 존슨과 윌리엄 스토리가 증명한 정리로, 이 정리에 따르면 어떤 배열을 나타내는 순열이 홀순열이면 아무리 노력해도 표준 배열로 바꿀 수 없어요. 샘 로이드가 제시한 14, 15번 타일의 위치만 바꾼 배열은 홀순열인 (14 15)로 나타낼 수 있으므로 애초에 풀 수 없는 문제였던 거지요.

존슨과 스토리가 증명한 정리를 이용하면 15 퍼즐뿐 아니라 다양한 크기의 퍼즐에서 어떤 배열을 표준 배열로 만들 수 없는지 알 수 있어요. 그런데 표준 배열로 만들 수 있는 배열이어도 구체적으로 어떤 타일을 어떻게 옮겨야 하는지, 어떻게 하면 가장 적은 수의 타일만 옮겨서 표준 배열을 만들 수 있는지는 아직 밝혀지지 않았어요.

1986년 미국의 컴퓨터 과학자인 다니엘 라트너와 맨프레드 바르무트는 가로세로가 각각 n개 타일로 이뤄진 n2-1 퍼즐에서 가장 적은 수의 타일만 옮겨서 표준 배열을 만드는 방법을 찾는 문제가 NP-하드★에 속한다는 사실을 밝혔지요.

NP-하드★ 문제를 푸는 알고리듬의 복잡도가 비슷한 문제끼리 모아둔 집합으로 P, NP, NP-하드, PSPACE가 있다. NP-하드는 PSPACE 다음으로 복잡한 문제의 집합이다.

표준 배열로 가는 거리

구체적인 방법을 찾을 수는 없지만, ‘맨해튼 거리’와 ‘해밍 거리’를 이용하면 타일을 최소한 몇 번 옮겨야 하는지 추측할 수 있어요. 맨해튼 거리에서 ‘거리’는 각 타일이 표준 배열에 맞는 자리로 곧장 가기 위해 움직인 횟수입니다. 왼쪽 배열을 보면 1은 표준 배열의 위치에 있으므로 거리가 0이고, 3은 5번 타일이 있는 자리로 가야 하므로 1입니다. 5번 타일이 9번 타일이 있는 자리로 곧장 가려면 아래로 1칸, 왼쪽으로 2칸 움직여야 하므로 거리가 3이지요. 이렇게 모든 타일이 움직여야 하는 거리를 합한 값이 맨해튼 거리입니다. 왼 쪽 배열의 경우 맨해튼 거리가 32니까 타일을 최소한 32번 움직여야 표준 배열이 될 수 있지요.

더 간단한 방법으로 해밍 거리가 있습니다. 해밍 거리는 맨해튼 거리와 달리 표준 배열 위치에 있는 타일은 거리가 0이고, 그렇지 않은 경우는 거리를 무조건 1로 계산합니다. 따라서 맨해튼 거리보다 항상 값이 작거나 같지요. 실제로는 타일을 빈칸으로만 움직일 수 있기 때문에 맨해튼 거리와 해밍 거리는 어디까지나 최솟값을 추측해보는 도구일 뿐이에요.

1999년에는 컴퓨터 과학자인 아드리안 부륀거, 암브로스 마제타, 코메이 후쿠다, 유어그 니버젤트가 배열이 짝순열이기만 하면 어떤 배열이든 80번 안에 표준 배열을 만들 수 있다고 증명하면서 최솟값과 최댓값을 대략 계산할 수 있게 됐어요.

앞으로 연구가 거듭되면 구체적으로 몇 번을 움직여야 하는지, 또 어떻게 움직여야 하는지 알 수 있겠죠?

※ 김종락 : 서강대학교 수학과 교수는 포스텍 수학과를 졸업하고, 서울대학교에서 석사 학위, 미국 일리노이주립대학교 시카고캠퍼스에서 박사 학위를 받았습니다. 주요 연구 분야는 부호론과 암호론, 산업수학, 인공지능입니다. 2004년 캐나다 조합론연구소에서 주는 커크만 메달을 한국인 최초로 받았습니다. 2016년부터 대한수학회 수학문화 앰배서더로 활동 중이며, ‘감성수학레드’라는 스타트업을 운영하고 있습니다.