The Tower of Hanoi is a puzzle, for which the goal is to move all disks from peg A to C, with the following rules for each move:
- Any pegs can be used to temporarily store a disk
- Disks can only be taken from the top of a stack
- Only a smaller disk can be place on top of a larger disk
An interactive version of the game can be found at mathisfun.com.
A simple algorithm to find the optimal moves for the game is to use recursion. The idea is continuous reduction of the problem size by one.
For example, let’s say we have N disks, moving from A to C. This can be reduced to moving N-1 disks to B, then after that we just have to move one bottom disk from A to C. Last step is to move N-1 disk from B to C, which is also solved recursively.
solve() method below implements the recursive algorithm. The following are the parameters:
n: the number of disks to move
from: the source peg number
to: the destination peg number
temp: the temporary peg
For example, the following
main() method solves the puzzle of 4 disks, moving from peg 1 to peg 3, using peg 2 as temporary storage.