나이트의 여행
말 하나로 체스판을 다 채우기
체스판의 나이트 말은 앞으로 두 칸 가고 옆으로 한 칸 꺾어 움직입니다. 가로세로 5칸짜리 바둑판을 종이에 그리고 구석에 말을 놓아 보세요.
말이 지나간 칸에 1, 2, 3… 번호를 적으며 25칸을 모두 밟아 보세요. 마지막 서너 칸을 남겨 두고 길이 꽉 막혀 버리는 까닭은 무엇일까요?
이야기
그런데 이 문제는 체스판보다 시에서 먼저 나타났습니다. 9세기 인도의 시학 책 『카비아랑카라』에 나이트가 움직이는 차례대로 글자를 읽으면 시가 되는 말놀이가 실려 있습니다. 수학 문제이기 전에 시인들의 놀이였던 것입니다.
수학으로 다룬 것은 1759년 오일러입니다. 그는 여행을 여러 가지로 만들어 보이고, 판을 반씩 나눠 이어 붙이는 요령까지 적어 두었습니다.
손으로 찾는 요령은 1823년 바른스도르프가 냈습니다. 「갈 수 있는 곳이 가장 적은 칸부터 가라」는 것입니다.
까닭은 구석이 나중에 갇히기 때문입니다. 판 가운데 칸에서는 여덟 곳으로 갈 수 있지만 구석에서는 두 곳뿐입니다. 그런 칸을 뒤로 미루면 들어갈 길이 먼저 막혀 버립니다.
🚩 다만 5×5 판에서는 제자리로 돌아오는 여행이 아예 없습니다. 나이트는 한 걸음마다 칸의 색이 바뀌는데, 25칸은 홀수라 출발한 색으로 돌아올 수가 없기 때문입니다.
「모든 곳을 한 번씩 지나는 길」 문제입니다. 이것이 어려운 문제(NP)의 대표 얼굴 중 하나입니다.
회로 기판의 배선 순서, 창고 로봇의 순찰 경로, 유전자 조각을 이어 붙이는 일이 같은 종류의 문제입니다.
계단 넷 — 같은 사실을 네 깊이로
작은 판에서 해 본다
작은 3×3 판에서 나이트를 움직여 보세요. 가운데 칸에는 영원히 들어갈 수 없거나 한 번 들어가면 갇힙니다.
하지만 판을 조금만 넓혀 5×5나 8×8로 만들면 모든 칸을 한 번씩 밟는 멋진 여행이 가능해집니다. 갈 곳이 적은 가장자리 구석 칸부터 먼저 채워 나가는 요령을 손으로 익혀 보세요.
나이트가 뛰어 보세요
3×3 은 가운데 칸에 영영 못 갑니다.
규칙을 찾아 큰 판으로
나이트가 갈 수 있는 다음 칸 후보 중에서 「그 칸에서 앞으로 갈 수 있는 길의 개수」가 가장 적은 칸을 먼저 고르면 길이 막히지 않습니다.
이것을 바른스도르프 규칙(Warnsdorff's rule)이라 부릅니다. 구석에 외따로 떨어진 칸을 나중에 남겨 두면 도달할 방법이 사라지므로, 선택지가 적은 불리한 칸을 먼저 방문하는 현명한 전략입니다.
색으로 따져 보세요
그래서 칸 수가 홀수면 닫힌 여행이 불가능합니다.
해밀턴 경로
체스판의 칸들을 꼭짓점으로 두고 나이트가 이동할 수 있는 관계를 변으로 이으면 하나의 거대한 그래프가 됩니다.
체스판의 모든 칸을 정확히 한 번씩만 거치는 경로는 그래프 이론에서 해밀턴 경로(Hamiltonian path)를 찾는 문제와 완전히 같습니다. 특히 출발점으로 돌아오는 닫힌 여행은 체스판 색깔의 흑백 교대 성질과 밀접하게 얽혀 있습니다.
여행의 가짓수
1995년에야 정확히 세어졌습니다.
그래프 탐색
일반적인 그래프에서 해밀턴 경로의 존재 여부를 판정하는 것은 대표적인 NP-완전(NP-complete) 문제입니다.
오일러 경로가 차수의 홀짝성으로 즉시 판정되는 것과 대조적입니다. 나이트의 여행은 그래프 탐색의 백트래킹(Backtracking) 기법과 휴리스틱 탐색 알고리즘의 성능을 검증하는 고전적인 벤치마크로 널리 연구됩니다.
워스도프의 규칙
왜 되는지는 아직 완전히 설명되지 않았습니다.
풀어 보기
작은 체스판과 나이트의 이동. 나이트의 이동 규칙과 체스판의 성질에 대해 답하시오.
(1) 3×3 체스판의 정가운데 칸에서 나이트가 이동할 수 있는 칸의 개수를 구하시오.
(2) 체스판의 나이트는 한 번 움직일 때마다 항상 발을 딛는 칸의 색(흑/백)이 바뀐다. 5×5 체스판(총 25칸)에서 닫힌 나이트의 여행(출발점으로 되돌아오는 여행)이 불가능한 까닭을 흑백 칸 수로 설명하시오.
(3) 3×3 체스판에서 모든 9개 칸을 한 번씩만 방문하는 열린 나이트의 여행이 존재하는지 판정하시오.
(2) 는 홀수 개의 칸을 밟고 제자리로 돌아오려면 색깔이 어떻게 바뀌어야 하는지 따져 보세요.
답과 풀이 보기
(1) 0 개입니다.
나이트는 한 방향으로 2 칸, 꺾어서 1 칸을 갑니다. 판의 한가운데에서 그렇게 뛰면 언제나 판 밖입니다.
가운데 칸은 어디로도 못 가고, 아무도 그리로 못 옵니다.
(2) 나이트는 한 번 뛸 때마다 반드시 색이 바뀝니다. 그러니 닫힌 여행에서는 흑과 백을 번갈아 밟고 제자리로 와야 하고, 그러려면 흑과 백의 수가 똑같아야 합니다.
그런데 는 홀수라 13 대 12 로 하나가 남습니다. 그래서 제자리로 돌아올 수 없습니다.
(3) 존재하지 않습니다.
(1) 에서 본 대로 가운데 칸은 완전히 외톨이입니다. 여행은 아홉 칸을 모두 밟아야 하는데, 그 칸에는 들어갈 수도 나올 수도 없습니다.
⭐ 가운데를 빼면 이야기가 달라집니다 — 바깥 여덟 칸은 하나로 이어진 고리를 이루어 여행이 됩니다.
1759 년 오일러가 판의 여행을 처음 체계적으로 다뤘습니다. 지금은 그 답이 1경 3천조 가지가 넘는다는 것까지 세어 놓았습니다.
그런데 은 단 한 가지도 없습니다. 작다고 쉬운 것이 아닙니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「모든 점을 한 번씩 지나기」는 어려운 문제의 대표입니다.
- 해밀턴 경로 — 이런 경로가 있는지 판정하는 것은 일반적으로 아주 어렵습니다
- 외판원 문제와 사촌입니다
- 작은 판부터 — 5×5 판에서 해 보세요. 6×6보다 오히려 쉽습니다
이어지는 장
영감을 받은 곳
9세기 인도 시인 루드라타(Rudrata)의 『카비얄랑카라(Kavyalankara)』에 체스판 나이트 행마로 읊는 시가 기록되어 있고, 레온하르트 오일러(Leonhard Euler)가 1759년 베를린 학술원에 낸 논문 「체스판 위 체스 말의 행마에 관한 새로운 방법의 연구」에서 체계화되었습니다.