15퍼즐 푸는 법, 줄 단위 공식과 안 풀리는 배치 판별법

15퍼즐(슬라이딩 퍼즐)을 처음 잡으면 1·2·3까지는 금방 맞추는데, 4를 넣으려는 순간 3이 빠져나가고 아래 줄은 아예 손을 못 대는 경우가 많아요. 결론부터 말하면 15퍼즐은 윗줄부터 한 줄씩 끝내고, 끝난 줄은 다시 건드리지 않으며, 줄 끝의 두 칸(3·4)은 "세워 두었다가 한 번에 돌려 넣고", 마지막 두 줄은 세로 짝(9·13, 10·14)으로 맞추면 누구나 풀 수 있어요. 외울 공식은 사실상 이 하나예요.

이 글에서는 줄 단위 풀이 순서, 줄 끝 두 칸을 넣는 요령, 마지막 2×4 영역 처리법을 단계별로 설명하고, 무작위로 섞은 배치의 정확히 절반이 왜 절대 풀리지 않는지 역전 수(inversion)로 직접 계산해 볼게요. 3×3·4×4·5×5가 얼마나 다른지, 컴퓨터가 찾은 최단 이동 수가 몇인지도 확실한 숫자만 골라 정리했어요. 슬라이딩 퍼즐 게임을 옆에 켜 두고 따라 하면 바로 체감돼요.

핵심 요약

풀이 순서는 첫 줄(1~4) → 둘째 줄(5~8) → 세로 짝 9·13 → 10·14 → 마지막 2×2(11·12·15) 회전이에요.

줄 끝의 두 칸은 하나씩 넣으면 서로 밀어내요. 4를 3 자리에, 3을 그 바로 아래에 세워 두고 빈칸을 돌려 한 번에 넣어요.

4×4에서는 "역전 수 + 빈칸이 아래에서 몇 번째 줄인지"가 홀수여야 풀려요. 타일을 아무렇게나 섞으면 정확히 절반이 안 풀리는 배치예요.

최단 이동 수의 최댓값은 8퍼즐 31번, 15퍼즐 80번(타일 한 칸 이동 기준)이에요. 사람 공식은 최단보다 몇 배 많이 움직이지만 확실하게 풀려요.

15퍼즐 규칙과 이 게임의 기본 조작

15퍼즐은 4×4 판에 1부터 15까지 타일 15개와 빈칸 하나가 있고, 빈칸 옆 타일을 밀어 1, 2, 3, …, 15 순서(빈칸은 오른쪽 아래)로 맞추는 퍼즐이에요. 3×3은 8퍼즐, 5×5는 24퍼즐이라고 불러요.

슬라이딩 퍼즐 게임은 3×3·4×4·5×5를 고를 수 있고, 조작은 이래요.

이동 수는 움직인 타일 개수로 세요. 한 번 클릭으로 타일 3개를 밀면 3번 이동이에요. 퍼즐 이론에서 쓰는 "타일 한 칸 이동" 기준과 같아서, 아래에 나오는 최단 이동 수와 그대로 비교할 수 있어요. 시간은 첫 이동부터 재고, 다른 탭에 가 있는 동안은 멈춰요. 제자리에 들어간 타일은 색이 바뀌고 "맞은 칸" 개수도 보여 줘서 진행 상황을 확인하기 좋아요.

섞을 때는 무작위로 섞은 뒤 풀 수 없는 배치면 빈칸이 아닌 타일 두 개를 맞바꿔 풀 수 있게 고쳐요. 그래서 이 게임에서 나오는 배치는 항상 풀려요. 왜 두 개를 바꾸면 고쳐지는지는 뒤의 홀짝 설명에서 나와요.

15퍼즐 푸는 순서: 윗줄부터 한 줄씩

핵심 원칙은 하나예요. 끝낸 줄은 다시 건드리지 않는다. 그러면 퍼즐이 점점 작아져요. 4×4에서 위 두 줄을 끝내면 남는 건 2×4 영역뿐이고, 5×5에서는 첫 줄과 첫째 열을 끝내면 4×4가 남아요.

1단계: 1과 2는 그냥 옮겨 넣기

1을 왼쪽 위로 옮기는 건 어렵지 않아요. 요령은 타일을 움직이는 게 아니라 빈칸을 움직인다고 생각하는 것이에요. 타일을 한 칸 왼쪽으로 옮기고 싶으면 먼저 빈칸을 그 타일의 왼쪽으로 데려온 뒤 타일을 밀어요. 타일을 여러 칸 옮길 때는 빈칸이 타일 주위를 시계 방향이나 반시계 방향으로 돌면서 한 칸씩 끌고 간다고 보면 돼요.

