Towers of Hanoi

Start Finish

Short problem statement:

Given a game board with three pegs and a set of disks of different diameter all stacked from smallest to largest on the leftmost peg, move all of the disks to the rightmost peg following these two rules. First, only one disk may be moved at a time. Second, a larger diameter disk may never be placed on a smaller disk. Any number of disks can be used.

We first solved it with one disk, then two, and then three. I noted that solving two disks could be done by moving first moving one disk to the center peg, then moving the bottom disk to the right peg, then moving the center disk to the right peg.

The three disk problem was similar: first move the top two disks to the center peg, then move the left disk to the right peg, then move the center stack to the right peg. Of course moving a stack involves multiple moves, but we arleady know how to move two disks from one peg to another (see above)... we just move them to the center using the right peg as the temporary spot. Likewise moving them from the center to the right can be done as above using the left peg as the temporary spot. (Try it!)

We actually wrote down all the moves for the four disk problem also, but this time we used the previous steps to guide us: first move the top three from LEFT to CENTER using RIGHT, then move the last disk from LEFT to the empty RIGHT peg, then move the stack of three from CENTER to RIGHT using LEFT.

In each case, we solve the problem of moving a stack of disks by moving a smaller stack first. Generally speaking, to move N disks from LEFT to RIGHT using CENTER we first move N-1 from LEFT to CENTER using RIGHT, move the Nth disk, then move N-1 disks from CENTER to RIGHT using LEFT.

The C++ program does just that. Each time the MOVE routine is called upon to move a stack, it first moves a smaller stack, then the last disk, and then the smaller stack again. Except, of course, for a stack of one. In this case it just does it.

The rest of the implementation can safely be called hand-waving.

The ancient problem called the Towers of Hanoi is not considered an easy problem to solve. The solution was actually quite simple and not an exceptionally hard or unsolvable problem.