15 퍼즐
15 퍼즐은 번호가 적힌 타일 15개와 빈칸 하나가 들어 있는 틀입니다. 타일을 밀어 다시 순서대로 놓으면 풀립니다. 단순해 보이지만 1880년에 열풍을 일으켰고, 그 뒤에는 오락 수학에서 가장 깔끔한 증명 가운데 하나가 있습니다. 전체 배치의 절반은 절대 풀 수 없다는 것입니다.
1880년의 열풍
이 퍼즐은 1870년대 뉴욕주에서 나왔습니다. 발명자로는 보통 카나스토타의 우체국장 노이스 채프먼이 꼽힙니다. 1880년 초에 이 퍼즐은 먼저 미국 전역에서, 이어서 유럽에서 열풍을 일으켰습니다.
샘 로이드의 14-15
미국의 퍼즐 작가 샘 로이드는 나중에 자신이 이 퍼즐을 발명했다고 주장했고, 14와 15만 바뀐 상태에서 퍼즐을 푸는 사람에게 1,000달러의 상금을 준다고 했습니다. 상금을 받은 사람은 없었고, 있을 수도 없었습니다. 그 배치는 풀 수 없기 때문입니다. 그가 발명했다는 주장도 사실이 아니었습니다.
배치의 절반이 불가능한 이유
빈칸을 16번째 타일로 생각해 보세요. 밀 때마다 빈칸이 타일 하나와 자리를 바꿉니다. 빈칸이 제 구석으로 돌아오려면 왼쪽으로 간 만큼 오른쪽으로, 위로 간 만큼 아래로 움직여야 하므로, 빈칸이 구석에 있는 배치는 언제나 완성된 순서에서 짝수 번의 교환만큼 떨어져 있습니다. 14와 15를 바꾸는 것은 한 번의 교환, 곧 홀수이므로 어떤 밀기로도 그 배치에 도달할 수 없습니다. 1879년 윌리엄 존슨과 윌리엄 스토리는 전체 배열의 정확히 절반에 도달할 수 있음을 증명했습니다.
어떤 배치에나 쓸 수 있는 판별법
틀을 한 줄씩 읽을 때 순서가 뒤바뀐 타일 쌍을 세어 보세요. 3×3이나 5×5 판에서는 그 수가 짝수일 때 풀 수 있습니다. 4×4 판에서는 빈칸이 아래에서 몇 번째 줄에 있는지를 더합니다. 그 합이 홀수일 때 풀 수 있습니다.
컴퓨터로 풀기
컴퓨터는 A*로 되돌아가는 길을 찾을 수 있습니다. A*는 언제나 가장 유망한 배치부터 살펴봅니다. 남은 이동 수는 각 타일이 제자리에서 얼마나 떨어져 있는지와, 제 가로줄이나 세로줄에서 서로 막고 있는 타일 쌍마다 더하는 2번으로 추정합니다. 판이 크면 가장 짧은 풀이를 찾기가 매우 어려워집니다. 15 퍼즐에서 가장 어려운 배치는 80번이 필요하고, 8 퍼즐은 31번을 넘지 않습니다.
PictorX에서 해 보기
15 퍼즐을 열고 타일을 클릭해 밀어 보세요. ‘섞기’는 타일을 섞어 풀 수 있는 새 배치를 만들고, ‘풀기’는 풀이를 한 수씩 재생하며, ‘제자리 타일 표시’는 이미 제자리에 있는 타일의 숫자에 색을 입힙니다. ‘로이드의 14-15’를 고르면 불가능한 배치를 볼 수 있고, ‘크기’로 3×3, 4×4, 5×5를 전환할 수 있습니다.
자주 묻는 질문
15 퍼즐은 누가 만들었나요?
보통 1870년대 뉴욕주 카나스토타의 우체국장 노이스 채프먼이 발명자로 꼽힙니다. 나중에 샘 로이드가 자신이 발명했다고 한 주장은 거짓이었습니다.
14-15 퍼즐은 풀 수 있나요?
아니요. 완성된 순서에서 교환 한 번만큼 떨어져 있는데, 밀기로 도달할 수 있는 배치는 모두 짝수 번의 교환만큼 떨어져 있습니다.
15 퍼즐에는 배치가 몇 가지 있나요?
16칸을 채우는 방법은 20,922,789,888,000가지입니다. 그중 정확히 절반인 10,461,394,944,000가지에 밀기로 도달할 수 있습니다.
PictorX가 무언가 업로드하나요?
아니요. 퍼즐은 브라우저의 캔버스에 그려집니다. ‘저장’은 PNG를 받고, ‘편집’은 그 이미지를 PictorX 편집기에서 엽니다.
관련 도구
15 퍼즐
고전 슬라이딩 퍼즐인 15 퍼즐을 브라우저에서 3×3, 4×4, 5×5 나무 타일로 즐겨 보세요. 타일을 섞고, 한 줄을 통째로 한 번에 밀고, 샘 로이드의 불가능한 14-15를 해 보거나, ‘풀기’가 끝까지 푸는 모습을 지켜보세요.
하노이의 탑
브라우저에서 원판 탑을 기둥 세 개 사이로 옮겨 보세요. 한 번에 하나씩, 큰 원판은 절대 작은 원판 위에 놓지 않습니다. 가장 짧은 풀이는 2ⁿ − 1번입니다.
하노이의 탑
하노이의 탑: 기둥 세 개, 한 번에 원판 하나, 큰 원판은 절대 작은 원판 위에 놓지 않기. 가장 짧은 풀이는 2ⁿ−1번입니다. 에두아르 뤼카가 1883년에 소개한 퍼즐입니다.
나이트 투어
체스의 나이트를 뛰게 해서 판의 모든 칸을 정확히 한 번씩 방문하세요. 바른스도르프 힌트를 보며 직접 해 보거나, ‘풀기’가 열린 투어나 닫힌 투어를 완성하는 모습을 지켜보세요. 경로는 PNG로 저장할 수 있습니다.
8퀸
체스판에 퀸 8개를 서로 공격하지 않도록 놓아 보세요. 직접 해 보고, 백트래킹 탐색이 한 단계씩 풀이를 찾는 모습을 보고, 92가지 풀이를 모두 둘러보세요.
랭턴의 개미
브라우저에서 랭턴의 개미를 실행하세요. 대칭, 혼돈, 104걸음 고속도로를 지켜본 뒤 여러 색 규칙, 여러 마리의 개미, 육각 격자, 터마이트를 시험해 보세요.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
15 퍼즐 해 보기