큐브가 아무리 심하게 뒤섞여 있어도, 컴퓨터는 언제나 20수 안팎의 해법을 눈 깜짝할 사이에 찾아냅니다. 이 블로그의 큐브 맞춰주는 사이트도 색만 입력하면 보통 21수 이내의 답을 즉시 계산하지요. 사람은 공식을 다 외워도 100수 가까이 걸리는데, 컴퓨터는 어떻게 이게 가능할까요? 그 비밀인 코시엠바(Kociemba) 2단계 알고리즘을 수식 없이 풀어서 설명해 보겠습니다.
4,325경 가지의 경우의 수
3×3 큐브가 만들 수 있는 상태의 수는 정확히 43,252,003,274,489,856,000가지, 약 4,325경입니다. 1초에 하나씩 상태를 확인한다면 다 보는 데 1조 년이 넘게 걸립니다. 우주의 나이(약 138억 년)의 100배쯤 되는 시간입니다.
그러니 “모든 경우를 다 따져보는” 방식은 애초에 불가능합니다. 그런데도 수학자들은 2010년, 구글의 컴퓨팅 파워를 빌려 놀라운 사실을 증명했습니다. 어떤 상태의 큐브든 20수 이내에 풀 수 있다는 것입니다. 이 20이라는 숫자에는 ‘신의 수(God’s Number)’라는 별명이 붙었습니다.
사람은 왜 100수나 걸릴까
사람이 배우는 해법(초보자용 LBL, 스피드큐빙용 CFOP)은 큐브를 한 층씩, 한 조각씩 맞춥니다. 이 방식의 약점은 명확합니다. 새 조각을 맞출 때마다 이미 맞춰둔 조각을 깨뜨리지 않으려고 빙 둘러 가는 회전을 반복해야 한다는 것이죠. 그래서 초보 해법은 100수 이상, 숙련자의 CFOP도 50~60수가 듭니다.
사람의 방법은 “외우기 쉬움”에 최적화되어 있고, 컴퓨터의 방법은 “수의 최소화”에 최적화되어 있는 셈입니다.
| 초보 해법(LBL) | CFOP | 코시엠바 알고리즘 | |
|---|---|---|---|
| 평균 수 | 100수 이상 | 50~60수 | 20수 안팎 |
| 방식 | 한 층씩 | 한 층씩 + 패턴 암기 | 전체를 한 번에 탐색 |
| 필요한 것 | 공식 몇 개 | 공식 수십~수백 개 | 컴퓨터 |
코시엠바의 발상 — 문제를 둘로 쪼갠다
1992년 독일의 수학 교사 헤르베르트 코시엠바(Herbert Kociemba)는 이렇게 생각했습니다.
“뒤섞인 상태에서 완성 상태까지 한 번에 가는 길을 찾는 건 너무 어렵다. 그렇다면 중간 휴게소를 하나 정해두고, 거기까지 가는 길과 거기서 완성까지 가는 길을 따로 찾으면 어떨까?”
자동차 여행에 비유하면 이렇습니다. 서울의 골목길에서 부산의 골목길까지 가는 최단 경로를 한 번에 계산하는 대신, 일단 가까운 고속도로 나들목까지 간 다음(1단계), 고속도로만 타고 부산까지 가는(2단계) 겁니다. 각 구간은 훨씬 단순해서 빠르게 계산할 수 있습니다.
1단계: 큐브를 ‘반쯤 정돈된 상태’로
코시엠바가 정한 중간 휴게소는 다음 세 가지 조건을 만족하는 상태입니다.
- 모서리 조각(엣지) 12개가 모두 뒤집히지 않은 방향일 것
- 꼭짓점 조각(코너) 8개가 모두 비틀리지 않은 방향일 것
- 가운데 층(허리띠)에 있어야 할 엣지 4개가 가운데 층 안에 있을 것
조각들의 “위치”는 아직 엉망이어도 됩니다. “방향”만 정돈하는 것이죠. 옷장 정리에 비유하면, 옷을 제자리에 넣기 전에 일단 모든 옷을 펴서 같은 방향으로 개어놓는 단계입니다. 어떤 큐브든 이 상태까지는 최대 12수면 도달합니다.
이 상태는 눈으로도 알아볼 수 있습니다. 아래 큐브를 보세요 — 옆면은 엉망인데, 윗면과 아랫면에는 흰색과 노란색만 모여 있습니다. 이것이 1단계가 끝났다는 신호입니다.
2단계: 제한된 회전만으로 완성
여기서부터가 이 알고리즘의 백미입니다. 1단계가 끝난 상태에서는 놀라운 성질이 생깁니다. 윗면과 아랫면은 자유롭게 돌리고, 옆면 4개는 180°로만 돌리면 — 조각들의 방향을 다시 흐트러뜨리지 않고 위치만 바꿀 수 있습니다. 고속도로에 일단 올라가면 신호등 없이 달릴 수 있는 것과 같습니다.
이렇게 회전을 제한하면 따져야 할 경우의 수가 극적으로 줄어듭니다. 전체 4,325경이던 탐색 공간이 1단계는 약 22억, 2단계는 약 195억 규모가 됩니다. 컴퓨터에게 수십억은 ‘작은 숫자’입니다. 2단계는 최대 18수면 끝납니다.
지름길만 밟는 요령 — 가지치기 테이블
수십억으로 줄었다 해도 무작정 더듬으면 느립니다. 코시엠바 알고리즘은 “이 상태에서 목표까지 최소 몇 수가 남았는지”를 미리 계산해둔 표(가지치기 테이블)를 들고 탐색합니다.
내비게이션과 똑같습니다. 갈림길마다 “이쪽으로 가면 남은 거리 최소 15수”라는 표지판이 붙어 있어서, 지금 찾고 있는 답(예: 10수짜리)보다 멀어지는 길은 들어가 보지도 않고 포기합니다. 덕분에 수십억 갈래 중 실제로 걸어보는 길은 극히 일부입니다.
한 가지 더: 알고리즘은 첫 해법을 찾았다고 멈추지 않습니다. “1단계를 조금 다르게 가면 2단계가 훨씬 짧아지지 않을까?”를 계속 시도하면서 더 짧은 해법으로 갱신합니다. 그래서 이론상 최대 30수(12+18)인 이 방법이 실제로는 거의 항상 20수 안팎의 답을 내놓습니다.
이게 브라우저에서 돌아간다고?
30년 전에는 PC로 몇 초가 걸리던 이 계산이, 지금은 자바스크립트로 포팅되어(min2phase.js) 브라우저 안에서 수십 밀리초 만에 끝납니다. 서버로 데이터를 보낼 필요조차 없습니다.
이 블로그의 3×3 큐브 자동 해법 페이지가 바로 이 알고리즘으로 동작합니다. 뒤섞인 큐브의 색을 입력하면 코시엠바 2단계 탐색이 즉시 실행되고, 찾아낸 해법을 3D 애니메이션으로 한 수씩 보여줍니다. 참고로 이런 솔버를 흔히 ‘인공지능’이라고 부르지만, 엄밀히는 학습하는 AI가 아니라 수학적 구조를 이용한 아주 영리한 탐색입니다. 어쩌면 그래서 더 아름답습니다. 43경 개의 미로에서 언제나 20걸음짜리 출구를 찾아내니까요.
정리
- 큐브의 상태는 약 4,325경 가지지만, 어떤 상태든 20수 이내에 풀 수 있다 (신의 수 = 20)
- 코시엠바 알고리즘은 문제를 “방향 정돈(1단계) → 위치 정돈(2단계)” 둘로 쪼개서 탐색 공간을 수십억 규모로 줄인다
- 가지치기 테이블로 가망 없는 길을 미리 잘라내고, 첫 답을 찾은 뒤에도 더 짧은 답을 계속 탐색한다
- 오늘날에는 이 모든 것이 브라우저 안에서 수십 밀리초 만에 실행된다
함께 보면 좋은 글
- 큐브 맞춰주는 사이트 – 3×3 무료 자동 해법 (3D) — 이 알고리즘을 직접 체험해 보세요
- 큐브 맞추는 방법 — 사람의 손으로 푸는 공식 정리
- 큐브 맞춰주는 사이트 비교 — 자동 해법 사이트들 총정리