기사의 여행

체스판 위에서의 경로의 예

5x5 기사의 여행을 나타낸 애니메이션

기사의 여행은 체스보드의 나이트에 대한 수학적인 알고리즘 문제의 일종이다. 체스 피스를 움직이는 규칙에 따라 나이트를 모든 칸으로 정확히 한 번씩 갈 수 있도록 하는 방법을 찾는 문제이다. 이 문제의 해법은 수없이 많다. 기사가 마지막 위치에 가서 첫 번째 위치로 공격을 할 수 있는 상태가 되면 여행이 닫혀 있다고 하고, 그렇지 않으면 여행이 열려 있다고 한다.

레온하르트 오일러를 비롯한 많은 수학자들이 이 문제의 다양한 변형에 대하여 연구하였다. 예를 들어 다음과 같은 다양한 변형 문제가 있다.

• 체스판의 크기가 다른 문제
• 두 명의 선수가 경기를 하는 경우를 다룬 문제
• 기사가 움직이는 방법을 조금 다르게 한 문제

이론

표준 8×8 체스판에서 기사의 여행에서 가능한 모든 경로를 보여주는 나이트 그래프. 각 노드의 수는 해당 위치에서의 이동 가능한 경로 수를 나타낸다.

기사의 여행 문제는 그래프 이론에서 NP-완전인 해밀턴 경로 문제의 특별한 경우이다. 닫힌 기사의 여행 문제 역시 해밀턴 순환 문제의 예시이다. 일반적인 다른 해밀턴 경로 문제들과 달리 선형 시간 안에 해결 가능하다.

역사

기사의 여행 문제에 대한 알려진 가장 오래된 언급은 9세기까지 거슬러간다. 루드라타의 산스크리트 시학 작품인 카비아랑카라에서(5.15), 체스판의 절반 크기 보드에서 기사의 여행 패턴이 정교한 시적 장식(citra-alaṅkāra)으로 제시되었으며, 이는 투라가파다반다 또는 '말의 발걸음 배열'이라 불린다.

이 구절은 각각 8음절로 이루어진 네 개의 행으로 구성되어 있으며, 왼쪽에서 오른쪽으로 읽을 수도 있고, 기사 이동 경로를 따라 읽을 수도 있다. 산스크리트어에 사용되는 인도 계열 문자 체계는 음절 기반이므로, 각 음절이 체스판의 한 칸을 나타낸다고 볼 수 있다.

루드라타의 예시는 다음과 같다:

से	ना	ली	ली	ली	ना	ना	ली
ली	ना	ना	ना	ना	ली	ली	ली
न	ली	ना	ली	ले	ना	ली	ना
ली	ली	ली	ना	ना	ना	ना	ली

음역:

se	nā	lī	lī	lī	nā	nā	lī
lī	nā	nā	nā	nā	lī	lī	lī
na	lī	nā	lī	le	nā	lī	nā
lī	lī	lī	nā	nā	nā	nā	lī

예를 들어, 첫 번째 줄은 왼쪽에서 오른쪽으로 읽을 수도 있고 첫 번째 칸에서 시작하여 (2,3), (1,5), (2,7), (4,8), (3,6) (4,4), (3,2) 순서로 이동하여 읽을 수도 있다.

해의 존재성

사방으로 대칭인 닫힌 기사의 여행 경로

앨런 슈벵크는 m ≤ n인 어떤 m×n 보드에서든 아래 세 가지 조건 중 하나 이상 만족하지 않는 이상 닫힌 기사의 여행이 가능함을 보였다:

1. m과 n이 모두 홀수
2. m = 1, 2, 또는 4
3. m = 3 그리고 n = 4, 6, or 8

여행의 개수

8×8 보드에서는 정확히 26,534,728,821,064개의 방향성이 있는 닫힌 여행(즉, 동일한 경로를 반대 방향으로 가는 여행은 별도로 계산되며, 회전과 대칭도 별도로 계산됨)이 있다. 방향성이 없는 닫힌 투어는 이 수의 정확히 절반인데, 모든 여행에 대해 반대방향의 다른 여행이 존재하기 때문이다. 6×6 보드에서는 방향성이 없는 닫힌 여행이 9,862개 존재한다.

n	n×n 보드에서 방향이 있는 여행 (닫힌, 열린 여행 모두 포함)의 개수 (OEIS의 수열 A165134)
1	1
2	0
3	0
4	0
5	1,728
6	6,637,920
7	165,575,218,320
8	19,591,828,170,979,904

컴퓨터로 기사의 여행 찾기

컴퓨터로 주어진 보드에서 기사의 여행 경로를 찾는 방법에는 여러가지가 있다. 방법들 중 몇몇은 알고리즘인 반면, 몇몇은 휴리스틱이다.

같이 보기

• 여덟 퀸 문제

외부 링크

• 머리를 내밀어 봅시다: 기사의 여행 - 기사의 여행 문제를 푸는 방법 중의 하나인 Warnsdorff의 규칙을 이용한 C언어 소스 코드
• 기사의 여행 퍼즐 - 기사의 여행 문제를 풀어 랭킹 경쟁을 하는 사이트