Return to my Puzzle pages
Go to my home page

The Tower Of Hanoi

© Copyright 1999, Jim Loy

towers of HanoiThis puzzle is famous. I see that it was invented by Edouard Lucas, in 1883, and is also called the Towers (plural) of Hanoi or the Pyramid Puzzle (with rectangles instead of disks). It consists of a pile of disks. Each disk is of a different size, so that when piled up, they can be piled with the largest disk on the bottom, the second largest above that, and so on, up to the smallest disk (see the diagram). Normally, there is a hole in the middle of each disk, so that they can be piled with the help of three vertical posts (pegs), as in the diagram.

The object of the puzzle is to move the tower, from one peg to another, moving only one disk at a time. And, you can never have any disk on top of a smaller disk. Let's say that our task is to move the tower onto the middle peg. To begin, you can move the top disk to either of the two available pegs. Then you can move the second disk (or move the first disk, if you didn't like where you put it). But, you cannot move the second disk on top of the first disk (as the second disk is larger than the first). It takes several moves, to move the entire tower.

Try it. It is fun to experiment with this puzzle. You can make disks out of wood or cardboard, or write numbers on a sheet of paper or on separate cards, or whatever. You may want to start with fewer than seven disks, as seven disks take 127 moves, which can take a while. Here is a numerical representation of the puzzle, part way through the solution.

   5   1
   6   2
   7   3   4

Click here to see an animation of the solution (takes a while to load).

The puzzle is actually not difficult, if you can figure out the way to progress, when you have two choices (besides backtracking). This difficulty pops up immediately, as you must figure out which move to start with. How do you start?

We have an odd number of disks, which we can number 1 (smallest) through 7 (largest). Through trial and error (or even reasoning), you should find that you always want an odd numbered disk on the bottom of the peg that the tower will end up on. If there were an even number of disks, then you would want an even numbered disk on the bottom of the peg that the tower would end up on. Also, you want an odd on top of an even disk, and an even on top of an odd. You don't want the formation shown below, on the left. You do want the formation shown below, on the right:

   1   2              2   1
   3   4              3   4

Here is the solution, for moving our tower to the middle peg. I am lettering the pegs, a b c. Each move is read "from-to" ("from a to b" for example):

  1. a-b
  2. a-c
  3. b-c
  4. a-b
  5. c-a
  6. c-b
  7. a-b
  8. a-c (the position that I showed numerically, above)
  9. b-c
  10. b-a
  11. c-a
  12. b-c
  13. a-b
  14. a-c
  15. b-c
  16. a-b (disk #5)
  17. c-a
  18. c-b
  19. a-b
  20. c-a
  21. b-c
  22. b-a
  23. c-a
  24. c-b
  25. a-b
  26. a-c
  27. b-c
  28. a-b
  29. c-a
  30. c-b
  31. a-b
  32. a-c (disk #6)
  33. b-c
  34. b-a
  35. c-a
  36. b-c
  37. a-b
  38. a-c
  39. b-c
  40. b-a
  41. c-a
  42. c-b
  43. a-b
  44. c-a
  45. b-c
  46. b-a
  47. c-a
  48. b-c (disk #5)
  49. a-b
  50. a-c
  51. b-c
  52. a-b
  53. c-a
  54. c-b
  55. a-b
  56. a-c
  57. b-c
  58. b-a
  59. c-a
  60. b-c
  61. a-b
  62. a-c
  63. b-c
  64. a-b (disk #7, half-way done)
  65. c-a
  66. c-b
  67. a-b
  68. c-a
  69. b-c
  70. b-a
  71. c-a
  72. c-b
  73. a-b
  74. a-c
  75. b-c
  76. a-b
  77. c-a
  78. c-b
  79. a-b
  80. c-a (disk #5)
  81. b-c
  82. b-a
  83. c-a
  84. b-c
  85. a-b
  86. a-c
  87. b-c
  88. b-a
  89. c-a
  90. c-b
  91. a-b
  92. c-a
  93. b-c
  94. b-a
  95. c-a
  96. c-b (disk #6)
  97. a-b
  98. a-c
  99. b-c
  100. a-b
  101. c-a
  102. c-b
  103. a-b
  104. a-c
  105. b-c
  106. b-a
  107. c-a
  108. b-c
  109. a-b
  110. a-c
  111. b-c
  112. a-b (disk #5)
  113. c-a
  114. c-b
  115. a-b
  116. c-a
  117. b-c
  118. b-a
  119. c-a
  120. c-b
  121. a-b
  122. a-c
  123. b-a
  124. a-b
  125. c-a
  126. c-b
  127. a-b

The solution represents what is called a Gray Code, in computer science. Several lengthy puzzles are based on Gray Codes.

Addendum:

Now that I have solved the puzzle, was that an optimal solution? I thought it was. Well, it has been shown that the optimal solution takes 2n-1 steps (where n is the number of disks). Above, n=7 and 27-1=127. So my solution was optimal.

In Mathematical Puzzles by Anthony S. Filipiak, shows this puzzle with four pegs. He calls it the Brahma Puzzle. And I suspect that he thinks you need the fourth peg. You can ignore the fourth peg and solve it as I did. The fourth peg shortens the solution. I do not know how to use the fourth peg most efficiently. He starts with eight disks. He says you can use more disks, "but always add an even number, never an odd number." Of course he is wrong there. With three pegs, adding an odd number just changes your first move.

Return to my Puzzle pages
Go to my home page