Skip to content

Learn

Articles and Guides

How the puzzle works, why the numbers are what they are, and where it came from — each with a board beside it.

Articles

  • The History of the Tower of HanoiÉdouard Lucas, the 1883 puzzle sold under a false name, the legend of the sixty-four golden disks, and what the puzzle went on to become.Updated
  • Why the Minimum Is 2ⁿ − 1 MovesThe full proof that 2ⁿ − 1 moves is both achievable and unbeatable, why the shortest solution is unique, and how the moves divide between the disks.Updated
  • Tower of Hanoi, Binary and Gray CodeWhich disk moves on any move, read straight off the binary digits of the move number — and the Gray code that changes exactly the same bit.Updated
  • The Iterative Tower of Hanoi SolutionSolving the puzzle with a loop and two rules, and why those rules reproduce the recursive solution move for move.Updated
  • Recursion, Explained with the Tower of HanoiBase cases, the leap of faith and the call stack, taught on the one puzzle that recursion makes easy.Updated

The algorithm

  • The Tower of Hanoi algorithmThe recursive solution traced line by line on a live board, why it is correct, the recurrence solved properly, and its complexity.
  • Tower of Hanoi in PythonRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
  • Tower of Hanoi in JavaScriptWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
  • Tower of Hanoi in JavaWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
  • Tower of Hanoi in CUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
  • Tower of Hanoi in C++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
  • Tower of Hanoi in C#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Solutions by number of disks

Every move of the optimal solution, played on a board and listed in full, with what is particular about each size.

Tools