## The Tower Of Hanoi

This 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```

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.