Mathematica 9 is now available

Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

The Problem of the Knight: A Fast and Simple Algorithm
Author

Arnd Roth
Organization: Max-Planck-Institut für Medizinische Forschung
Old MathSource #

0202-127
Revision date

1999-06-30
Description

Knight Tour More than 200 years ago, Leonhard Euler posed the following problem: Given a chessboard of n times n squares, is it possible to find a path for the knight that touches every square exactly once in succession? For n >= 5, the answer is yes. Several algorithms with different time complexity solving this problem are discussed. One of them, Warnsdorff's algorithm, is implemented in Mathematica in an improved fashion. Mathematica's list processing capabilities account for the compactness and readability of the resulting code.
Subjects

*Applied Mathematics > Computer Science
*Mathematics > Discrete Mathematics > Graph Theory
Keywords

applied mathematics, knight, chess, hamiltonian path, graph, graph theory, discrete mathematics, game, improved Warnsdorff
Downloads Download Wolfram CDF Player

Download
Knight.nb (477.6 KB) - Knight Problem Mathematica notebook

Files specific to Mathematica 2.2 version:
Download
Knight.ma (112.9 KB) - Knight Problem Mathematica notebook