Below, you’ll find the answers to last week’s puzzles, which were proposed to me by my good friend, chess grandmaster Robert Hess. If you would like to take a crack at the Week 7 challenge and haven’t had a chance yet, just click here.
1. There are 26,534,728,821,064 possible tours on an 8×8 board. (That number counts the same path in which the knight travels in opposite directions as two separate tours.)
It’s necessary to know that a knight’s movement looks like an L (one move will take it two squares vertically and one square horizontally, or one square vertically and two squares horizontally). That means that the piece moves from light squares to dark squares or dark squares to light squares. It will also help to determine how a knight is constrained on an 8×8 board by seeing how many possible moves it has from each square.
Then, unless you’re especially gifted at imagining a knight’s movement around a chessboard (I’m still working on this myself), get a piece of paper and a pencil, make an 8×8 grid, and give it a shot.
Here’s a trick if you’re having trouble: the knight always jumps to a square from which it has the fewest possible onward moves.
The so-called knight’s tour problem is one that has vexed chess players — and mathematicians — for centuries. The earliest known reference dates back to a poet in the ninth century! The great mathematician Euler most prominently raised it again in the 18th century. In mathematics, the knight’s tour is a special instance of something known as the Hamiltonian cycle in graph theory.
2. You cannot find a closed knight’s tour on a 5×5 board.
3. In fact, you can’t find a knight’s tour on any rectangular n x m board (n,m>5) with an odd number of tiles. One easy way to think about the problem: we already know that a knight moves from black tiles to white tiles and white tiles to black tiles. For it to land on every tile once, then, the number of white tiles needs to equal the number of black tiles. But on a rectangular board with an odd number of tiles, there are more black tiles than white ones or more white tiles than black ones. (You can see this immediately, because all the corners are the same color.)