숫자 밀기 퍼즐 윗줄부터 맞추는 법과 마지막 두 장

숫자 밀기 퍼즐은 어느 타일을 어디로 보낼지보다 어떤 순서로 맞추느냐에서 갈립니다. 3×3 판은 풀리는 배치 181,440개를 전부 따져 보면 가장 먼 배치도 31수면 끝나고 평균은 21.97수입니다. 그런데 윗줄, 왼쪽 열, 마지막 2×2 순서로 한 겹씩 맞추는 방식은 같은 판을 평균 26~28수에 풉니다. 몇 수를 내주는 대신 생각할 것이 줄어듭니다. 이 글은 숫자 밀기 퍼즐의 규칙을 기준으로 그 순서와 마지막 두 장 처리 요령을 정리했고, 수치는 게임 엔진 위에서 직접 계산했습니다. 계산 조건은 아래 '계산 조건'에 적었습니다.

한눈에 보기

우리 게임의 규칙

• 판은 3×3, 4×4, 5×5입니다. 완성 배치는 1부터 차례로 놓고 오른쪽 아래 한 칸을 비운 모양입니다.
• 한 수는 타일 한 장이 한 칸 움직이는 것입니다. 빈칸과 같은 줄에 있는 먼 타일을 눌러 세 장을 한꺼번에 밀면 3수로 셉니다.
• 모든 판은 반드시 풀립니다. 섞은 배치가 풀리지 않으면 타일 두 장을 맞바꿔서 내보냅니다.
• 오늘의 판은 한국 시간 날짜와 크기로 정해져서 같은 날 같은 크기면 모두 같은 배치입니다.
• 3×3을 맞추면 결과 화면에 정확한 최소 이동이 나옵니다. 4×4와 5×5는 타일마다 제자리까지의 칸 수를 더한 값을 '○○수 이상'으로 보여 줍니다. 이 값은 하한입니다.

윗줄부터, 그다음 왼쪽 열

1. 윗줄을 1, 2, 3(4×4는 4까지)으로 채웁니다.
2. 왼쪽 열의 나머지를 채웁니다. 3×3이면 4와 7입니다.
3. 남은 판이 한 칸씩 작아집니다. 4×4는 3×3이 되고 5×5는 4×4가 됩니다. 같은 일을 반복합니다.
4. 2×2만 남으면 돌려서 끝냅니다.

이렇게 하는 이유는 맞춘 타일을 다시 건드릴 필요가 없는 범위가 점점 넓어지기 때문입니다. 3×3에서 윗줄 1, 2, 3을 맞추면 남는 것은 타일 다섯 장과 빈칸이 아래 두 줄 여섯 칸에 놓인 360가지뿐입니다. 이 360가지의 최단 수는 평균 12.62수, 가장 먼 것이 21수였습니다. 전체 181,440가지에서 360가지로 줄어드는 셈입니다.

이 방식의 비용도 계산했습니다. 3×3에서 이 순서(윗줄, 왼쪽 열 4·7, 마지막 2×2)를 따르되 각 단계를 그 단계만 놓고 가장 적은 수로 두면, 첫 단계인 윗줄 맞추기에만 평균 14.05수(가장 먼 판 22수)가 듭니다. 세 단계의 합은 같은 수로 끝나는 길이 여럿일 때 가장 유리한 길을 고르면 평균 25.97수, 가장 불리한 길을 고르면 27.84수였습니다. 정확한 최단 수 평균 21.97수와 비교하면 4~6수 정도를 내주는 셈이고, 이 방식으로 둔 결과가 최단 수와 같아지는 판은 유리한 길을 골랐을 때도 29.4%였습니다. 이 방식으로 가장 오래 걸린 판은 42~45수였습니다(최단 수로는 가장 먼 판이 31수). 4×4와 5×5는 이런 계산을 하지 못했습니다.

마지막 두 장은 따로 세운다

줄을 채우다 보면 마지막 두 장이 문제입니다. 3×3 윗줄에서 1과 2가 맞았다면 3만 오른쪽 위 모서리에 넣으면 될 것 같지만, 모서리 칸은 이웃이 둘뿐입니다. 하나는 2의 자리이고 다른 하나는 모서리 바로 아래 칸입니다. 빈칸이 모서리로 들어가려면 둘 중 하나를 건드려야 해서 맞춘 2를 흩어 놓게 됩니다.

