J.R. Hay

Looking to sharpen my poor programing skills, I decided to take on an afternoon side project. Scouring through the various forums I came across a math problem which I thought was and interesting and within the reach of my skills – the Knights Tour. The premise is simple, take a Knight at any of the four corners of the chess board and move such that you land on every space once without repetition. For my weapon of choice I chose MATLAB, primarily because it the one which I have the most comfort and the one I will be working with during my summer internship and in future research.

The solution I landed on works by taking all the potential moves and then looking at their potential moves, second order potential moves if you will. Potential moves being moves that abide by the rules of the Knight, abide by the boundary conditions (don’t exit the board), and have not already been made.

The knight moves moves in the combinatorics of [+/-2,+/-1]. So if we set up a grid in which the checkerboard exists on a 8*8 coordinate system (0-7*0-7 because I like to start indexing at 0.) then we can compute these possible moves by adding the permutations to the current position. Next we can cull based off of the remaining two rules, boundary conditions, and moves already made. Now we have a list of possible moves… but which one do we choose?

We run the whole thing again creating branches for each possible move. We note how many possible moves each branch has and choose the branch with the lowest possible moves, this is our best move. [Note if there are multiple best moves I randomly chose from them, this happens frequently during the first few moves and decreases as the board fills.]

This entire solution is based in graph theory, where all of our points are connected in a web like graph. Our goal is to hit every point on this graph once and only once a path known as a Eulerian Trail.

Here is my finished circuit, the orange squares are previous moves and the red square is the knight, since I only look toward the second order of possible moves it does not always make a Eulerian Trail.

All in all it was a fun project to sink an afternoon into and not to hard if you would like to go after it yourself.