Algorithms for finding knight’s tours on Aztec diamonds
Samantha Davies, Chenxiao Xue, Carl Yerger · Involve a Journal of Mathematics · 2017
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 2n where triangular regions of side length n -1 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-andconquer 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 n = 22 apart from n = 17, 21.The second is a path-conversion algorithm that finds a solution for all n ≤ 100.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.