신의 수(God's number)에 대하여

루빅스 큐브는 헝가리 조각가이자 교수인 에르뇌 루빅 (Rubik Ernő) 교수가 1974년에 발명한 3x3x3 정육면체 모양의 퍼즐이다.

이 퍼즐의 발명 이후, 루빅스 큐브는 전세계적으로 많은 사랑을 받아 왔다. 수학자들 또한 루빅스 큐브에 대해 많은 관심을 가져왔는데, 그들이 관심을 가졌던 루빅스 큐브의 중요한 성질 중의 하나는, 루빅스 큐브의 회전변환들의 집합이 가지는 군(group)의 성질이다. 그리고 또 하나의 중요한 관심사가 바로 이번 글에서 설명할 루빅스 큐브의 신의 수(God's number)이다.

신의 수(God's number)

루빅스 큐브에 조금 관심이 있는 사람이라면, 루빅스 큐브로 만들 수 있는 모든 배열의 경우의 수는

\[ 43,252,003,274,489,856,000 \]

개라는 것을 알고 있을 것이다. 하지만 약 4300경 가지에 다다르는 서로다른 큐브의 배열 중 우리가 원하는 (즉, 퍼즐이 해결된 상태인) 배열은 단 한가지이다. 이렇게 루빅스 큐브를 맞추기 위해서는 일련의 큐브 해법을 사용하는데, 총 7단계의 과정을 통해 맞추는 가장 기본적인 초급 해법의 경우, 최초의 큐브 배열에 상관 없이 평균적으로 100회전이면 큐브를 맞출 수 있다. 또한 중급 해법으로 잘 알려진 프리드리히 해법(Fridrich method)를 이용하면, 평균적으로 56회전 정도에 큐브를 맞출 수 있음이 알려져 있다.

그렇다면 이 큐브 해법을 좀 더 발전시키면 임의로 섞인 큐브를 맞추는데 필요한 회전수를 얼만큼 줄일 수 있을까? 만약 신이 존재하여 큐브가 어떻게 섞여 있든지 상관 없이 필요한 가장 최소한의 회전수로 큐브를 맞출 수 있는 해법을 알고 있다고 한다면, 이 최소한의 회전수는 과연 몇 번일까? 즉, "(약 4300경 개의) 임의로 섞인 큐브를 맞추는데 필요한 최소한의 회전수"를 신의 수(God's number)라고 부르고, "임의로 섞인 큐브를 언제나 신의 수 이하의 회전수로 맞출 수 있게 해주는 해법"을 신의 해법(God's algorithm)이라 부른다.

신의 수의 발견 과정

신의 수에 대해서 설명 하기 전에 먼저 루빅스 큐브의 '회전수'에 대한 정의를 해야할 것 같다. 먼저 루빅스 큐브를 보았을 때, 윗면을 $U$, 아랫면을 $D$, 앞면을 $F$, 뒷면을 $B$, 오른쪽면을 $R$, 왼쪽면을 $L$이라 하자. 이제 임의의 면 $X \in \{U,\, D,\, F,\, B,\, R,\, L\}$에 대하여, $X$는 $X$면을 시계방향으로 90도 회전, $X'$은 $X$면을 반시계방향으로 90도 회전, 그리고 $X^2$는 $X$면을 180도 회전하는 것으로 정의한다. 이제 $X$, $X'$, $X^2$를 모두 1회전으로 간주하는 것을 하프 턴 방식(half turn metric)이라 하고, $X^2$를 2회전으로 처리하는 것을 쿼터 턴 방식(quarter turn metric)이라 한다. 예를 들어 어떤 큐브를 아래의 과정을 통해서 맞추었다고 하자.

\[ R\; U\; R'\; D^2\; F'\; L\; D\; B\; R^2\; L^2\; U' \]

그러면 이 큐브를, 하프 턴 방식으로는 11회전에 맞춘 것이지만, 쿼터 턴 방식으로는 14회전에 맞춘 것이 된다. 하지만 큐브의 회전수라고 하면 일반적으로 하프 턴 방식의 큐브 회전수를 의미한다.

신의 수의 역사는 1980년대로 거슬러 올라간다. 처음 신의 수 문제가 제기되었을 때 신의 수의 최솟값은 18, 최댓값은 52였다. 그리고 수십 년에 걸친 수학자들의 연구 끝에 이 두 값의 차를 점점 줄여 나가는데 성공하였고, 마침내 2010년 7월, 토마스 로키키(Tomas Rokicki), 헤르베르트 코침바(Herbert Kociemba), 몰리 데이비슨(Morley Davidson), 존 데스리지(John Dethridge)가 신의 수가 20이라는 것을 증명해내었다.

Date	Lower bound	Upper bound	Gap	Notes and Links
July, 1981	18	52	34	Morwen Thistlethwaite (UB: 52 moves)
December, 1990	18	42	24	Hans Kloosterman (UB: 42 moves)
May, 1992	18	39	21	Michael Reid (UB: 39 moves)
May, 1992	18	37	19	Dik Winter (UB: 37 moves)
January, 1995	18	29	11	Michael Reid (UB: 29 moves)
January, 1995	20	29	9	Michael Reid (LB: 20 moves)
December, 2005	20	28	8	Silviu Radu (UB: 28 moves)
April, 2006	20	27	7	Silviu Radu (UB: 27 moves)
May, 2007	20	26	6	Dan Kunkle, Gene Cooperman (UB: 26 moves)
March, 2008	20	25	5	Tomas Rokicki (UB: 25 moves)
April, 2008	20	23	3	Tomas Rokicki, John Welborn (UB: 23 moves)
August, 2008	20	22	2	Tomas Rokicki, John Welborn (UB: 22 moves)
July, 2010	20	20	0	Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge (UB: 20 moves)

이들은 Google 사의 컴퓨터들를 몇 주간 이용하여 신의 수가 정확히 20임을 증명하는데 성공하였다고 한다. 이들은 신의 수를 증명한 과정은 다음과 같다.

1. 약 4300경개의 모든 큐브의 배열을 약 195억개의 배열을 가진 22억개의 그룹으로 나눈다.
2. 큐브 배열의 대칭성(회전대칭과 거울대칭)을 이용하면 하나의 해법으로 최대 48개의 서로다른 배열을 맞출 수 있는데, 이를 이용하여 1에서 나눈 22억개의 그룹을 약 5500만개의 그룹으로 줄일 수 있다.
3. 이제 약 5500만개로 줄인 각각의 그룹을 컴퓨터를 이용하여 해결하는데, 굳이 각 배열 당 최소의 회전수를 찾을 필요는 없으므로 (단지 20회전 이하의 해법만 찾으면 된다) 계산 시간을 많이 줄일 수 있다.
4. 각 그룹에 있는 약 195개의 배열을 모두 해결하는데 약 20초 정도가 걸리는 효율적인 알고리즘을 개발한다.

이제 남은 일은 이들이 개발한 알고리즘을 이용하여 약 5500개의 모든 그룹이 최대 20회전 안으로 해결할 수 있는지 없는지를 확인하는 것이다. 이를 모두 해결하는데는

\[ [55,882,296 \times 20 (\text{sec})] \times \frac{1 (\text{min})}{60 (\text{sec})} \times \frac{1 (\text{hr})}{60 (\text{min})} \times \frac{1 (\text{day})}{24 (\text{hr})} \times \frac{1 (\text{year})}{365 (\text{day})} \simeq 35 (\text{year}) \]

약 35 CPU년이 걸린다고 한다. 이 문제를 증명하는데 사용된 코드는 http://www.cube20.org/src/에서 확인할 수 있다.

현재 신의 해법에 가장 가깝다고 평가받는 해법은 큐브 익스플로러라는 오픈소스 프로그램에서 사용하는 2상 알고리즘(2-phase algorithm)이다. 2상 알고리즘은 이름대로 두 단계에 걸쳐 큐브를 맞춘다. 첫 번째 단계는 모든 조각의 위치(permutation)를 맞추고, 두 번째 단계는 모든 조각의 방향(orientation)을 맞춘다. 그렇게 하나의 해법을 찾아내면, 첫 번째 단계의 공식의 길이를 늘리고 두 번째 단계의 공식의 길이를 짧게 하며 알고리즘을 반복한다. 그리고 두 번째 단계의 공식의 길이가 0이 되는 순간이 최소회전이다.

또한 하프 턴 방식에 의한 회전수가 아닌, 쿼터 턴 방식에 의한 회전수의 신의 수는 비교적 더 최근에 알려졌다. 쿼터 턴 방식에 의한 회전수의 신의 수는 26임이 최종적으로 2014년 토마스 로키키(Tomas Rokicki)와 몰리 데이비슨(Morley Davidson)에 의해 증명되었다. 이를 증명한 증명 과정은 하프 턴 방식의 회전수의 신의 수와 유사하므로 http://www.cube20.org/qtm/를 참고하도록 하자.

마지막으로 (총 3,674,160가지의 서로다른 배열을 가진) 2x2x2 큐브의 신의 수 또한 알려져 있는데, 이는 하프 턴 방식의 회전수의 경우 11회전, 쿼터 방식의 회전수의 경우 14라고 한다. 하지만 4x4x4 큐브나 그 이상의 큐브에 대한 신의 수에 대해서는 아직까지 알려진 바가 없다.

슈퍼플립(super-flip) 배열과 20회전

신의 수는 어떤 큐브의 배열이든지 간에 최악의 경우에도 20회전이면 맞출 수 있다는 사실을 보여준다. 하지만 (약 94.8%에 해당하는) 대부분의 배열이 17~18회전안에 맞출 수 있고, 20회전이 모두 필요한 큐브의 배열은 약 4억 9000만개 정도 밖에 되지 않는다고 한다. (비율로 따지면 약 0.000000001% 정도 밖에 되지 않는다.)

Distance	Count of Positions	Ratio
0	1	0.000000000000000
1	18	0.000000000000000
2	243	0.000000000000000
3	3,240	0.000000000000000
4	43,239	0.000000000000001
5	574,908	0.000000000000013
6	7,618,438	0.000000000000176
7	100,803,036	0.000000000002331
8	1,332,343,288	0.000000000030804
9	17,596,479,795	0.000000000406836
10	232,248,063,316	0.000000005369649
11	3,063,288,809,012	0.000000070824206
12	40,374,425,656,248	0.000000933469495
13	531,653,418,284,628	0.000012291995238
14	6,989,320,578,825,358	0.000161595303100
15	91,365,146,187,124,313	0.002112391086427
16	about 1,100,000,000,000,000,000	0.025432348023722
17	about 12,000,000,000,000,000,000	0.277443796622424
18	about 29,000,000,000,000,000,000	0.670489175170859
19	about 1,500,000,000,000,000,000	0.034680474577803
20	about 490,000,000	0.000000000011329

최초로 맞추는데 20회전이 모두 필요하다고 알려진 배열은 슈퍼플립(super-flip)이라고 불리는 배열이다. 슈퍼플립 배열을 맞추는데 적어도 20회전이 필요하다는 사실은 1995년 마이클 레이드(Michael Reid)이 증명하였다. 여기서 슈퍼플립 배열이란, 아래 그림과 같이 모든 코너 조각이 맞추어져 있고, 오직 엣지 조각들만 제 위치에서 방향이 전부 반대로 된 배열을 말한다.

실제로 이 배열을 맞추기 위해서는 아래와 같은 공식을 사용한다. (물론 이 외에도 무수히 많은 공식이 있지만 모두 20회전 이상이다.)

\[ R\; L\; U^2\; F\; U’\; D\; F^2\; R^2\; B^2\; L\; U^2\; F’\; B’\; U\; R^2\; D\; F^2\; U\; R^2\; U \]

회전수는 많이 필요하지만 실제로 핑거트릭이 가능하고 외우기도 쉬운 공식은

\[ (S\; U'\; S\; U'\; S\; U'\; S\; U')\; x\; y'\; (S\; U'\; S\; U'\; S\; U'\; S\; U')\; x\; y'\; (S\; U'\; S\; U'\; S\; U'\; S\; U') \]

가 있다. 현재까지 알려진 20회전이 모두 필요한 큐브 배열들에 관한 정보는 http://www.cube20.org/distance20s/에서 확인할 수 있다.