2도 같은 방법으로 1 오른쪽에 넣어요. 이때 빈칸이 이미 맞춘 1을 지나가지 않게, 빈칸은 항상 아래쪽으로 돌아서 움직여요.

2단계: 3과 4는 "세워 두고" 한 번에 넣기

여기서 대부분 막혀요. 3을 넣고 4를 넣으려 하면 4 자리로 가는 길이 3 자리를 지나가야 해서 3이 빠져요. 해결책은 이래요.

1. 4를 3의 자리(첫 줄 셋째 칸)에 먼저 넣어요.
2. 3을 4 바로 아래(둘째 줄 셋째 칸)에 넣어요. 이때 4가 흐트러지지 않게 빈칸은 아래쪽으로 돌려요.
3. 빈칸을 4의 목표 자리(첫 줄 넷째 칸)로 데려와요. 빈칸을 둘째 줄 넷째 칸으로 가져온 다음 위로 올리면 돼요.
4. 4를 오른쪽으로, 3을 위로 밀면 3과 4가 동시에 제자리에 들어가요.

만약 4가 이미 첫 줄 셋째 칸, 3이 넷째 칸처럼 뒤집혀 들어가 있으면 이 방법이 안 통해요. 그때는 둘 중 하나를 아래 영역으로 빼낸 뒤 1번부터 다시 하는 게 가장 빨라요. 처음엔 손해 같아도 결국 이게 지름길이에요.

3단계: 둘째 줄도 똑같이

5와 6은 그냥 넣고, 7과 8은 3·4와 같은 방법으로 "8을 7 자리에, 7을 그 아래에" 세운 뒤 돌려 넣어요. 이제 위 두 줄은 끝났고, 이후로는 절대 위 두 줄에 빈칸을 올리지 않아요.

마지막 두 줄 푸는 법: 세로 짝으로 맞추기

남은 2×4 영역(9~15와 빈칸)은 가로줄로 풀 수가 없어요. 아래 두 줄밖에 없어서 줄 끝 두 칸을 세울 공간이 없거든요. 그래서 이번에는 방향을 90도 돌려 왼쪽 세로줄부터 풀어요.

1. 9와 13을 짝으로 넣어요. 원리는 3·4와 같아요. 13을 9의 자리(셋째 줄 첫째 칸)에, 9를 13의 오른쪽(셋째 줄 둘째 칸)에 나란히 세운 뒤, 빈칸을 13의 목표 자리(넷째 줄 첫째 칸)로 데려와 13을 아래로, 9를 왼쪽으로 밀어요.
2. 10과 14도 같은 방법으로 넣어요. 이제 남은 건 오른쪽 아래 2×2 칸(11, 12, 15, 빈칸)뿐이에요.
3. 2×2 칸은 빈칸을 한 방향으로 돌리기만 하면 돼요. 세 타일이 원을 그리며 돌다가 정답 배치가 나오는 순간 멈추면 끝이에요.

여기서 2×2를 아무리 돌려도 11·12·15가 안 맞는다면, 그건 배치 자체가 풀 수 없는 경우예요(직접 타일을 빼서 섞은 실물 퍼즐에서 생겨요). 이 게임에서는 그런 배치가 나오지 않아요.

15퍼즐 절반이 안 풀리는 이유: 역전 수와 홀짝

실물 15퍼즐에서 타일을 빼서 아무렇게나 다시 끼우면 정확히 절반의 확률로 영원히 풀리지 않는 배치가 돼요. 유명한 예가 14와 15만 서로 바뀐 배치예요. 15퍼즐은 1880년 무렵 미국에서 크게 유행했는데, 이 "14·15 문제"가 풀 수 없다는 사실은 그 무렵 수학 논문으로 이미 증명됐어요.

역전 수 세는 법 (예시 계산)

역전(inversion) 은 빈칸을 빼고 타일을 왼쪽 위부터 읽었을 때, 큰 수가 작은 수보다 앞에 오는 쌍의 개수예요. 위 그림 왼쪽 배치로 직접 세 볼게요.

 5  1  2  4
 9  6  3  8
13 10  7 11
14 15 12  _

읽는 순서는 5, 1, 2, 4, 9, 6, 3, 8, 13, 10, 7, 11, 14, 15, 12예요. 각 수 뒤에 나오는 더 작은 수를 세면,

합계는 18개예요.

4×4 판정 규칙

가로 칸 수가 짝수인 4×4에서는 역전 수만으로는 안 되고, 빈칸이 아래에서 몇 번째 줄에 있는지를 더해요(맨 아랫줄 = 1).

