Home > Mathematica, Mathematics > Euler and Hamilton Knight Adventure

## 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 built-in 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.