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

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

Revision date


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.

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

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

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

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