요령은 마지막 두 장을 각자 제자리가 아니라 한 칸씩 어긋난 자리에 세워 두는 것입니다.

• 윗줄(3×3). 1을 맞춘 뒤 3을 2의 자리(가운데)에, 2를 3 바로 아래 칸에 놓고 빈칸을 오른쪽 위 모서리에 둡니다. 3을 오른쪽으로 밀고, 2를 위로 밀면 윗줄이 1, 2, 3으로 끝납니다. 두 수입니다.
• 4×4 윗줄. 같은 요령입니다. 4를 3의 자리에, 3을 그 바로 아래 칸에, 빈칸을 오른쪽 위 모서리에 둡니다. 4를 오른쪽으로, 3을 위로 밀면 1, 2, 3, 4가 됩니다.
• 왼쪽 열. 윗줄을 다 맞춘 뒤 4와 7이 남았다면 같은 요령을 옆으로 눕힙니다. 7을 4의 자리에, 4를 그 오른쪽 칸에 두고 빈칸을 왼쪽 아래 모서리에 둡니다. 7을 아래로, 4를 왼쪽으로 밀면 왼쪽 열이 1, 4, 7이 됩니다.

세워 두는 준비는 아직 맞추지 않은 칸에서 하니 맞춘 타일을 건드리지 않습니다. 세 가지 모두 엔진의 이동 함수로 직접 실행해 두 수 만에 완성되는 것을 확인했습니다. 4×4와 5×5에서 아래 두 줄이 남았을 때도 왼쪽 열부터 위아래 두 장씩 같은 요령으로 끝내 가면 됩니다.

마지막 2×2는 빈칸을 돌린다

3×3이라면 윗줄과 왼쪽 열을 맞춘 뒤 5, 6, 8과 빈칸이 오른쪽 아래 2×2에 남습니다. 이 네 칸은 어떻게 밀어도 한 장을 건너뛸 수 없어서, 타일 세 장이 빈칸을 따라 고리 모양으로 돌기만 합니다. 엔진으로 세어 보니 이 2×2에서 가능한 배치는 12가지이고, 12가지가 고리 하나로 이어져 있습니다. 빈칸을 한 방향으로 돌릴지 반대로 돌릴지 둘 중 하나이고, 가장 먼 배치도 6수면 끝납니다. 평균은 3수입니다.

4칸을 늘어놓는 방법은 24가지인데 왜 12가지일까요. 나머지 12가지는 아래에서 설명할 홀짝이 맞지 않아 풀리지 않는 배치입니다. 우리 게임은 풀리는 배치만 내보내므로, 윗줄과 왼쪽 열을 맞춘 뒤의 2×2는 언제나 이 12가지 중 하나입니다.

풀리는 배치의 홀짝

타일을 아무렇게나 섞으면 절반은 어떻게 해도 풀리지 않습니다. 3×3 배치 362,880개(9!)를 엔진의 검사 함수로 하나씩 확인했더니 풀리는 것은 181,440개로 정확히 절반이었고, 완성 배치에서 시작해 한 칸씩 움직이며 도달할 수 있는 배치 181,440개와 하나도 어긋나지 않았습니다. 1과 2만 맞바꾼 배치는 검사에서 풀 수 없는 것으로 나옵니다.

빈칸을 뺀 타일을 왼쪽 위부터 읽어 순서가 뒤집힌 쌍의 수를 역전 수라고 합니다. 완성 배치는 0입니다.

