나이트 투어
나이트 투어(knight’s tour) 는 체스판에서 나이트를 체스의 규칙에 맞게 움직이면서 모든 칸을 정확히 한 번 방문하는 경로이다. 시작했던 칸으로 돌아올 수 있는 경우를 닫힌 나이트 투어라고 하고, 그렇지 않은 경우를 열린 나이트 투어라고 한다. 예를 들어 그림 15에 체스판의 열린 나이트 투어가 나와 있다.
- 그림 15. 체스판의 열린 나이트 투어
체스판의 각 칸이 노드가 되고, 나이트가 체스의 규칙에 따라 두 칸 사이를 이동할 수 있는 경우를 간선으로 연결한 그래프를 생각하자. 나이트 투어는 이 그래프의 해밀턴 경로에 대응된다. 나이트 투어를 찾는 자연스러운 방법은 퇴각 검색을 이용하는 것이다. 규칙에 맞게 움직이는 방법이 매우 많기 때문에, 투어를 빠르게 찾는 방향으로 나이트를 움직이는 휴리스틱(heuristic)을 이용해야 탐색을 효율적으로 수행할 수 있게 된다.
바른스도르프 규칙(Warnsdorf’s rule) 은 나이트 투어를 찾기 위한 간단하고 효율적인 휴리스틱이다. 이 규칙을 이용하면 판의 크기가 크더라도 효율적으로 경로를 찾을 수 있다. 아이디어는 나이트를 움직일 수 있는 여러 칸이 있을 때, 다음으로 움직일 수 있는 경우가 가장 적은 곳으로 움직이는 것이다. 그림 16을 예로 들면, 다음으로 갈 수 있는 칸은 로 표기된 다섯 칸이다. 이 경우 바른스도르프 규칙에 따르면 칸으로 이동해야 하는데, 이 칸에서 다음으로 갈 수 있는 경우의 수가 한 가지뿐이기 때문이다. 다른 칸으로 이동하면 경우의 수가 세 가지가 된다.
- 그림 16. 바른스도르프 규칙을 이용하여 나이트 투어 찾기