• 역전 수 + 빈칸 줄(아래에서) = 홀수면 풀림, 짝수면 안 풀림
• 왼쪽 예시: 18 + 1 = 19 → 홀수 → 풀려요
• 14·15 바뀐 배치: 역전 1개(15가 14보다 앞에 오는 한 쌍) + 1 = 2 → 짝수 → 안 풀려요
• 완성 상태: 역전 0 + 1 = 1 → 홀수 (기준점)

3×3(8퍼즐)과 5×5 판정 규칙

가로 칸 수가 홀수인 3×3과 5×5는 더 간단해요. 역전 수가 짝수면 풀리고, 홀수면 안 풀려요. 빈칸 위치는 상관없어요. 예를 들어 8퍼즐 배치 8 1 3 / 4 _ 2 / 7 6 5는 읽는 순서 8, 1, 3, 4, 2, 7, 6, 5에서 8이 뒤의 7개 수보다 커서 7개, 3과 4가 각각 2보다 커서 2개, 7이 6과 5보다 커서 2개, 6이 5보다 커서 1개, 합계 12개라 짝수 → 풀려요.

왜 이 규칙이 성립할까

• 가로로 밀기: 빈칸과 타일이 같은 줄에서 자리를 바꾸므로 읽는 순서가 그대로예요. 역전 수가 변하지 않아요.
• 세로로 밀기: 타일 하나가 읽는 순서에서 (가로 칸 수 − 1)개의 타일을 건너뛰어요. 3×3이면 2개, 5×5면 4개를 건너뛰니 역전 수가 짝수만큼 변해서 홀짝이 그대로예요. 4×4면 3개를 건너뛰어 역전 수 홀짝이 뒤집히는데, 동시에 빈칸이 한 줄 위나 아래로 가서 빈칸 줄 번호의 홀짝도 뒤집혀요. 둘을 더한 값의 홀짝은 그대로예요.

즉 어떤 이동을 해도 이 홀짝 값은 바뀌지 않으니, 완성 상태와 홀짝이 다른 배치는 영원히 완성에 닿을 수 없어요. 그리고 빈칸이 아닌 타일 두 개를 맞바꾸면 역전 수의 홀짝이 정확히 한 번 뒤집혀요. 그래서 풀리는 배치와 안 풀리는 배치가 일대일로 짝지어지고, 무작위 배치의 정확히 절반이 안 풀리는 거예요. 이 게임이 안 풀리는 배치가 나오면 타일 두 개를 바꿔 고치는 것도 같은 원리예요.

3×3, 4×4, 5×5 차이와 최단 이동 수

크기가 한 단계 커질 때마다 경우의 수는 폭발적으로 늘어요. 풀 수 있는 배치 수는 (칸 수)! ÷ 2예요.

최단 해의 최댓값은 "어떤 배치든 이 횟수 안에 풀 수 있다"는 뜻의 숫자로, 흔히 "신의 수(God's number)"라고 불러요. 모두 타일 한 칸 이동을 1번으로 센 기준이에요. 8퍼즐은 경우의 수가 18만 개뿐이라 노트북으로도 전부 계산할 수 있어서 직접 돌려 봤어요. 완성 상태에서 거꾸로 너비 우선 탐색을 하면 181,440가지 배치 전부의 최단 거리가 나와요.

8퍼즐은 무작위 배치의 대부분이 20~27번 사이에서 풀려요. 이 게임 3×3에서 이동 수가 30번 안쪽이면 최단 해에 꽤 가까운 거예요. 15퍼즐은 무작위 배치의 최단 해가 평균 50번대 초반으로 알려져 있는데, 사람이 줄 단위 공식으로 풀면 보통 그보다 몇 배 많이 움직여요. 최단 해를 찾는 건 컴퓨터도 IDA* 같은 탐색 알고리즘이 필요한 일이라, 사람은 이동 수보다 "막히지 않고 끝까지 푸는 것"을 먼저 목표로 하는 게 맞아요.

5×5는 첫 줄과 첫째 열을 끝내면 4×4가 남으니 공식은 같아요. 다만 줄 끝 두 칸 넣기를 더 여러 번 해야 해서 시간이 두세 배 걸려요.

15퍼즐 빨리 푸는 요령

