|
|||||
 |
|
|
|
|
|
Algorithms for
finding knight's tours on Aztec diamonds
Samantha Davies, Chenxiao Xue and Carl R. Yerger
Vol. 10 (2017), No. 5, 721–734
|
Abstract |
|
A knight’s tour is a sequence of knight’s moves such that each square on the board is visited exactly once. An Aztec diamond is a square board of size where triangular regions of side length have been removed from all four corners. We show that the existence of knight’s tours on Aztec diamonds cannot be proved inductively via smaller Aztec diamonds, and explain why a divide-and-conquer approach is also not promising. We then describe two algorithms that aim to efficiently find knight’s tours on Aztec diamonds. The first is based on random walks, a straightforward but limited technique that yielded tours on Aztec diamonds for all apart from . The second is a path-conversion algorithm that finds a solution for all . We then apply the path-conversion algorithm to random graphs to test the robustness of our algorithm. Online supplements provide source code, output and more details about these algorithms. |
Keywords
knight's tour, Aztec diamond, Hamiltonian, algorithm
|
Mathematical Subject Classification 2010
Primary: 05C45
Secondary: 05C57, 97A20
|
Supplementary material |
Milestones
Received: 28 July 2015
Revised: 8 July 2016
Accepted: 21 August 2016
Published: 14 May 2017
Communicated by Ronald Gould
|
Authors |
| Samantha Davies | |
| Padelfor Hall University of Washington W. Stevens Way NE Seattle, WA 98105 United States |
|
| Chenxiao Xue | |
| Department of Mathematics and
Computer Science Davidson College Box 7129 Davidson, NC 28035 United States |
|
| Carl R. Yerger | |
| Department of Mathematics and
Computer Science Davidson College Box 7059 Davidson, NC 28035 United States |
|
|
