Knight's Tour
Knight's tour(기사의 여행)은 체스보드에서 나이트가 체스보드의 모든 칸을 방문하는 경로이다. 체스보드의 크기와 나이트가 여행을 시작하는 칸에 따라서 knight's tour가 존재하지 않을 수 도 있다. 만약 knight's tour가 존재하고, 나이트가 tour의 마지막 위치에서 시작 위치로 이동이 가능하다면, 이를 closed knight's tour라고 부르며, 그렇지 않을 때 open knight's tour라고 부른다.
아래 두 문장은 knight's tour에 대한 잘 알려진 사실이다.
\(n \times n\) 체스보드에서 \(n\)이 홀수라면 \(n \ge 5\)일때 open knight's tour가 반드시 존재한다.
\(n\)이 짝수라면, \(n \ge 6\)일때 closed knight's tour가 존재한다.
이 외에도 몇 가지 사실이 밝혀져, knight's tour가 존재하는지 검사할 수 있게 되었다. [1][2]
Knight's tour는 그래프로 표현될 수 있다. 체스보드의 각 칸을 vertex로, 나이트가 이동할 수 있는 칸 끼리 edge로 이어주면 된다.
그러면, Knight's tour를 찾는 문제는 그래프에서 Hamiltonian path를 찾는 문제와 같다. 또, Closed knight's tour는 Hamiltonian cycle과 같아진다.
Knight's tour에서 체스보드의 크기를 \(n \times m\)과 같이 직사각형 형태로 정할 수 있다. 하지만, 이번 글에서는 \(n \times \ n\)과 같이 정사각형 체스보드에 대해서만 다룰 예정이다.
Warnsdorff's Rule
Knight's tour를 찾는 문제는 backtracking을 연습하기 좋은 문제이고, backtracking을 이용한 풀이가 가장 널리 알려져 있다. 하지만, backtracking은 \(O\left(4^n \right)\)의 시간복잡도를 가지므로, \(n\)이 커지면 knight's tour를 찾는 데에 필요한 연산이 너무 커져, 해를 찾기가 힘들다.
Warnsdorff's rule은 이런 시간복잡도 문제를 효과적으로 해결해 줄 수 있다. Backtracking의 방식은 그대로 두면서, 탐색할 vertex의 순서를 정하여 그래프에서 Hamiltonian path를 빠르게 찾을 확률을 높혀준다. 하지만, knight's tour가 존재하지 않는 상황에서 단순히 backtracking에 warnsdorff's rule 만 적용할 경우, backtracking과 같은 성능을 보여준다. 때문에, Warnsdorff's rule을 이용할 때, Warnsdorff's rule에 따라 다음 vertex를 정하는 방식으로 knight's tour를 찾고, 만약 모든 체스보드의 칸을 방문하지 못했지만, tour의 다음 vertex로 선택할 수 있는 것이 없다면, 탐색을 종료하고 knight's tour가 존재하지 않는 것으로 판단한다. 만약, 사실과 다른 결과를 얻었다면, Warnsdorff's rule이 실패했다고 한다.
Warnsdorff's rule은 탐색에서 아래와 같이 다음에 방문할 vertex 선택하는 규칙이다.
현재 위치가 \(u\)라면, 다음에 방문할 vertex는
\(v \in V\) such that \(\left\{ u,v\right\} \in E\), \(\mathrm{deg}(v) \le \mathrm{min}_{t}\left\{\mathrm{deg}(t)\right\}\), \(\left\{ u,t\right\} \in E\)
이다.
(\(E\)는 set of edge, \(V\)는 set of vertex. deg의 경우 해당 vertex에서 이동할 수 있는 vertex의 수로, 이미 방문한 vertex는 세지 않는다.)
엄연히, Warnsdorff's rule은 heuristic으로, 이를 이용한 탐색이 실패할 수 있다. 오히려, 실패할 확률이 생각보다 높다. \(8 \times 8\) 크기의 체스보드에서도 심심찮게 실패하는 모습을 관찰할 수 있다. 이는 Warnsdorff's rule에서 deg가 같은 vertex가 여러 개이기 때문이다.
아래는 Warnsdorff's rule을 개선하기 위한 두 규칙이다.
Arnd Roth's Proposition
deg가 같은 vertex가 2개 이상일 경우, 체스보드 중앙에서 가장 멀리 떨어진 vertex를 정하는 방법이다. (유클리드 거리를 이용한다.)
*Arnd Roth's Proposition이 언급된 논문이나 인터넷 게시글은 볼 수 있었으나 원문이 어디서 왔는지는 확실치 않다.
Markku Vähäaho's Proposition
deg가 같은 vertex가 2개 이상일 경우, 시작 vertex에서 가장 멀리 떨어진 vertex를 선택한다. (유클리드 거리를 이용한다.)
두 규칙 모두 일반 Warnsdorff's rule을 이용했을 때 보다 실패할 확률이 감소한다. 평범한 Warnsdorff's rule이 vertex가 100정도만 되어도 쉽게 실패 하는데 반해 vertex가 200 정도에서도 knight's tour를 잘 찾는 모습을 보여준다.
BOJ 2025: 나이트투어는 이런 휴리스틱을 시험해 보기에 좋은 문제이다. 간단한 테스트 케이스를 만들어 직접 실험을 진행해도 좋다.
BOJ의 해당 문제를 기준으로, Arnd Roth's proposition을 적용한 코드는 252/256, Markku Vähäaho's proposition을 적용한 코드는 242/256, 일반 Warnsdorff's rule의 경우 최대 127/256, 최소 44/256의 성능을 보였다.
Warnsdorff's rule을 개선하기 위해서 두 proposition을 제외하고도 다른 방법을 이용할 수 있다.
필자는 9가지의 서로 다른 vertex 선택 방법을 이용하여 256/256의 결과를 얻을 수 있었다.
[1] Parberry I (1997) An efficient algorithm for the Knight’s tour problem. Discrete Applied Mathematics 73:251–260. doi: 10.1016/s0166-218x(96)00010-8
[2] Lin S-S, Wei C-L (2005) Optimal algorithms for constructing Knight’s tours on arbitrary n x m chessboard. Discrete Applied Mathematics 146:219–232. doi: 10.1016/j.dam.2004.11.002
'Well Known Problem' 카테고리의 다른 글
| Bitonic Tour 바이토닉 투어 (0) | 2023.05.25 |
|---|