15 퍼즐
4×4 틀 안에 번호가 적힌 타일 15개와 빈칸 하나. 타일을 밀어서 1부터 15까지 다시 순서대로 놓고, 빈칸은 마지막 구석에 둡니다. ‘섞기’로 만든 배치는 모두 풀 수 있지만, 전체 배열의 절반은 풀 수 없으며, 그중 가장 유명한 것이 샘 로이드의 14-15입니다. 빈칸 옆의 타일을 클릭하면 빈칸으로 밀려 들어가고, 빈칸과 같은 가로줄이나 세로줄에서 더 멀리 있는 타일을 클릭하면 그 줄 전체가 밀립니다. 빈칸이 오른쪽 아래 구석에 오도록 타일을 다시 순서대로 놓으세요. ‘섞기’는 타일을 섞고, ‘풀기’는 길을 찾아 한 수씩 재생합니다.
작동 원리
- 빈칸 옆의 타일을 클릭하면 빈칸으로 밀려 들어갑니다. 같은 가로줄이나 세로줄에서 더 멀리 있는 타일을 클릭하면 그 줄 전체가 밀립니다.
- 왼쪽 위 구석의 1부터 타일을 다시 순서대로 놓고, 빈칸은 오른쪽 아래 구석에 두세요.
- 막혔나요? ‘풀기’를 누르면 끝까지 푸는 모습을 볼 수 있고, ‘단계’로 한 번에 한 수씩 볼 수도 있습니다. 그런 다음 PNG로 저장하세요.
하는 방법
빈칸 옆의 타일만 움직일 수 있고, 그 타일은 빈칸으로 들어갑니다. 빈칸과 같은 가로줄이나 세로줄에서 더 멀리 있는 타일을 클릭하면 그 사이의 모든 타일이 함께 밀립니다. 화살표 키는 빈칸의 그쪽에 있는 타일을 밉니다. ‘이동’은 움직인 타일을 하나하나 세고, ‘실행 취소’는 한 번의 밀기를 되돌립니다. ‘크기’는 3×3의 8 퍼즐, 15 퍼즐, 5×5의 24 퍼즐 사이를 전환합니다.
전체 배치의 절반은 풀 수 없다
타일 두 개를 꺼내 서로 바꾸면 퍼즐은 다시는 풀 수 없습니다. 밀 때마다 빈칸이 타일 하나와 자리를 바꾸고, 빈칸이 제 구석으로 돌아오려면 짝수 번 밀어야 하므로, 타일은 짝수 번의 교환으로만 재배열될 수 있습니다. 교환 한 번은 홀수 번입니다. 16칸을 채우는 20,922,789,888,000가지 방법 가운데 정확히 절반에 도달할 수 있습니다. 로이드의 14-15는 나머지 절반에 속합니다.
‘풀기’의 원리
‘풀기’는 A*로 되돌아가는 길을 찾습니다. 각 타일이 제자리에서 얼마나 떨어져 있는지를 기준으로 삼고, 제 가로줄이나 세로줄에 있지만 순서가 뒤바뀐 타일 쌍마다 2번의 이동을 더합니다. 3×3 판에서는 가장 짧은 풀이를 찾으며, 그 풀이는 31번을 넘지 않습니다. 더 큰 판에서는 오래 탐색해야 할 수도 있는 가장 짧은 풀이 대신, 바로 찾은 짧은 풀이로 만족합니다. 4×4에서 가장 어려운 배치는 80번이 필요합니다.
자주 묻는 질문
15 퍼즐은 모두 풀 수 있나요?
전체 배열의 절반만 풀 수 있습니다. 4×4 판에서는 순서가 뒤바뀐 타일 쌍의 수에 빈칸이 아래에서 몇 번째 줄에 있는지를 더한 값이 홀수일 때 풀 수 있습니다. ‘섞기’는 풀 수 있는 배치만 만듭니다.
샘 로이드의 14-15 퍼즐은 무엇인가요?
완성된 순서에서 14와 15를 맞바꾼 것입니다. 로이드는 이것을 푸는 사람에게 1,000달러의 상금을 준다고 했지만, 어떤 밀기 순서로도 풀 수 없습니다. 한 번의 교환은 홀수 재배열이고, 밀기는 짝수 재배열만 만들기 때문입니다.
풀이에는 몇 번 이동이 필요한가요?
15 퍼즐에서 가장 어려운 배치는 80번이 필요하고, 무작위 배치는 아무리 잘해도 약 50번이 걸립니다. 8 퍼즐은 31번을 넘지 않습니다. ‘풀기’는 3×3에서는 가장 짧은 풀이를, 더 큰 판에서는 늘 가장 짧지는 않은 짧은 풀이를 찾습니다.
왜 한 번 클릭했는데 타일 여러 개가 움직이나요?
빈칸과 같은 가로줄이나 세로줄의 타일을 클릭하면, 그 타일과 빈칸 사이의 모든 타일이 함께 밀립니다. 실제 퍼즐에서 타일을 밀 때와 같습니다. ‘이동’은 움직인 타일을 하나하나 셉니다.
무언가 업로드되나요?
아니요. 퍼즐은 브라우저의 캔버스에 그려집니다. ‘저장’은 PNG를 받습니다. ‘편집’은 그 이미지를 PictorX 편집기에서 엽니다.
관련 도구
15 퍼즐
슬라이딩 퍼즐인 15 퍼즐의 역사와 수학: 1880년의 열풍, 샘 로이드의 14-15, 전체 배치의 절반을 풀 수 없다는 홀짝성 증명, 그리고 컴퓨터가 푸는 방법.
하노이의 탑
브라우저에서 원판 탑을 기둥 세 개 사이로 옮겨 보세요. 한 번에 하나씩, 큰 원판은 절대 작은 원판 위에 놓지 않습니다. 가장 짧은 풀이는 2ⁿ − 1번입니다.
나이트 투어
체스의 나이트를 뛰게 해서 판의 모든 칸을 정확히 한 번씩 방문하세요. 바른스도르프 힌트를 보며 직접 해 보거나, ‘풀기’가 열린 투어나 닫힌 투어를 완성하는 모습을 지켜보세요. 경로는 PNG로 저장할 수 있습니다.
8퀸
체스판에 퀸 8개를 서로 공격하지 않도록 놓아 보세요. 직접 해 보고, 백트래킹 탐색이 한 단계씩 풀이를 찾는 모습을 보고, 92가지 풀이를 모두 둘러보세요.
랭턴의 개미
브라우저에서 랭턴의 개미를 실행하세요. 대칭, 혼돈, 104걸음 고속도로를 지켜본 뒤 여러 색 규칙, 여러 마리의 개미, 육각 격자, 터마이트를 시험해 보세요.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집자로 이동