Vol. 10, No. 5, 2017

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

Volume 12, 1 issue

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
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
This article is available for purchase or by subscription. See below.
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.

PDF Access Denied

Warning: We have not been able to recognize your IP address 54.198.86.28 as that of a subscriber to this journal. Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form.

Or, visit our subscription page for instructions on purchasing a subscription. You may also contact us at contact@msp.org or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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