Week 5: Towers of Hanoi

With our first assignment looming on the horizon (and haunting me in my dreams), I've resolved to dedicate this week's post to the Towers of Hanoi.

Though this puzzle bears resemblance to some child's toy one would see in the purgatory we know as the doctor's waiting room, it finds its origins in ancient India.  Indeed, the original story tells the tale of monks who endeavour to solve this puzzle by moving its three discs from the first peg to the last.  Our assignment is a modified version in which Anne Hoi - whose name sounds like Hanoi, curiously enough - wants to move cheeses from one stool to another.

The recursion insight at the heart of this problem, for three stools at least, was that all movements of multiple cheeses could be simplified into moving n - 1 cheeses first, then the bottom cheese, then n - 1 cheeses again.  The four stools variation in our assignment is however a slightly more daunting challenge; the availability of an additional stool may mean that the optimal move sequence cannot always be broken down into the same steps, or even the same number of steps.  I suspect that the crux of the issue is finding the optimal split of cheeses to move, possibly using recursion.