Knight’s tour

Posted June 18th, 2009 by William Willing

Categories: Fun

An item in Professor Stewart’s Cabinet of Mathematical Curiosities reminded me of a puzzle I once amused myself with during a boring physics class. I wanted to create a puzzle for the school paper where you have a 4×4 grid filled with letters and you have to use the knight’s move to visit all squares in the right order so you get a sixteen-letter word.

After I picked the word, I tried to fill all squares, but soon I suspected that what I wanted wasn’t possible; I couldn’t find a way to reach all sixteen squares using a knight’s move (one square horizontal or vertical and one diagonal) without passing any square twice. Now I had a new puzzle: prove that this is impossible.

Unfortunately, I don’t have the proof I wrote back then anymore. Still, I remember some of the key parts of it and it isn’t that hard to reconstruct. I suggest you have a go at it; it’s quite a nice puzzle.

Ian Stewart asks: what is the longest path possible on a 4×4 grid? The problem I have with that question is not so much finding the answer, but knowing when to stop looking. Obviously, when you find a path that visits fifteen squares, you know that must be the longest (since we already know that sixteen is impossible). However, if you find a path that’s shorter than that, how can you be sure whether you found the longest or not? Of course, you can write a computer program that uses brute force to calculate all paths and then shows you the longest it found, but that feels like cheating.

1 comment on “Knight’s tour”

  1. Says:……

RSS feed for comments on this post.

Leave a comment

CAPTCHA Image Audio Version
Reload Image

Bad Behavior has blocked 10 access attempts in the last 7 days.