1. 빈칸 위치를 먼저 보기: 다음 타일을 옮기기 전에 빈칸이 어느 쪽으로 돌아가야 하는지 경로를 정해요. 빈칸 경로가 끝난 줄을 지나가면 다른 길을 찾아요.
2. 여러 칸 한꺼번에 밀기: 이 게임은 빈칸과 같은 줄의 타일을 클릭하면 사이의 타일이 한꺼번에 밀려요. 이동 수는 같아도 클릭 수가 줄어 시간이 빨라져요.
3. 다음 타일을 미리 근처로: 1을 옮기는 동안 2가 근처로 오게 빈칸 경로를 고르면 다음 단계가 짧아져요. 숙련자는 이걸 몇 타일 앞까지 계획해요.
4. 키보드나 스와이프 한쪽으로 통일: PC에서는 방향키가 손이 가장 덜 움직여요. 방향키는 "타일이 움직이는 방향" 기준이라는 점만 익숙해지면 돼요.
5. 3×3으로 감 잡기: 8퍼즐은 같은 원리를 작은 판에서 연습할 수 있어요. 첫 줄 1·2·3에서 2·3 세워 넣기, 마지막 2×3 영역에서 4·7 세로 짝 넣기를 연습하면 4×4가 쉬워져요.

처음에는 4×4 한 판에 몇 분씩 걸려도 정상이에요. 공식이 손에 익으면 1~2분 안쪽으로 금방 줄어요. 시간 기록보다 이동 수 기록을 줄이고 싶다면, 빈칸이 같은 자리를 왔다 갔다 하는 "헛걸음"을 줄이는 게 가장 효과가 커요.

15퍼즐 흔한 실수

• 3·4를 하나씩 넣으려고 계속 시도하기: 넣는 순간 다른 하나가 빠져요. 세워 두고 한 번에 넣는 방법을 쓰세요.
• 끝난 줄로 빈칸을 올리기: 길이 짧아 보여도 이미 맞춘 타일이 흐트러지면 몇 배로 손해예요.
• 마지막 두 줄을 가로로 풀기: 공간이 부족해 거의 안 풀려요. 세로 짝으로 바꾸세요.
• 2×2가 안 맞는다고 계속 돌리기: 세 바퀴 넘게 돌려도 안 맞으면 앞 단계의 짝이 틀어진 거예요. 실물 퍼즐이라면 배치 자체가 안 풀리는 경우일 수도 있어요.

자주 묻는 질문

15퍼즐은 어떤 배치든 다 풀 수 있나요?

아니요. 타일을 빼서 아무렇게나 끼우면 정확히 절반은 절대 풀리지 않아요. 4×4는 역전 수와 빈칸 줄 번호(아래에서)의 합이 홀수일 때만 풀려요. 이 사이트의 슬라이딩 퍼즐은 항상 풀리는 배치만 내요.

15퍼즐 최소 몇 번이면 풀 수 있나요?

배치마다 달라요. 어떤 배치든 타일 한 칸 이동 기준 80번 안에 풀 수 있다는 것이 컴퓨터로 증명돼 있고, 무작위 배치의 최단 해는 평균 50번대 초반이에요. 8퍼즐은 최대 31번, 평균 약 22번이에요.

3과 4를 넣으면 자꾸 하나가 빠져요. 어떻게 하나요?

4를 3의 자리에, 3을 그 바로 아래에 세워 두고 빈칸을 4의 목표 자리로 데려와 4를 오른쪽, 3을 위로 밀면 한 번에 들어가요. 마지막 두 줄의 9·13, 10·14도 같은 원리로 세로 짝을 넣어요.

8퍼즐과 15퍼즐 중 무엇부터 연습하는 게 좋나요?

8퍼즐로 원리를 익히고 15퍼즐로 넘어가는 걸 추천해요. 줄 끝 두 칸 세워 넣기와 세로 짝 넣기가 3×3에서도 똑같이 나와서, 작은 판에서 손에 익히면 4×4가 훨씬 빨라져요.

이 게임의 이동 수는 어떻게 세나요?

움직인 타일 개수로 세요. 한 번 클릭으로 타일 3개를 밀면 3번이에요. 그래서 위에 적은 최단 이동 수(타일 한 칸 이동 기준)와 그대로 비교할 수 있어요.

정리

15퍼즐 푸는 법은 "윗줄부터 한 줄씩, 줄 끝 두 칸은 세워서 한 번에, 마지막 두 줄은 세로 짝으로"가 전부예요. 안 풀리는 배치는 역전 수 홀짝으로 미리 가려낼 수 있고, 무작위 배치의 정확히 절반이 그런 배치예요.

슬라이딩 퍼즐 게임에서 3×3으로 감을 잡은 뒤 4×4, 5×5로 넘어가 보세요. 크기별 최고 시간과 최소 이동 수가 따로 기록돼요. 판을 읽는 퍼즐이 좋다면 2048 공략과 지뢰찾기 패턴 정리도 함께 읽어 보세요.