나이트 투어
나이트 투어는 체스판의 모든 칸을 정확히 한 번씩 방문하는 나이트의 연속된 수입니다. 오락 수학에서 가장 오래된 퍼즐 가운데 하나로, 9세기 인도의 한 시에 판의 절반을 도는 투어가 나오며, 레온하르트 오일러는 1759년에 이 퍼즐을 연구했습니다.
오래된 퍼즐
인도의 시인 루드라타가 9세기에 쓴 『카비얄랑카라』에는 한 시구가 체스판의 절반에 배치되어 있어 나이트의 경로를 따라 읽을 수 있습니다. 레온하르트 오일러는 1759년에 나이트 투어에 관한 최초의 수학적 연구를 썼고, 투어를 만드는 방법과 투어를 닫힌 투어로 바꾸는 방법을 제시했습니다.
그래프 속의 경로
각 칸을 점으로, 나이트의 각 수를 두 점을 잇는 선으로 생각해 보세요. 그러면 나이트 투어는 모든 점을 정확히 한 번씩 지나는 경로가 되는데, 수학자들은 이를 해밀턴 경로라고 부릅니다. 닫힌 투어는 해밀턴 순환입니다. 대부분의 네트워크에서는 이런 경로를 찾기가 매우 어렵습니다. 나이트의 네트워크는 너그럽습니다. 투어가 아주 많아서 좋은 규칙 하나면 금방 하나를 찾습니다.
바른스도르프 규칙
H. C. 폰 바른스도르프는 1823년에 자신의 규칙을 설명했습니다. 언제나 다음에 둘 수 있는 수가 가장 적게 남는 칸으로 뛰라는 것입니다. 가장자리를 따라 있는 칸은 이웃이 적으므로, 이 규칙은 그 칸들을 외톨이로 남겨 두지 않고 일찍 방문합니다. 두 칸이 동점이면 선택이 필요하고, 운 나쁜 선택을 하면 그래도 나이트가 막힐 수 있습니다. 앱에서는 금색 숫자가 이 규칙이 고를 칸을 표시합니다.
백트래킹으로 탐색하기
‘풀기’는 바른스도르프의 순서를 따르지만 무작정 믿지는 않습니다. 깊이 우선으로 탐색하다가, 아직 방문하지 않은 칸에 더 이상 닿을 수 없게 되는 순간 그 가지를 버리고 다음 수를 시도합니다. 10×10까지의 판에서는 대개 곧바로 투어를 찾습니다. 직접 만든 경로가 나이트를 가두어 버렸다면 먼저 몇 수 되돌아갑니다.
색과 닫힌 투어
나이트가 한 번 움직일 때마다 칸의 색이 바뀝니다. 5×5처럼 한 변이 홀수인 판에서는 구석 색의 칸이 다른 색보다 하나 더 많으므로, 투어는 구석 색에서 시작해 구석 색에서 끝나야 합니다. 그런 판에서는 닫힌 투어가 불가능합니다. 색이 번갈아 나오는 고리에는 두 색의 칸이 같은 수만큼 있기 때문입니다. 한 변이 짝수인 판에서는 6×6부터 닫힌 투어가 있습니다.
PictorX에서 해 보기
나이트 투어를 열고 칸을 클릭해 시작하세요. 강조된 칸은 규칙에 맞게 뛸 수 있는 칸이고, 금색 숫자는 바른스도르프의 선택이며, 판에는 여러분이 둔 수의 순서가 남습니다. ‘크기’는 판을 5×5부터 10×10까지 정하고, ‘닫힌 투어’는 ‘풀기’가 고리를 찾게 하며, ‘실행 취소’는 어떤 수든 되돌립니다. 완성된 경로는 PNG로 저장하세요.
자주 묻는 질문
나이트 투어를 처음 연구한 사람은 누구인가요?
투어는 누군가 수학적으로 연구하기 훨씬 전부터 알려져 있었습니다. 레온하르트 오일러가 1759년에 최초의 수학적 논의를 썼고, 바른스도르프는 1823년에 자신의 규칙을 내놓았습니다.
모든 판에 투어가 있나요?
5×5 이상의 정사각형 판에는 열린 투어가 있고, 그중 6×6 이상에서 한 변이 짝수인 판에는 닫힌 투어도 있습니다. 2×2, 3×3, 4×4 판에는 투어가 전혀 없습니다.
체스판에는 투어가 몇 개 있나요?
어떤 투어와 그 투어를 거꾸로 따라간 것을 따로 세면 닫힌 투어는 26,534,728,821,064개입니다. 열린 투어의 수는 약 1경 9,600조 개입니다.
PictorX가 무언가를 업로드하나요?
아니요. 판은 브라우저의 캔버스에 그려집니다. ‘저장’은 PNG를 내려받고, ‘편집’은 그 이미지를 PictorX 편집기에서 엽니다.
관련 도구
나이트 투어
체스의 나이트를 뛰게 해서 판의 모든 칸을 정확히 한 번씩 방문하세요. 바른스도르프 힌트를 보며 직접 해 보거나, ‘풀기’가 열린 투어나 닫힌 투어를 완성하는 모습을 지켜보세요. 경로는 PNG로 저장할 수 있습니다.
8퀸
체스판에 퀸 8개를 서로 공격하지 않도록 놓아 보세요. 직접 해 보고, 백트래킹 탐색이 한 단계씩 풀이를 찾는 모습을 보고, 92가지 풀이를 모두 둘러보세요.
8퀸 문제
8퀸 문제의 역사와 수학: 막스 베첼과 가우스, 12개 그룹으로 나뉘는 92가지 풀이, n퀸 문제, 그리고 백트래킹.
하노이의 탑
브라우저에서 원판 탑을 기둥 세 개 사이로 옮겨 보세요. 한 번에 하나씩, 큰 원판은 절대 작은 원판 위에 놓지 않습니다. 가장 짧은 풀이는 2ⁿ − 1번입니다.
하노이의 탑
하노이의 탑: 기둥 세 개, 한 번에 원판 하나, 큰 원판은 절대 작은 원판 위에 놓지 않기. 가장 짧은 풀이는 2ⁿ−1번입니다. 에두아르 뤼카가 1883년에 소개한 퍼즐입니다.
랭턴의 개미
브라우저에서 랭턴의 개미를 실행하세요. 대칭, 혼돈, 104걸음 고속도로를 지켜본 뒤 여러 색 규칙, 여러 마리의 개미, 육각 격자, 터마이트를 시험해 보세요.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
나이트 투어 해 보기