슬라이드 퍼즐 푸는 법: 위 줄부터 맞추는 순서와 15퍼즐 이야기

빈칸 하나로 움직이는 퍼즐

슬라이드 퍼즐은 네모난 판에 조각을 채우고 한 칸만 비워 둔 퍼즐이에요. 조각을 들어 옮길 수는 없고, 빈칸 옆의 조각을 빈칸 쪽으로 미는 것만 할 수 있어요. 그렇게 뒤섞인 조각을 1, 2, 3 순서로 되돌리거나 그림 한 장으로 완성하면 끝나요.

가장 널리 알려진 모양은 4×4 판에 조각 15개가 들어가는 '15퍼즐'이에요. 어릴 때 플라스틱으로 된 작은 퍼즐을 만져 본 사람도 많을 거예요. 이 사이트의 슬라이드 퍼즐은 4×4부터 8×8까지 고를 수 있고, 조각은 숫자·그림+번호·그림 세 가지예요.

처음 해 보면 앞의 몇 조각은 금방 맞추다가 뒤로 갈수록 이미 맞춘 조각을 흐트러뜨리게 돼서 막막해져요. 그런데 이 퍼즐에는 칸 수와 상관없이 쓸 수 있는 정해진 순서가 있어요. 순서만 알면 시간이 걸릴 뿐 반드시 풀 수 있어요. 이 글에서는 그 순서를 4×4 숫자 판을 예로 들어 설명하고, 이 퍼즐이 수학 문제로 유명해진 이야기까지 살펴볼게요.

기본 순서: 위 줄부터 한 줄씩

가장 중요한 원칙은 맞춘 줄은 다시 건드리지 않는다는 거예요. 4×4 판이라면 이런 순서로 진행해요.

1. 맨 윗줄 1, 2, 3, 4를 맞춰요. 2. 둘째 줄 5, 6, 7, 8을 맞춰요. 3. 아래 두 줄이 남으면 이제 줄이 아니라 왼쪽 세로줄부터 맞춰요. 9와 13, 그다음 10과 14예요. 4. 오른쪽 아래에 남은 네 칸에서 11, 12, 15를 빙글빙글 돌려 맞춰요.

이렇게 하면 윗줄을 맞출 때마다 판이 한 줄씩 작아지는 셈이에요. 5×5나 8×8도 똑같아요. 위에서부터 줄을 맞춰 내려오다가 두 줄이 남으면 왼쪽부터 세로로 맞추면 돼요. 칸 수가 커져도 할 일이 많아질 뿐, 방법이 달라지지는 않아요.

조각 하나를 옮길 때는 그 조각 자체를 움직이려 하기보다 빈칸을 조각 앞으로 데려간다고 생각하면 쉬워요. 조각을 왼쪽으로 옮기고 싶다면 빈칸을 그 조각의 왼쪽으로 돌려 보낸 뒤 조각을 밀어요. 한 칸 옮길 때마다 빈칸이 조각 둘레를 돌아 다시 앞으로 가야 해서 시간이 걸리지만, 이미 맞춘 줄을 건드리지 않고 원하는 곳까지 옮길 수 있어요.

줄 끝 두 조각은 함께 넣어요

1과 2는 차례대로 넣으면 어렵지 않아요. 문제는 3과 4예요. 3을 제자리에 넣고 나면 4가 들어갈 길이 막히거든요. 그래서 줄의 마지막 두 조각은 따로 넣지 않고 이어 붙여서 한 번에 넣어요.

4×4 맨 윗줄이라면 순서는 이래요.

1. 3을 오른쪽 위 구석, 즉 원래 4가 있어야 할 자리에 먼저 놓아요. 2. 4를 3의 바로 아래에 붙여요. 3. 빈칸을 3의 왼쪽, 즉 원래 3이 있어야 할 자리로 데려가요. 4. 3을 왼쪽으로 한 칸 밀고, 이어서 4를 위로 한 칸 밀어요.

3이 왼쪽으로 가면서 구석이 비고, 바로 아래에서 기다리던 4가 그 자리로 올라가는 거예요. 두 조각이 나란히 기차처럼 움직여서 한 번에 제자리에 들어가요. 둘째 줄의 7과 8도 똑같이 8 자리에 7을, 그 아래에 8을 놓고 시작해요.

