Vol. 10, No. 5, 2017

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
Author index
To appear
Other MSP journals
Algorithms for finding knight's tours on Aztec diamonds

Samantha Davies, Chenxiao Xue and Carl R. Yerger

Vol. 10 (2017), No. 5, 721–734

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-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 n22 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.

knight's tour, Aztec diamond, Hamiltonian, algorithm
Mathematical Subject Classification 2010
Primary: 05C45
Secondary: 05C57, 97A20
Supplementary material

Java code implementing the algorithms

Example knight's tours for selected board sizes

Received: 28 July 2015
Revised: 8 July 2016
Accepted: 21 August 2016
Published: 14 May 2017

Communicated by Ronald Gould
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