## How to Solve

The puzzle can be played with any number of disks, although many toy versions have around seven to nine of them. The game seems impossible to many novices, yet is solvable with a simple algorithm. The number of moves required to solve a Tower of Hanoi puzzle is 2n -1, where n is the number of disks.

I have discussed some common methods to solve 'towers of hanoi' puzzle game. Though complex methods are available, for the sake of simply solving them, these methods are enough.

Iterative solution

The following solution is a simple solution for the toy puzzle. Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle using the fewest number of moves to do so.

It should perhaps be noted that this can be rewritten as a strikingly elegant set of rules:

Simpler statement of iterative solution

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:

• make the legal move between pegs A and B
• make the legal move between pegs A and C
• make the legal move between pegs B and C
• repeat until complete
For an odd number of disks:

• make the legal move between pegs A and C
• make the legal move between pegs A and B
• make the legal move between pegs B and C
• repeat until complete
In each case, a total of 2n-1 moves are made.

Equivalent Iterative Solution

Another way to generate the unique optimal iterative solution, is to number the disks 1 through n, largest to smallest. If n is odd, the first move is from the Start to the Finish peg, and if n is even the first move is from the Start to the Using peg.

Now, add the constraint that no odd disk may be placed directly on an odd disk, and no even disk may be placed directly on an even disk. With this extra constraint, and the obvious rule of never undoing your last move, there is only one move at every turn. The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.

Recursive solution

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. The following procedure demonstrates this approach.

• label the pegs A, B, C - these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

1. move n-1 discs from A to B. This leaves disc n alone on peg A
2. move disc n from A to C
3. move n-1 discs from B to C so they sit on disc n

The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n-1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial. This approach can be given a rigorous mathematical formalism with the theory of dynamic programming, and is often used as an example of recursion when teaching programming.

Non-recursive solution

The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs f, t, r, f, t, r, etc. for odd height of the tower and traverses the pegs f, r, t, f, r, t, etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm.
In alternate moves:

• move the smallest disk to the peg it has not recently come from.
• move another disk legally (there will be one possibility only)

For the very first move, the smallest disk goes to peg t if h is odd and to peg r if h is even.
Also observe that:

• Disks whose ordinals have even parity move in the same sense as the smallest disk.
• Disks whose ordinals have odd parity move in opposite sense.
• If h is even, the remaining third peg during successive moves is t, r, f, t, r, f, etc.
• If h is odd, the remaining third peg during successive moves is r, t, f, r, t, f, etc.

With this knowledge, a set of disks in the middle of an optimal solution can be recovered with no more state information than the positions of each disk:

• Call the moves detailed above a disk's 'natural' move.
• Examine the smallest top disk that is not disk 0, and note what its only (legal) move would be: (if there is no such disc, then we are either at the first or last move).
• If that move is the disk's 'natural' move, then the disc has not been moved since the last disc 0 move, and that move should be taken.
• If that move is not the disk's 'natural' move, then move disk 0.