• 3×3과 5×5처럼 가로가 홀수인 판에서 가로 이동은 읽는 순서를 바꾸지 않고, 세로 이동은 타일 한 장이 두 장(5×5는 네 장)을 건너뛰어 역전 수가 +2, 0, -2만큼 바뀝니다. 3×3의 모든 이동을 확인했더니 그랬습니다. 그래서 홀짝은 변하지 않고, 역전 수가 짝수인 배치만 풀립니다.
• 4×4처럼 가로가 짝수인 판에서는 세로 이동이 타일 세 장을 건너뛰어 홀짝이 바뀌지만 빈칸의 줄도 한 줄 바뀝니다. 그래서 '역전 수 + 아래에서 센 빈칸 줄 번호(맨 아래가 1)'가 홀수일 때만 풀립니다. 완성 배치는 0 + 1입니다. 엔진도 이 검사를 씁니다.
• 4×4와 5×5에서는 한 칸씩 20만 번 무작위로 움직여 보았고, 매번 검사 결과가 '풀림'을 유지했습니다. 무작위로 섞은 4×4 20만 개 중 풀리는 것은 49.97%였습니다.
• 4×4에서 14와 15만 맞바꾼 배치는 역전 수 1에 아래에서 첫 줄이라 합이 짝수이고, 풀 수 없다고 나옵니다.

이 홀짝 구분은 1879년 Johnson과 Story가 미국수학저널에 실은 논문에서 이미 설명했습니다. 체스판처럼 칸에 색을 칠하면 한 번 움직일 때마다 빈칸의 칸 색이 바뀌므로, 빈칸이 원래 칸으로 돌아오려면 짝수 번 움직여야 하고, 그 결과 타일 배열은 짝수 번의 자리바꿈으로만 바뀐다는 논리입니다. 논문은 이 결론이 판의 모양과 상관없다고 적고 있습니다. 빈칸 자리는 그대로 두고 타일 두 장만 맞바꾼 배치는 어떤 크기의 판에서도 풀 수 없습니다.

3×3의 최단 수 분포

완성 배치에서 한 칸씩 움직이는 너비 우선 탐색으로 풀리는 배치 181,440개 모두의 최단 수를 구했습니다.

가장 먼 두 배치는 8 6 7 / 2 5 4 / 3 _ 1과 6 4 7 / 8 5 _ / 3 2 1입니다. 10수 안에 풀리는 판은 천 개 중 네 개꼴입니다.

게임 결과 화면에 나오는 '이론상 최소' 문구와도 연결됩니다. 타일마다 제자리까지의 칸 수를 더한 값은 3×3에서 최단 수보다 평균 7.97수 작았고, 둘이 같은 배치는 1.30%뿐이었습니다. 타일끼리 서로 길을 막고 비켜 주는 수가 평균 8수 가까이 필요하다는 뜻입니다. 4×4와 5×5의 '○○수 이상'은 정확한 최소가 아니라 그보다 한참 낮은 하한일 수 있습니다.

4×4는 엔진으로 전체를 계산하지 못했습니다. 다만 Korf와 Schultze(2005)가 완성 배치에서 빈칸이 모서리에 있을 때 가장 먼 배치까지의 거리가 80수이고, 그만큼 먼 배치가 정확히 17개라고 보고했습니다. 이 값을 처음 얻은 것은 Brüngger 등(1999)입니다. 풀리는 4×4 배치는 16!의 절반, 약 10.46조 개입니다.

오늘의 판 난이도

오늘의 판은 날짜와 크기로 정한 값으로 섞습니다. 섞은 뒤 풀리는지 검사하고, 너무 쉬운 판을 걸러 내려고 타일마다 제자리까지의 칸 수 합이 3×3은 10, 4×4는 24, 5×5는 44 미만이면 다시 섞습니다.

3×3은 풀리는 배치 가운데 칸 수 합이 10 미만인 것이 10,946개(6.03%)여서 이만큼이 빠집니다. 시드 1부터 100,000까지 만든 판 10만 개의 최단 수는 평균 22.25수로, 전체 평균 21.97수보다 조금 높았습니다. 범위는 10~31수였습니다.

2026년 10월 1일(한국 시간)의 판은 다음과 같습니다.

3×3 판은 칸 수 합이 12인데 최단 수가 24수여서, 평균 격차(약 8수)보다 타일끼리 길을 더 막는 판입니다. 4×4와 5×5의 최단 수는 계산하지 않아 '이상'으로만 적었습니다.

한 달 동안 어떻게 달라지는지도 같은 규칙으로 계산했습니다.

3×3 오늘의 판은 10월 어느 날이든 최단 수가 17~27수 안이라 전체 평균(21.97수)과 비슷한 수준입니다. 4×4는 칸 수 합이 26에서 47까지, 5×5는 58에서 93까지 날마다 오르내렸습니다. 전날보다 오래 걸렸다고 실력이 줄었다고 볼 일은 아닙니다.

