Euler and Hamilton Knight Adventure
I once again have been motivated to explore a classic problem from the a post on Endeavour blog of John D Cook.
The Knight’s tour has a number of generalizations and solutions.
I tried to implement the Warnsdorff algorithm in Mathematica, and quickly found the problem of tied minimally accessible paths leading to dead ends. After frustration at resolving this, I turned to visualization of the solution of Knight’s tour available within Mathematica.
Using the Combinatorica
package there is a function KnightsTourGraph[m,n]
that produces a graph of arbitrary size with vertices the chess board cells and edges between two vertices defined by the accessibility by one knight move. For the typical 8 x 8 board:
Finding a tour can be done using HamiltonianCycle[]
. This produces a list of vertices of a Hamiltonian cycle in the graph. The following highlights Mathematica’s solution.
I visualized the tour on a chessboard:
Notes:
Combinatorica
has compatibility issues with the Mathematica builtin graph functions. This leads to some frustrating complexities that I have not worked through. Ant Colony Optimization algorithms seem like exciting ways to solve network and graph theory problems.

May 12, 2011 at 1:44 amEuler and Hamilton Knight Adventure « Unknown Blogger Mathematica  Solve Math & Science Problems  Solveable.com

May 13, 2012 at 7:39 pmKnights tour revisited « Unknown Blogger Mathematica