by
Jun 22. 2022
신의 수. 큐브를 맞추는 가장 효율적인 방법
일반적으로 큐브를 맞추는 기록이라고 하면 '시간'을 이야기합니다. 내가 큐브를 맞추는 데 몇 초가 걸렸는지를 측정해서 순위를 매기고 그것은 나의 기록이라고 이야기하죠. 하지만 이것만 있는 것은 아닙니다. 약간 관점을 바꿔보면 여러분이 큐브를 맞추는 데 몇 회전을 사용하였는지 세어볼 수 있죠. 50회전, 100회전. 사람마다 다양할 것이고 저는 보통 60회전 근방의 회전수로 큐브를 맞춥니다. 운이 좋으면 50회전 미만이 나오기도 하고요. 그리고 WCA 공인 종목에는 이 회전수를 가지고 경쟁하는 FMC라는 종목이 존재하죠.
그렇다면 섞여있는 임의의 3x3x3 큐브를 맞추는 데 필요한 최소한의 회전수는 얼마일까요?
3x3x3 큐브의 경우의 수는 무려 43,252,003,274,489,856,000개입니다. 4325경 개입니다. 만약 큐브의 신이 있다면 어떨까요. 전지전능한 신이 존재한다면 섞여있는 임의의 3x3x3 큐브를 맞추는 가장 회전수가 적은 방법을 찾아내겠죠? 이때의 회전수를 우리는 '신의 수' 영어로 God's number라고 부릅니다. 신의 수를 n이라고 할 때 섞여있는 임의의 3x3x3 큐브는 n회전 혹은 그 미만의 회전수로 맞출 수 있습니다.
1970년대 중후반에 출시된 루빅스 큐브가 전 세계적인 인기를 끌고 있던 1980년대부터 사람들은 신의 수가 얼마일지 궁금해했습니다. 하지만 신의 수가 얼마인지 밝혀진 것은 무려 30년가량이 흐른 2014년이었습니다. 신의 수를 찾는 것은 예상외로 매우 어려운 문제였던 거죠.
큐브 유튜버 J Perm은 팩맨 아케이드 출시부터 슈퍼 마리오 갤럭시 2 출시까지라고 했지만 사실 슈퍼 마리오 갤럭시 2의 출시보다도 4년이 더 흘러서야 찾아냈습니다.큐브가 가지는 경우의 수는 유한하기 때문에 모든 경우의 수에 대해서 브루트 포스로 일일이 최소 회전수를 계산한 뒤 나온 최적의 솔루션 중 가장 회전수가 많은 경우의 회전수를 신의 수라고 할 수도 있습니다. 계산이 잘못되지 않은 이상 이 방법을 사용하면 무조건 신의 수를 구할 수 있죠. 그렇지만 현실적으로 그 방법이 가능할까요? 4325 경이라는 어마어마한 경우의 수에 대한 솔루션을 다 뽑아내려면 인류가 멸망할 때까지 계산해도 부족할지도 모릅니다. 특히나 처음 이 문제가 제시된 당시의 컴퓨터 성능을 생각한다면 더욱 그렇죠. 하지만 4색 정리가 그랬듯 계산해야 하는 상황의 수를 줄일 수만 있다면 여전히 인간이 계산하기에는 터무니없이 많은 상황이겠지만 컴퓨터 여러 대를 돌리면 할만한 수준일지도 모릅니다.
신의 수의 최솟값을 찾아내는 것은 쉽습니다. 한 가지 예로 신의 수가 최소 2회전은 되어야 된다는 것은 너무나도 자명합니다.
외부 층 회전을 무조건 1회전, 중간층 회전은 2회전, 시점 변환은 0회전으로 계산하는 하프 턴 회전 방식 (HTM)을 기준으로 한다면 큐브엔 U, U', U2, R, R', R2, F, F', F2, D, D', D2, L, L', L2, B, B', B2의 총 18가지의 1회전을 할 수 있습니다. 그렇다면 이 18가지 경우가 아닌 경우는 1회전으로는 맞출 수 없는 상황이며 최소 2회전이 필요하다는 것을 알 수 있죠. 너무나 당연한 이야기지만 이런 식의 논리를 2회전 이상으로 적용해봅시다. 모든 경우의 수에 대한 솔루션을 다 적는 것은 사실상 불가능하겠지만 만약 가능하다면 모든 경우의 수에 대해 각각 완전히 다른 솔루션이 나오겠죠. 만약 신의 수가 너무 작다면 그 수만큼의 회전으로 만들 수 있는 솔루션이 큐브의 경우의 수에 비해 너무 적게 될 겁니이다. 그럼 4325 경개의 서로 다른 회전들의 묶음을 만들려면 최소 몇 회전이 필요할까요.
큐브를 1회전 돌리는 방법은 위에서 본 것과 같이 18개가 있고 첫 회전을 고르고 나면 다음 1회전을 돌리는 방법은 15가지입니다. 직전에 돌렸던 층을 다시 돌리는 것은 회전수 계산법의 특성상 1회전이 추가되는 것이 아니기 때문이죠. 그래서 18x15x15x15x...이걸 계속하다 보면 총 17번 돌렸을 때 가능한 공식들은 경을 넘어 해라는 수까지 가게 됩니다.
사실 위의 방법은 잘못되었습니다. 서로 평행한 두면을 돌릴 때 그 순서를 바꾸어도 결과는 같습니다. U D를 하나 D U를 하나 결과가 같은 것 처럼 말이죠. 하지만 우리는 이것을 서로 다른 공식으로 셌죠. 그래서 이런 패턴이 나올 때마다 그중 하나를 지워야 합니다. 또한 이런 패턴이 나오면 다음 회전에는 총 12가지의 회전밖에 할 수 없죠. 이 모든 것을 고려하여 컴퓨터가 계산한 결과는 17회전으로는 부족하고 18회전부터 4325 경개의 서로 다른 공식들을 만들 수 있다는 것입니다.
그런데 왜 18회전이 신의 수라고 할 수 없는 걸까요? 그 이유는 18회전으로 서로 다른 경우의 수를 만들 수 있는 게 아닌 그저 서로 다른 회전을 가진 공식을 만든 것일 뿐이기 때문입니다. 서로 다른 공식이라도 결과는 같을 수 있습니다.(예시: R' L' F2 B2 R L D R' L' F2 B2 R L는 U와 같습니다.) 그리고 이런 공식이 다른데도 결과가 같은 것은 많아서 18회전이 충분한지 알 수 없습니다. 확실한 건 신의 수는 최소한 18회전은 돼야 한다는 거죠.
최댓값을 찾는 것은 더 어렵습니다. 최솟값은 그냥 이 스크램블을 맞추는데 최소 몇 회전이 필요하다는 것만 증명하면 되지만 최댓값을 증명하려면 모든 경우의 수를 맞추는데 이만큼의 회전이면 충분하다는 것을 보여야 되기 때문입니다.
모든 경우의 수를 각각 해보는 건 너무 오래 걸리기 때문에 당연히 불가능합니다. 그 대신 우리는 어떤 해법을 만들어서 그 해법으로 큐브를 맞추는데 최대 몇 회전이 걸린다는 것을 보일 수 있습니다. 예를 들어 가장 많이 쓰이는 해법인 CFOP에서 각 단계마다 나올 수 있는 가장 안 좋은 경우들의 회전수를 다 더하면 69회전이 나옵니다.(Cross:8 첫 번째 페어:8 두 번째 페어:8 세 번째 페어:9 네 번째 페어:9 OLL:12 PLL:14 AUF:1) 다르게 말하면 CFOP해법으로 최소한의 회전을 이용해서 맞추면 어떻게 섞여있더라도 69회전이면 맞출 수 있다는 겁니다.
1992년, 하버트 코시엠바는 코시엠바의 알고리즘이라 불리는 해법을 만들었습니다. 코시엠바의 알고리즘의 순서는 다음과 같습니다.
1. 큐브를 U, D, F2, B2, R2, L2 만으로 맞출 수 있는 상태로 만든다.
2. 큐브를 U, D, F2, B2, R2, L2 만으로 맞춘다.
1단계가 끝나면 모든 조각의 오리엔테이션이 맞아있고 중간층 엣지들이 모두 중간층에 위치해 있습니다. 이 조건을 만족시켰다면 나머지를 U, D, F2, B2, R2, L2 만으로 맞출 수 있습니다. 이렇게 만드는 것은 도미노 리덕션이라고도 알려져 있습니다.
2단계는 나머지를 이 회전들만으로 맞추는 것입니다. 물론 가능한 최소한의 회전수로 말이죠.
코시엠바의 알고리즘을 사용한 이유는 다음과 같습니다.
1. 적은 회전수를 쓴다.
2. 컴퓨터로 솔빙 가능하다.
이 해법은 어떻게 적은 회전수를 이용해서 맞출 수 있을까요? 일단 1단계가 완료된 상황을 보시면 맞춰진 것처럼 보이는 조각은 없습니다. 하지만 U, D, F2, B2, R2, L2 이렇게 특정한 무브만을 사용해서 돌린다면 어떻게 돌리든지 1단계가 완료된 상황을 벗어나지 않습니다. CFOP를 사용한다면 F2L을 맞추고 나면 마지막 층을 맞출 때 맞추면서 계속 F2L이 섞였다가 맞춰지기를 반복할 것인데 이 것은 엄청난 회전수 낭비고 코시엠바의 알고리즘과 같은 해법들이 효율적인 이유입니다.
코시엠바의 알고리즘의 1단계는 약 20억 개의 경우의 수가 있고 2단계는 약 200억 개의 경우의 수가 있습니다. 이것도 상당히 많지만 4300 경개에 비하면 훨씬 적죠.
컴퓨터가 계산한 결과는 1단계는 최대 12회전, 2단계는 최대 18회전이면 된다는 것입니다. 하지만 수학자 마이클 리드는 가장 긴 솔루션들을 보면서 1단계의 회전들을 바꿔서 2단계에서 더 짧은 솔루션을 만들 수 있는지 확인했습니다. CFOP에서 F2L 부분을 하는 방법을 바꿔서 마지막 층에서 더 적은 회전으로 맞출 수 있도록 만드는 것과 비슷하죠. 그 결과는 언제나 그것이 가능하다는 것이었습니다. 1단계가 12회전이라면 2단계는 17회전으로 줄일 수 있었습니다. 그래서 코시엠바의 알고리즘은 언제나 29회전 또는 그 이하로 맞출 수 있게 되었습니다. 위의 과정을 극단적으로 반복하면 1단계의 회전수를 늘리고 2단계를 더 적은 회전수로 해서 전체적인 회전수를 줄일 수 있고, 이걸 계속 반복할 수 있습니다. 그렇게 1단계의 회전수가 충분히 많아서 2단계의 회전수가 없게 할 때까지 반복하거나 아니면 2단계의 회전수가 너무 적어서 1단계의 회전수를 더 줄일 필요 없을 수도 있죠. 그냥 최적의 1단계 솔루션과 최적의 2단계 솔루션을 하는 것보다 더 효율적입니다. 이론적으로는 이 방법은 언제나 최적의 회전수로 할 수 있습니다. 하지만 1990년대의 컴퓨터는 이 연산이 가능할 정도로 충분히 빠르지 않았죠.
앞서 살펴본 바와 같이 신의 수는 최소 18회전이었지만 이런 방식은 구조적인 증명이 아니었습니다. 최소 18회전이 걸려야 맞출 수 있는 상황의 존재성만 이론적으로 확인했을 뿐이죠. 하지만 슈퍼플립이라는 패턴은 하나의 전환점이 되었습니다.
