15퍼즐 조각을 아무렇게나 흩뿌리면 정확히 절반은 풀 수 없습니다
핵심 요약 — 15퍼즐 조각 열다섯 개와 빈칸을 아무렇게나 놓으면 그중 절반은 아무리 밀어도 못 맞춥니다. 20만 번 흩뿌려 세어 보니 풀 수 있는 배치가 50.23%였습니다. 8퍼즐(50.14%)도 24퍼즐(50.14%)도 같습니다. 그래서 우리 게임은 판을 흩뿌려 만들지 않고 맞춰 놓은 판을 거꾸로 밀어서 만듭니다 — 그렇게 만든 5,000판은 전부 풀 수 있었습니다.
15퍼즐에는 유명한 이야기가 있습니다. 19세기 말에 어떤 사람이 조각 두 개만 바꿔 놓은 판을 내걸고 "맞히면 상금 1,000달러"라고 했다는 것입니다. 아무도 못 받았습니다. 풀 수 없는 판이었기 때문입니다.
20만 번 흩뿌려 봤습니다
세 크기 전부, 조각을 완전히 무작위로 섞어 놓고 풀 수 있는 배치인지 판정했습니다.
| 판 | 조각 | 배치 가짓수 | 풀 수 있는 비율 |
|---|---|---|---|
| 3×3 (8퍼즐) | 8개 | 362,880 | 50.14% |
| 4×4 (15퍼즐) | 15개 | 20,922,789,888,000 | 50.23% |
| 5×5 (24퍼즐) | 24개 | 15,511,210,043,330,985,984,000,000 | 50.14% |
셋 다 절반입니다. 우연이 아니라 정확히 절반입니다 — 배치 가짓수를 정확히 2로 나눈 만큼만 풀립니다.
왜 하필 절반인가
조각을 한 칸 미는 동작이 무엇을 하는지 보면 답이 나옵니다.
조각을 밀 때마다 바뀌는 것은 딱 하나 — 빈칸과 조각 하나의 자리가 맞바뀝니다. 순서를 두 개만 맞바꾸는 것을 한 번 할 때마다, 수학에서 말하는 뒤집힘의 홀짝이 반드시 뒤집힙니다.
그런데 빈칸도 함께 한 칸 움직입니다. 그래서 다음 값을 함께 보면 그것이 절대 변하지 않습니다.
(순서가 뒤집힌 짝의 개수) + (빈칸이 아래에서 몇 번째 줄에 있는가)
이 합의 홀짝은 어떻게 밀어도 그대로입니다. 맞춰진 판에서 이 값이 짝수라면, 홀수인 배치는 영원히 짝수가 될 수 없습니다.
배치 전체는 이 값으로 두 무리로 정확히 갈립니다. 한쪽은 맞출 수 있고, 다른 한쪽은 서로서로는 오갈 수 있지만 맞춰진 판에는 절대 닿지 못합니다. 그래서 절반입니다.
19세기의 그 상금 문제는 조각 두 개를 바꿔 놓은 것이었습니다. 두 개를 바꾸면 홀짝이 뒤집히므로, 건널 수 없는 쪽으로 넘어간 판이었습니다.
그래서 우리는 흩뿌리지 않습니다
판을 만드는 방법이 두 가지 있습니다.
하나. 무작위로 흩뿌리고 풀 수 있는지 검사한다. 절반은 버려야 하지만 가능합니다.
둘. 맞춰진 판에서 거꾸로 밀어 섞는다. 실제로 미는 동작만 쓰므로, 나온 판은 정의상 되돌아갈 수 있습니다.
우리는 두 번째를 씁니다. 8퍼즐은 120번, 15퍼즐은 300번, 24퍼즐은 600번을 되밉니다. 되밀 때 방금 온 방향으로는 다시 가지 않게 해서 제자리를 맴도는 것을 줄입니다.
| 판 | 되미는 횟수 | 만든 판 | 풀 수 있는 판 |
|---|---|---|---|
| 8퍼즐 | 120회 | 5,000 | 5,000 (100%) |
| 15퍼즐 | 300회 | 5,000 | 5,000 (100%) |
| 24퍼즐 | 600회 | 5,000 | 5,000 (100%) |
검사할 것이 없습니다. 만드는 방법 자체가 보장합니다.
한 가지 예외를 따로 막습니다 — 되밀다 보면 우연히 맞춰진 판으로 돌아올 수 있습니다. 그 판은 낼 수 없으므로 다시 섞습니다.
되밀기 횟수는 왜 그만큼인가
되미는 횟수가 많다고 무한정 어려워지지는 않습니다. 어느 지점을 넘으면 판이 "가장 먼 곳"에서 더 멀어질 수 없기 때문입니다.
8퍼즐에서 맞춰진 판으로부터 가장 먼 배치는 31번이면 닿습니다. 15퍼즐은 80번, 24퍼즐은 그보다 훨씬 큽니다. 즉 8퍼즐을 아무리 오래 섞어도 서른한 번이면 풀립니다.
120·300·600번을 되미는 것은 어렵게 만들려는 것이 아니라 골고루 섞이게 하려는 것입니다. 스무 번만 밀면 원래 자리 근처에 남아 있는 조각이 많아 판이 쉬워 보입니다.
이 게임을 푸는 사람에게 남는 것
- 아무리 밀어도 안 되는 판은 여기 없습니다. 만드는 방법이 그것을 보장합니다.
- 한 조각씩 확정해 나가세요. 첫 줄을 맞추고 잠그고, 다음 줄로 갑니다. 마지막 2×2만 남기면 그 안에서 돌리는 문제가 됩니다.
- 막혔다고 느껴도 되돌릴 수 있습니다. 이 퍼즐에는 되돌아갈 수 없는 상태가 없습니다 — 밀어서 간 곳은 밀어서 돌아옵니다.
재현 방법. 풀 수 있는 비율은 배치를 완전히 무작위로 섞어 크기마다 20만 번 판정한 값입니다. 판정 기준은 "뒤집힌 짝의 개수 + 빈칸의 아래에서부터의 줄 번호"의 홀짝이고, 홀수 크기 판(3×3·5×5)은 뒤집힘 개수만 봅니다. 우리 판 검사는 lib/puzzle/fifteen.ts의 scramble()로 크기마다 씨앗 1~5,000번의 판을 만들어 같은 기준으로 판정했습니다.