기사의 여행

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

체스판 위에서의 경로의 예

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

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

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

기사의 여행 문제는 그래프 이론에서 NP-완전인 해밀턴 경로 문제의 특별한 경우이다.

외부 링크

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