Solution:

1. Move the top N-1 disks of the stack aside, on the spare peg.
2. Move disk N in position on the other peg.
3. Move the stack of N-1 disks on top of disk N.

This method works because this reduces the puzzle of N disks to a puzzle of only N-1 disks. That in turn is reduced to a puzzle of N-2 disks, and so on until the puzzle is reduced to moving a stack containing only 1 disk, which is easy. This algorithm has exactly 2^N-1 moves, because from the steps above it is easily seen that Length(N)=2Length(N-1)+1, and Length(1)=1, and the result then follows by induction. This solution is also minimal, in other words there is no shorter way to solve it, because every solution for N disks must reach the intermediate position with the top N-1 disks on the spare peg.

The recursive algorithm works very well, but in practice there are several rules of thumb which can guide you:

• Every other move is a move of the smallest disk, i.e. the small disk is moved on move number 1, 3, 5, ... ,2^N-1.
• The smallest disk visits each peg in turn, and is never moved back to the peg it came from on its previous move. In fact this is true of all disks (except for the largest), but it is more obvious with the smallest one since it is moved so often.
• On a move not involving the small disk (i.e. moves 2, 4, 6, ...) there is only one possible move choice.
• If the disks are numbered, then an even disk is never placed on top of an even disk, and an odd one never on top of another odd one.
• If there is an even number of disks then the first move takes the small disk to the second peg, with an odd number of disks the first move is to the third peg. This can be seen as an extension of the odd/even rule above; the bases of the pegs are also considered odd or even in such a way that the start and end positions follow the odd/even rule, and then the first move can be deduced.

There are 3^N possible positions, and 2^N positions are encountered while solving the puzzle directly using the methods above. All the other 3^N-2^N positions break the odd/even rules by having two disks of the same parity on top of each other (or the largest disk on the middle peg). The odd/even rule always rules out one of the three available moves, so that you can only go forwards to the end or back to the beginning.

If you stop in the middle of solving and forget what your last move was, then you may find yourself reversing previous moves and ending up back at the beginning. The rules of thumb also do not help you when you encounter one of the 3^N-2^N positions that do not lie on the direct route between the start and the end. In these cases the correct move can be deduced as follows:

1. You want to move the stack of N disks to the third peg. You therefore want to put disk N on the third peg first.
2. If the disk is in position, then the aim is to put all the smaller disks on top of it. If not, then the aim is to put all the smaller disks on the other peg.
3. Repeat the above for this smaller stack of disks.

This is best illustrated by example:

Here we want to move disk 4 from peg B to peg C. This means that we need all the smaller disks to be on peg A, so we must move disk 3 from peg C to peg A first. For this we need all disks smaller than 3 to be on peg B. Disk 2 is already on peg B, but disk 1 is not so this has to be moved to peg B. The correct move is therefore disk 1 from A to B.
Similarly if we want to move back to start, to move disk 4 from B to A means that disk 3 and smaller must be on peg C. Disk 3 is already on C, so we must put disk 2 on C next. Disk 1 does not obstruct this, so the correct move is disk 2 from B to C.
If we wanted all the disks on peg B instead, then the correct move would be move disk 1 from A to C. Note that this move does break the odd/even rule (disk 1 moves on top of disk 3), but that is only because the position itself already breaks that rule (disk 2 lies on disk 4).

An interesting pattern emerges if you map out all possible positions in a graph, with lines connecting two positions that differ by a single move. The graph will resemble of Sierpinski's gasket; the more disks, the more closely its graph approximates the gasket's fractal triangular shape. The solution is the path along the edge of the triangle, from one corner to the other.