Tower of Hanoi

Overview

The Tower of Hanoi is a puzzle consisting of moving a series of discs of various sizes among three pegs. The puzzle starts with all the discs stacked in ascending order on one peg in a conical tower and the object of the puzzle is to reconstruct the tower onto another peg. The rules to the puzzle restrict how discs can be moved from one peg to another. Only one disc is allowed to be moved at a time, only the top most disc can be moved from a stack, and larger discs cannot be stacked onto smaller discs. The most efficient means to solve the puzzle (the fewest number of moves required) follows the simple function 2^n - 1, where n is the number of discs in the puzzle. For example, a Tower of Hanoi puzzle played with three discs can be solved in seven moves and a five disc puzzle can be solved in 31 moves.

History

The Tower of Hanoi puzzle was developed by French mathematician Édouard Lucas in 1883. The Tower of Hanoi, also called the Tower of Brahma and the End of the World Puzzle, is based on a legend involving an esoteric Buddhist monastery in Vietnam where generations of priests toil to move 64 golden discs between three posts in the center of a prayer hall. It is said that when the priests finally complete the puzzle it will usher in the end of the world. Using the function above, it can be calculated, however, that their task would require 2 to the 64th minus 1, or 18,446,744,073,709,551,615 moves. To underscore the impossibility of their task, if the priests make one move per second it would require them more than 585 billion years to finish. The legend and the puzzle have long been used in mathematics courses to illustrate exponential complexity.

Use in Video Games

Though developed in the 19th century, the Tower of Hanoi puzzle has maintained a degree of popularity in computer science. Because of its simple rule set, the Tower of Hanoi is taught to illustrate the core concept of recursive functions, a fundamental part of computer science.

Because of its ubiquity in computer programming, the Tower of Hanoi puzzle has popped up in a number of video games, including a couple of Bioware titles: Star Wars: Knights of the Old Republic, during the Naga Sadow's Tomb on Korriban; and in Mass Effect, on the planet Noveria. Bioware even pokes fun of their predilection for the puzzle in Dragon Age: Origins; in the town of Haven, the location of the Gauntlet (a series of puzzles similar to, but not including, the Tower of Hanoi) a tombstone can be found with the inscription "T.O. Hanoi. Unloved, unmourned."

In Professor Layton and the Diabolical Box the Tower of Hanoi puzzle is played with a stack of pancakes.