♞ 기사의 여행이란?
기사의 여행(Knight's Tour)은 체스판에서 나이트(기사)가 모든 칸을 정확히 한 번씩만 방문하는 경로를 찾는 수학 퍼즐입니다. 나이트는 체스에서 L자 모양으로만 이동할 수 있어, 이 제약 조건 하에서 모든 칸을 방문하는 것은 쉽지 않습니다.
나이트의 L자 이동
나이트는 가로 2칸 + 세로 1칸, 또는 세로 2칸 + 가로 1칸으로 이동합니다. 파란색 칸이 현재 위치에서 이동 가능한 최대 8개의 칸입니다.
시작점으로 돌아오면 '닫힌 여행(Closed Tour)', 그렇지 않으면 '열린 여행(Open Tour)'이라 부릅니다. 이 문제는 해밀턴 경로 문제의 특수한 경우입니다.
📜 역사와 오일러의 방법
기사의 여행 문제는 수 세기에 걸쳐 수학자들의 관심을 끌어왔습니다. 특히 레온하르트 오일러는 1759년에 이 문제를 최초로 수학적으로 분석한 논문을 발표했습니다.
💡 Warnsdorff의 규칙 (AI 힌트 알고리즘)
- 현재 위치에서 이동 가능한 모든 칸을 찾는다
- 각 칸에서 다시 이동 가능한 칸의 수를 계산한다
- 이동 가능한 칸이 가장 적은 칸을 선택한다
- 이 방법은 막다른 골목에 빠질 확률을 줄여준다
오일러가 해결한 8×8 체스판에서 기사의 여행을 완성하는 방법은 무려 19,591,828,170,979,904가지나 됩니다!