|
|
|
|
|
|
 |
 |
|
The Problem of the Knight: A Fast and Simple Algorithm
|
|
|
|
|
|
| Organization: | Max-Planck-Institut für Medizinische Forschung |
|
|
|
|
|
|
0202-127
|
|
|
|
|
|
1999-06-30
|
|
|
|
|
|
 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, knight, chess, hamiltonian path, graph, graph theory, discrete mathematics, game, improved Warnsdorff
|
|
|
 |
|
|
| 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 |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