가끔 3을 구석에 놓았는데 4가 하필 3 자리, 즉 바로 왼쪽 칸에 끼어 있을 때가 있어요. 이때는 억지로 해결하려 하지 말고, 4를 아래쪽으로 두세 칸 멀리 빼낸 다음 처음부터 다시 붙이는 게 빨라요. 맞춰 둔 1, 2는 그대로 두고 3과 4만 다시 움직이면 돼요.

마지막 두 줄과 네 칸 맞추기

줄이 두 개만 남으면 위아래로 움직일 여유가 없어서 줄 단위로는 맞출 수 없어요. 이때는 방향을 바꿔서 왼쪽 세로줄부터 맞춰요. 방법은 앞에서 본 줄 끝 넣기를 옆으로 눕힌 것과 같아요.

1. 9를 왼쪽 아래 구석, 즉 원래 13이 있어야 할 자리에 놓아요. 2. 13을 9의 바로 오른쪽에 붙여요. 3. 빈칸을 9의 위, 즉 원래 9가 있어야 할 자리로 데려가요. 4. 9를 위로 밀고, 이어서 13을 왼쪽으로 밀어요.

10과 14도 같은 방법으로 넣으면 오른쪽 아래에 네 칸만 남아요. 여기에는 11, 12, 15와 빈칸이 있어요. 이 네 칸 안에서는 조각을 시계 방향이나 반시계 방향으로 돌리는 것만 할 수 있어요. 돌리다 보면 세 조각이 함께 제자리에 들어오는 순간이 나와요.

이 사이트의 판은 여기서 끝나지 않아요. 다 맞추면 판 아래의 마지막 조각이 반짝이고, 이 조각을 눌러 끼워야 시간이 멈춰요. 마지막까지 손을 늦추지 마세요.

그림 판과 기록 줄이기

숫자 판에 익숙해지면 그림 판도 같은 순서로 풀 수 있어요. 다만 조각에 번호가 없으니 어느 조각이 어디로 가야 하는지를 그림에서 찾아야 해요.

• 그림+번호부터: 구석의 작은 번호를 보고 풀면서 그림에 눈을 익혀요. 번호 없는 그림 판은 가장 어려운 단계예요.
• 완성 모습 보기: 버튼을 꾹 누르는 동안 완성된 그림이나 숫자 판이 보여요. 조각 하나가 어디로 가는지 헷갈릴 때 확인해요.
• 윤곽과 색 따라가기: 하늘과 땅의 경계선, 캐릭터의 윤곽처럼 이어지는 선을 찾으면 옆 조각이 무엇인지 알기 쉬워요.
• 금빛 테두리 확인: 제자리에 들어간 조각은 테두리가 금빛으로 바뀌어요. 그림 판에서는 맞았는지 판단하는 좋은 기준이에요.

시간을 줄이고 싶다면 한 조각씩 밀기보다 같은 줄을 한꺼번에 미는 습관을 들여 보세요. 이 사이트에서는 빈칸과 같은 줄에 있는 조각을 누르면 그 조각부터 빈칸 쪽까지 한꺼번에 밀려요. 빈칸을 데려갈 때 멀리 있는 조각을 바로 누르면 여러 번 누를 것을 한 번에 끝낼 수 있어요. PC에서는 방향키로도 움직일 수 있어서, 손에 익으면 마우스보다 빠르게 풀 수 있어요.

매일 조금씩 해 보고 싶다면 오늘의 판이 좋아요. 자정마다 그림과 판이 바뀌고, 월요일부터 목요일까지는 4×4, 금요일부터 일요일까지는 5×5가 나와요.

절반은 풀 수 없다: 15퍼즐을 둘러싼 이야기

15퍼즐은 수학사에도 이름을 남긴 퍼즐이에요. 이 퍼즐을 만든 사람으로는 미국 뉴욕주 캐너스토타의 우체국장이던 노이스 채프먼(Noyes Chapman)이 꼽혀요. 1880년에는 미국에서 크게 유행했다고 해요.

