in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #12

Algorithm 8.3: Design and implement a recursive algorithm to solve the Towers of Hanoi problem for one or more disks.

I actually never written code for that problem. I want to finally do this ā€“ I don’t care how long this takes. Let’s do it.

The representation is important. I first thought about using lists however most often I see an other one ā€“ a simpler one. We only need to know the largest number for each pole. This is a good tip.

See how it works if we have one disk: We just move the disk from our starting pole to our end pole and we’re done. The great thing about the smallest disk is that it can move everywhere. We don’t have to check anything.

Let’s add an other disk. To move disk 2 from :a to :c we have to clean :a first. Preferably to :b, so that we can move :c without problems.

However, we aren’t ready yet. Disk one needs to move from :b to :c.

Looks fine. Now, hopefully this works for 3 disks. And it worked:

Here’s the incredible short code:

The biggest revelation was that it only matters were the largest disk is. Somehow a super simple problem but I had problems wrapping my head around it. Maybe it was because I had problems understanding it at a kid and still think that I can’t understand it properly. Strange but simple.

So, to solve the problem I have to take the smaller disk, move it on spare, move my larger disk to end, and move the smaller disk from spare to end. That’s it. Thanks to recursion it works for all n. Magic.

Write a Comment

Comment