The Knight’s Tour

I recently went for a job interview for a Java Programmer position. It seemed to go well and I was given a programming test to complete based around The Knight’s Tour. After the better part of a week (minus full-time work hours) this is what I came up with.


The Knight’s Tour is a chess-based problem. Picking a starting point on a square grid, a chess knight must move around the board in the usual manner (2 horizontal moves, 1 vertical move or vice-versa) visiting each grid square only once. If the knight manages to do this, it is called a ‘tour’. An closed tour is when you visit each space and land back on the space you started on, whereas an open tour simply involves visiting every space. The task I was given was to write a Java program which takes in a grid size, then calculates and returns the total number of open knight’s tours possible.

At first, I attempted a brute force approach; randomly select a move, starting again if the knight runs out of moves. This failed to actually produce a full path; so backtracking was implemented, allowing the knight to reverse when no moves are available and not all squares have been visited. Another technique used to ensure paths were found was to move the knight to locations from which the least number of consequent moves could be made. (i.e. move to whichever square provides the least options)

In order to learn the principles behind solving the knight’s tour, my first program gave a visual representation of solving the knight’s tour without recording or tallying total paths. However, the programming test specified that a method return the total number of paths for the grid specified in a console program. The basic logic of the program would go as follows:

Of course, given the number of possibilities that the problem produces (for an 8×8 grid, this surpasses millions) this is still theoretical. Hopefully I’ll be able to update this as I make some progress.

Advertisement