기사의 여행

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
체스판 위에서 기사의 여행 경로
5x5 기사의 여행을 나타낸 애니메이션

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

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

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

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

바깥 고리[편집]