Towers of Noah

The Towers of Noah

This is a free-interpretation of the famous Towers of Hanoi problem. The problem is treated here as a DP problem and is used to illustrate how DP works. The DP formulation is treated in the 620-261 lecture notes.

For the benefit of visitors from other planets who have never heard about this problem, here is the story:

there are a number of objects on a peg, arrange in increasing order by size. The objective is to move the objects to another peg - one item at a time - utilising a third peg for temporary storage.

The difficulty stems from the requirement that at no time should a larger item be placed on top of a smaller item.

The optimal solution requires (2^n) - 1 moves where n is the number of objects.

Try it!