Euler and Hamilton Knight Adventure
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.
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:
Combinatoricahas 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.