Towers of Hanoi

I’ve had a solution to the Towers of Hanoi problem, written in Common Lisp, on my GitHub for a while now.

I would like to explain the Towers of Hanoi problem here. Unfortunately, it’s difficult to explain if you don’t use visual illustrations, and WordPress isn’t great for visual illustrations. Consequently, I recommend the Wikipedia page. But, to put the solution into a nutshell, the basic idea behind the algorithm is this:

If you have N rings on the source tower, then move the top N – 1 rings from the source tower to the spare tower. Then move the bottom Nth ring from the source tower to the destination tower in one move. Then move the N – 1 rings on the spare tower to the destination tower.

To move the N – 1 rings, you solve a subinstance of the original problem of size N – 1. So, it is natural to apply recursion.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s