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.
About these ads
Categories: Mathematica, Mathematics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 36 other followers

%d bloggers like this: