Vol. 10, No. 5, 2017

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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 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.

Keywords
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

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