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
2 comments:
That is just stunning.
And now... for the rest of the story.
In Jan 1975 my lab partner and I created the first version of that physical 8x8x8 knights tour model... using 8 layers of wire mesh painted with chess board black and white squares... then strung it with orange yarn.
The class was "Chess and Mathematics" for the "J-term". I had to choose a partner, and a project from a long list of choices. The had noticed that the math department had a PDP-11 with a teletype interface, so I asked if he would let me write a program to do Knight's tours on an 8x8 chess board. In a couple days I had it running and printing out a lot of closed solutions.
Mr. Larson thought we solved it too fast, so he upped the challenge to an 8x8x8 stacked set of boards. A couple days later, after my first 4 debugging runs, the 5th run produced a Closed 8x8x8 solution (Coming to understand the Euler logic, I started with a good guess). We studied a bunch of various starting points to determine the best places to start. The answer was "near the corners"... giving the Euler algorithm the fewest possible initial moves.
He then wanted to show off the closed knight's tour solution... so he gave us the last 4 days to create the full size 8 layer chess board (chicken wire and yarn) model... "For his coffee table".
Loren Larson's recreation all out of wood really is amazing! He obviously had a lot of patience!!
I really did like him as a teacher... he clearly got his joy from the challenges of math, and shared that joy with his students.
Post a Comment