Knight’s Tour Problem

A knight's tour

A knight's tour

One of the homework problems we had in graph theory class asks the question: given a Knight piece and an 8×8 chessboard, can you start the Knight off on one square, move into every other square once and exactly once, and land back on the square that you started with? This is a really annoying problem because it’s easy to understand and sucks you in for hours. I only got half credit on it by trying to fill a 4×4 part of the board as much as I could and copying the same moves 4 times.  Apparently, a Knight’s tour doesn’t exist for a 4×4 as Professor So mentions some theorems about this problem. If you’re interested in more, check out Schwenk’s theorem.

Coincidentally, I was randomly practicing programming problems in Topcoder and I found that the Knight’s Tour makes an appearance as the 2nd problem in division 2, SRM 447. The problem has you implement an algorithm, namely Warnsdorff’s algorithm, which is a heuristic algorithm that makes the Knight piece walk the board, and if you start with a fresh board with the Knight in a corner, you can actually discover a Knight’s tour. BUT, the thing is, it doesn’t give you the elusive Hamiltonian circuit but rather a Hamiltonian path ie. the starting and ending points that you find with this algorithm are different. Still, it’s pretty awesome for a 500 point problem.

The cool thing about that algorithm is that although the Hamiltonian path problem is NP-hard, it supposedly is able to find Hamiltonian paths in many graphs in linear time. I’ve attached my Java program if you just want to test it out. Don’t worry about having seen this tour and having the problem being spoiled; apparently, there are billions of possible tours. Also, I have not found the Hamiltonian circuit yet, so good job if you managed to find it but don’t tell me 🙂