Tower of Hanoi

Show Summary Details

Quick Reference

A logical puzzle, frequently studied in cognitive psychology and used as a test of problem-solving ability, consisting of three pegs, on one of which are placed a number of discs of varying diameter, the largest at the bottom and the smallest at the top (see illustration). The problem is to move the tower of disks over to one of the other pegs in the smallest number of moves, moving one disc at a time and using the third peg as a temporary way station as required, and never placing a larger disc on top of a smaller one. The puzzle is of ancient (possibly Indian) origin but was rediscovered by the French mathematician Edouard Lucas (1842–91) and marketed as a toy in 1883. Lucas proved that, for any number n of discs, the minimum number of moves is given by the formula 2n − 1. Hence 3 discs can be transferred in 7 moves, 4 discs in 15 moves, 5 discs in 31 moves, and so on. See also General Problem Solver. [So called because of its supposed resemblance to a certain type of Vietnamese building, Lucas's toy having been described as a simplified version of the Tower of Brahma, which was said to contain 64 gold discs, and which would therefore require a minimum of 264 − 1 (more than 18 billion billion) moves to solve]

Tower of Hanoi

Subjects: Mathematics — Psychology.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.