Towers of Hanoi

The last problem that I would like to talk about in this tutorial is the Towers of Hanoi game, which again is an example of a wonderful naturally recursive problem.

The Problem

You have 3 shelves (A, B, C) and N disks. Each disk is a different size and stacked such that a smaller disk is placed on top of a larger disk.

You are not allowed to place a bigger disk on top of a smaller disk. The target of the game is to move all disks from one shelf to another, using the third one as an intermediate storage location.

At any point you are not allowed to violate the rule of the game. Thus, a smaller disk is always on top of a bigger disk.

Below is an example of 3 disks of different sizes. I have made them all in a different color. The starting and goal configurations are shown in this figure.