The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The disks are in a neat stack in ascending order of size on one rod, the smallest at the top, thus making conical shape. The towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1)Only one disk can be moved at a time.
2)Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3)No disk may be placed on top of a smaller disk.
The puzzle was invented by the French mathematician Édouard Lucas in 1883.
A simple solution for the toy puzzle is to 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 in the fewest number of moves
The puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2(power n) − 1, where n is the number of disks.
Source: Tower of Hanoi