July 21, 2010

Knight Moves in 3D

The crazily crinkled structure, framed within a cube, is an impressive sight. Suspended above the stairs on the sixth floor of the mathematics building at St. Olaf College in Northfield, Minn., it is also the solution to a mathematical puzzle.

Painstakingly crafted from wood by retired St. Olaf mathematician Loren Larson, the sculpture embodies a path that a knight could take on a three-dimensional chessboard to complete a tour of the 512 (83) positions on the grid, visiting each position just once before returning to the starting point.

According to the rules of chess, a knight makes an L-shaped move that shifts its position by a single square in one direction and two squares in a perpendicular direction. Indeed, the knight is the only chess piece that covers an asymmetrical pattern of squares.

Finding a sequence of 64 knight moves that visit each square of a standard chessboard—a knight's tour—is a classic problem with a long history. Leonhard Euler (1707-1783) described a method for constructing such a tour in 1759, and mathematicians have investigated many variants of the problem since (see, for example, "A Magic Knight's Tour"), including knight's tours in three dimensions.

In Larson's sculpted solution, the sticks representing the 512 moves gradually change in color from pale yellow to deep red, with the final move linking the lightest yellow piece to the darkest red piece.

The color changes give insights into the algorithm used to find the route. If you start at or near a face of the 8 x 8 x 8 cube, you first visit other positions that have relatively few outlets, such as corners or edges. In effect, you knock off the hardest cases first. The result is that the tangle of moves seems to get darker and darker as you move toward the cube's center.

Photos by I. Peterson

1 comment:

paulsc said...

That is just stunning.