그보다 조금 앞선 1879년에는 수학자 존슨(Johnson)과 스토리(Story)가 학술지에 이 퍼즐을 다룬 논문을 실었어요. 조각을 아무렇게나 늘어놓으면 그중 절반은 아무리 움직여도 풀 수 없다는 내용이에요. 조각을 옮기는 것만으로는 바꿀 수 없는 성질이 있어서, 판은 풀 수 있는 쪽과 없는 쪽으로 처음부터 나뉘어 있어요. 흔히 '짝홀성'이라고 불러요. 조각을 한 줄로 늘어놓았을 때 순서가 뒤바뀐 쌍의 개수가 짝수인지 홀수인지를 보는 방식이에요.

가장 유명한 예가 14와 15만 서로 바뀐 판이에요. 다른 조각은 모두 제자리인데 두 조각만 뒤바뀐 이 판은 절대 풀리지 않아요. 미국의 퍼즐 작가 샘 로이드(Sam Loyd)는 이 판을 풀면 1,000달러를 주겠다고 내걸었어요. 처음부터 불가능한 문제였던 셈이죠. 로이드는 1891년부터 세상을 떠난 1911년까지 자기가 이 퍼즐을 발명했다고 주장했지만, 지금은 발명이나 초기 유행과는 관계가 없었던 것으로 정리돼 있어요.

직접 확인해 봤어요. 이 사이트의 판 계산 코드로 조각을 완전히 무작위로 늘어놓고 풀 수 있는지 검사했더니, 20만 판 중 4×4는 49.88%, 5×5는 49.98%가 풀 수 있는 판이었어요. 이론대로 거의 절반이에요. 그래서 이 사이트의 판은 섞을 때 풀 수 있는 판인지 검사해요. 풀 수 없게 나오면 조각 두 개를 바꿔 풀 수 있는 판으로 만들어서, 모든 판이 반드시 풀려요. 칸 수별로 2,000판씩 섞어 확인했을 때도 풀 수 없는 판은 나오지 않았어요.

풀 수 있는 4×4 판은 16개의 칸에 놓는 경우의 수의 절반이라 약 10조 4,600억 가지예요. 그런데도 컴퓨터로 끝까지 계산해 보니, 어떤 판이든 80번 이내로 풀린다는 사실이 밝혀졌어요. 여기서 1번은 조각을 한 칸 옮기는 것을 뜻해요.

실제로 몇 칸이나 움직일까

위에서 소개한 순서대로 풀면 몇 칸이나 움직이게 될까요? 이 사이트의 검사 프로그램에 같은 순서로 풀게 해 봤어요. 위 줄부터, 줄 끝 두 조각은 함께, 아래 두 줄은 왼쪽부터 맞추되, 단계마다 가장 짧은 길을 컴퓨터가 찾게 했어요. 조각 한 칸 이동을 1로 센 평균이에요.

• 4×4: 평균 97칸 (300판)
• 5×5: 평균 215칸 (300판)
• 6×6: 평균 410칸 (60판)
• 7×7: 평균 700칸 (15판)
• 8×8: 평균 1,083칸 (15판)

7×7과 8×8은 판 수가 적어서 대략적인 값으로 봐 주세요. 그래도 판이 커질수록 할 일이 얼마나 빠르게 늘어나는지는 잘 보여요. 칸 수는 4×4의 16칸에서 8×8의 64칸으로 4배가 되는데, 움직일 양은 11배쯤 돼요. 먼 거리를 옮겨야 하는 조각이 많아지기 때문이에요.

4×4의 평균 97칸은 앞에서 본 80번이라는 한계보다 많아요. 줄 단위로 맞추는 방식은 맞춘 줄을 건드리지 않느라 돌아가는 길이 생기기 때문이에요. 대신 사람이 외우고 따라 할 수 있다는 큰 장점이 있죠. 사람은 컴퓨터처럼 가장 짧은 길을 찾기 어려우니 이보다 많이 움직이게 되는 게 보통이에요. 기록이 느리다고 실망할 필요는 없어요.

순서를 익혔다면 슬라이드 퍼즐에서 4×4부터 시작해 보세요. 숫자로 익힌 뒤 그림+번호, 그림 순서로 넘어가면 자연스러워요. 머리를 더 쓰는 문제가 좋다면 묘수풀이란?을 읽고 오늘의 문제도 풀어 보세요. 컴퓨터가 이런 문제를 어떻게 찾아가는지는 컴퓨터는 어떻게 다음 수를 고를까?에 정리했어요.