The Knights Tour

Posted by

It is possible for a knight in the game of chess to move about the board, using only that piece’s legal moves and land on every square of the board.

Obviously, the board is cleared of all the other chess pieces first. I used to do some computer programming back in college and that was one of the tasks we were set to do. The basic design brief was as I have just described, and within that we were left to design a program to complete the task.

I have since used the same question when I have had to interview people for programming-based roles, I just like the question as it’s a good way of ascertaining how a person approaches a problem. Some chose to overanalyse at the beginning try and plot out the valid route, some chose to code a solution that runs a route till the number of moves are exhausted, then exit. Others to record all moves as they happened, but roll back and try a different path when a route was exhausted but still incomplete.

This is actually the best solution, at any one time a knight can have up to eight possible moves. Some of these will be eliminated as it will take the knight outside the limits of the chess board, you also eliminate moves that will position the knight on a previously visited square, this gives you a valid subset of possible moves for each jump, and when exhausted, you can eliminate that route and roll back to the previous instance where there was more than one possible move, and try a different path. The theory there is that eventually, by the process of elimination the knight will find a path that generates a complete tour of the board landing on all 64 squares.

Unless you forcefully interrupt the program, the knight will keep jumping until it succeeds. The same is true of us in our businesses, it may take us many iterations, and we may have to go back and try different paths and routes, but as long as we don’t give up, we will ultimately succeed. You may well find as your path evolves that you move far away from where you originally intended to go, but that the trick we all need to learn. Our plans are never set in stone, they are fluid, they roll like the waves of an ocean and no two waves are exactly alike, they’ll push us left and right and back and forth. But eventually, as long as we keep pushing through, they will take us were we want to go.

Eventually the knight will land on all the squares on the board.