Welcome to the Towers of Hanoi Lab!

Just to let you know that Dynamic Programming provides a very elegant solution to this famous game. It goes like this:

Let,

Sol[n,x,y] := solution to a game that requires moving n items from peg x to peg y

and

not(x,y) := the peg that is neither x nor y, observing at by definition

Sol[1,x,y] := Move the object from peg x to peg y.

Then clearly,

Sol[n,x,y] = Sol[n-1,x,not(x,y)] , Sol [1,x,y] , Sol[n-1,not(x,y),y].

In any case, the purpose of this page is to show you an animated dynamic programming algorithm in action for a problem with 4 objects.

You'll need a browser supporting animated GIF files, eg. Netscape 3.

Back to Live OR

Contribued by Moshe Sniedovich