Flexistentialism Welcome Guest | Login or Register

Two tiny updates:

On the “About”:/about.shtml page, there is now a tiny bit of additional info, namely, the total number of posts, total number of comments, and overall comments per entry (currently 1.9), in addition to the month-to-month data. You don’t care, but I do! It is like a running log of how interesting I am.

Second, there is a little “Towers of Hanoi solver”:/hanoi.php running. Thanks to “Amit Singh’s Hanoimania”:http://www.kernelthread.com/hanoi/ I have been tweaking some PHP code to solve the classic puzzle. His code is great, and deserves all the credit, however, I’ve made a few tweaks to improve the interface, and add additional information such as the number of moves required to solve the puzzle.

For anyone who isn’t familiar, the Towers of Hanoi is a classic puzzle consisting of three posts with a tower of disks placed on one of the posts. The disks are stacked according to size, with the smallest disk on top, descending to the largest disk on the bottom. To solve the puzzle you must move the entire tower from the starting post to a different post. You can only move one disk at a time, and no disk may be placed upon a disk smaller than itself, IE, disks can only move to empty posts, or on top of larger disks. It turns out that the puzzle has a very simple algorithmic solution, which Amit implements in 108 different programming languages, a truly heroic effort. I’m playing with the PHP one for the heck of it.

There is a little legend associated with the puzzle, whereupon a monastery deep under the mountains contains a version of this puzzle with diamond posts and golden disks. There are monks there who are solving the puzzle. The puzzle began with 64 disks, and they started solving the puzzle, one movement per second, at the beginning of the universe. When they finish the puzzle, the universe will end. Solving a 5 disk puzzle is fairly easy, and once you figure out the system, the movements come quickly. However, with a little calculation you can see that the number of moves needed to solve the puzzle goes up very quickly. It turns out that it will take the monks somewhere around 580 billion years to finish the puzzle with only 64 disks.

Bonus points to anyone who can figure out the equation to calculate the optimal number of moves required to solve the puzzle with a given number of disks (N). Hint, check out the solution for “1 disk”:/hanoi.php?1, “2 disks”:/hanoi.php?2, “3 disks”:/hanoi.php?3, and “4 disks”:/hanoi.php?4. Seeing a pattern yet? Try to predict the number of moves required for “5 disks”:/hanoi.php?5, and see if you can formulate an equation based on that pattern.

Feed on comments to this Post