계산 조건

• 엔진: 이 사이트의 숫자 밀기 퍼즐 엔진(engine.ts)의 이동·풀림 검사·칸 수 합·판 생성 함수를 그대로 불러다 썼습니다. 날짜 시드는 게임이 쓰는 계산식과 같게 옮겨 썼습니다.
• 3×3 최단 수는 완성 배치에서 시작하는 너비 우선 탐색으로 구했고, 엔진의 정확한 최단 수 함수(IDA*)가 무작위로 고른 300개에서 탐색 결과와 모두 일치하는 것을 확인했습니다.
• '층층이 맞추는 방식'의 계산은 단계 목표를 윗줄 완성, 윗줄과 왼쪽 열(4·7) 완성, 완성의 세 가지로 잡고, 각 단계를 맞춰 둔 칸을 깨지 않으면서 그 단계만 가장 적은 수로 두는 것으로 정의했습니다. 같은 수로 끝나는 길이 여럿이면 유리한 길과 불리한 길 둘 다 계산했습니다.
• 오늘의 판은 2026년 10월 1일부터 31일까지 날짜 시드로 만든 판입니다. 이후 게임의 판 생성 규칙이 바뀌면 달라질 수 있습니다.

흔한 실수

1. 마지막 두 장을 각각 제자리에 넣으려 하기. 앞의 그림처럼 한 칸씩 어긋나게 세워 두었다가 두 수로 끼우세요.
2. 맞춘 윗줄 위로 빈칸을 끌고 다니기. 빈칸은 아직 맞추지 않은 아래쪽에서 돌리세요.
3. 줄을 깨야 할 때 크게 흩뜨리기. 필요한 만큼만 풀고 바로 다시 맞추세요.
4. 마지막 2×2에서 한 장만 따로 옮기려 하기. 세 장이 같이 돕니다. 빈칸을 한 방향으로 돌리다가 맞는 순간 멈추세요. 최대 6수입니다.
5. 풀리지 않는 배치일까 의심하기. 우리 게임은 풀리는 배치만 냅니다.
6. 먼 타일을 눌러 한꺼번에 밀기. 손은 덜 가지만 이동 수는 밀린 타일 수만큼 늘어납니다.

연습 방법

• 3×3으로 요령 익히기. 윗줄 끝내기와 왼쪽 열 끝내기를 열 판씩 반복해 보세요.
• 같은 판을 두 번 풀기. '처음부터'로 같은 배치를 다시 풀어 보세요.
• 결과 화면의 최소 이동과 비교하기. 3×3에서 내 이동 수와 정확한 최소 이동의 차이를 확인하세요. 위 계산으로는 층층이 맞추는 방식이 평균 4~6수를 더 씁니다. 그 근처라면 순서대로 잘 푼 것입니다.
• 4×4로 넘어가기. 윗줄 네 장, 왼쪽 열 세 장을 끝낸 뒤 남은 3×3을 풉니다. '제자리 표시'를 켜고 시작하세요.

정리

숫자 밀기 퍼즐은 윗줄, 왼쪽 열 순서로 판을 한 겹씩 줄이고, 줄의 마지막 두 장은 한 칸 어긋나게 세워 두었다가 두 수로 끼우고, 마지막 2×2는 빈칸을 돌려 끝내는 것이 기본 순서입니다. 3×3은 풀리는 배치 181,440개의 최단 수가 평균 21.97수, 가장 먼 배치가 31수이고, 이 순서로 풀면 평균 4~6수를 더 쓰는 대신 생각할 것이 훨씬 줄어듭니다. 풀리는지 여부는 역전 수의 홀짝으로 정해지며, 우리 게임은 풀리는 배치만 내보냅니다. 읽은 내용은 숫자 밀기 퍼즐에서 바로 확인해 볼 수 있습니다.

참고 자료

• Wm. Woolsey Johnson, William E. Story (1879). Notes on the "15" Puzzle. American Journal of Mathematics 2(4), 397-404
• Richard E. Korf, Peter Schultze (2005). Large-Scale Parallel Breadth-First Search. AAAI-05