못 푸는 배치가 생기는 이유(패리티)

15퍼즐 조각을 통에 쏟아붓듯 무작위로 늘어놓으면, 놀랍게도 딱 절반은 아무리 밀어도 풀리지 않습니다. 이건 실력 문제가 아니라 수학적으로 정해진 사실입니다. 이 글은 왜 그런지를 역위(inversion)와 패리티라는 개념으로 쉽게 풀어 봅니다.

최종 업데이트: 2026년 7월

1. 왜 절반만 풀릴까

조각 하나를 빈 칸으로 미는 이동은 사실 빈 칸과 조각의 자리를 맞바꾸는 것과 같습니다. 그런데 이 맞바꿈은 아무렇게나 일어나는 게 아니라 항상 일정한 규칙을 지킵니다. 그래서 완성된 상태에서 도달할 수 있는 배치와 도달할 수 없는 배치가 정확히 반반으로 갈립니다. 완성 상태에서 시작해 아무리 밀어도, 처음부터 반대편에 속한 배치로는 넘어갈 수 없습니다.

바로 이 때문에 "숫자만 무작위로 뒤섞기"는 위험합니다. 섞은 결과의 절반은 사용자가 몇 시간을 붙잡고 있어도 절대 완성할 수 없는 배치이기 때문입니다.

2. 역위: 순서가 뒤바뀐 횟수

배치가 어느 편에 속하는지는 역위(inversion)의 개수로 판별합니다. 역위란 조각을 왼쪽 위부터 오른쪽으로 한 줄로 죽 읽었을 때, 큰 번호가 작은 번호보다 앞에 나오는 쌍의 개수입니다. 빈 칸은 셈에서 빼고 읽습니다.

3. 풀 수 있는 배치의 조건

격자의 폭에 따라 조건이 조금 다릅니다.

• 폭이 홀수(3×3, 5×5)인 경우: 역위 개수가 짝수이면 풀 수 있습니다.
• 폭이 짝수(4×4)인 경우: 빈 칸이 있는 행을 맨 아래에서부터 셌을 때 그 값과 역위 개수를 더한 것이 홀수이면 풀 수 있습니다. 바꿔 말하면 빈 칸이 아래에서 홀수 번째 줄이면 역위가 짝수여야, 짝수 번째 줄이면 역위가 홀수여야 풀립니다.

규칙이 조금 복잡해 보이지만 핵심은 하나입니다. 역위(그리고 4×4에서는 빈 칸의 행)로 정해지는 패리티가 완성 상태와 같아야 풀 수 있다는 것입니다.

4. 이 도구는 어떻게 항상 풀리게 하나

못 푸는 배치를 피하는 방법은 두 가지입니다. 하나는 무작위로 섞은 뒤 위 공식으로 패리티를 검사해 풀 수 없으면 조각 두 개를 맞바꿔 고치는 방법입니다. 다른 하나는 더 간단하고 확실한데, 완성된 상태에서 실제로 가능한 이동만 무작위로 수백 번 적용하는 것입니다.

이 도구는 두 번째 방법을 씁니다. 완성 상태에서 빈 칸을 무작위 방향으로 계속 밀어 충분히 섞기 때문에, 나오는 배치는 정의상 완성 상태로 되돌릴 수 있는 배치입니다. 되돌아가는 길이 곧 푸는 길이니까요. 그래서 화면에 어떤 배치가 나와도 반드시 답이 있습니다. "혹시 못 푸는 것 아닐까" 하는 걱정 없이 마음껏 도전하면 됩니다.

5. 자주 묻는 질문

그럼 종이로 만든 15퍼즐도 못 푸는 경우가 있나요?

조각을 빼서 아무렇게나 다시 끼웠다면 그럴 수 있습니다. 유명한 일화로, 조각 14와 15만 뒤바꿔 끼운 배치는 절대 풀 수 없습니다. 역위가 딱 하나 어긋나 패리티가 반대편이 되기 때문입니다.

빈 칸도 역위 계산에 넣나요?

넣지 않습니다. 역위는 번호가 붙은 조각들끼리만 비교해서 셉니다. 다만 4×4처럼 폭이 짝수인 격자에서는 빈 칸이 몇 번째 줄에 있는지가 별도로 조건에 들어갑니다.

이 원리를 알면 게임에 도움이 되나요?

직접 푸는 손기술과는 별개지만, "지금 이 배치는 반드시 풀린다"는 확신을 줍니다. 안 풀리면 배치 탓이 아니라 조작 순서 문제라는 뜻이니, 침착하게 행·열 고정 공략으로 돌아가면 됩니다.