Main Page » Miscellaneous »

Fun With Towers of Hanoi

Created:

Always use secure-HTTP / Unsecure HTTP / Permanent Link

This article is completely pointless, and has no real goal or conclusion.

One of my preferred ways of killing time at restaurants and such entails solving Towers of Hanoi in my head. A Tower of Hanoi (if you cannot pronounce this, just go with "Tower of Brahma") is a mathematical game in which you have a number of rods, and a number of disks of different size which can slide onto any rod, and at the beginning of the game, they're all arranged in ascending order of size one of the rods to make a conical shape. Describing a Tower of Hanoi puzzle takes the form of T(x,y) where x = the number of disks and y = the number of pegs. The standard example seems to be T(4,3).

The Rules

  • The goal is to move all the disks from one peg to a specific other peg, i.e. if the pegs are all in a row, and they start on the peg on the left, the goal might be to get them to the far right.
  • You can only move one disk at a time.
  • No disk may be placed on top of a smaller disk.

Corollary:

  • For any T(x,y) where x is greater than 1, a Tower of Hanoi puzzle is only solvable if y is greater than 2.

Some Interesting Things I've Noticed

Solving T(x,3) towers in my head, I noticed some patterns. For the purposes of this discussion, the rods shall be labelled A (the one you start on), B (the middle one), and C (the one you want to put them all on), and the disks are numbered in increasing order of size (1 = smallest, infinity = largest).

  • Quickest solution to T(3,3): disk 1 to rod C, disk 2 to B, disk 1 to B (on top of 2 — assume this sort of thing hereinafter), disk 3 to C, disk 1 to A, 2 to C, 1 to C. Seven moves.
  • With about six disks, it starts to become fairly easy to lose mental track. Hey, I get to kill more time that way!
  • I quickly hit on what Wikipedia refers to as the "recursive method" of solving Towers of Hanoi: recursively subdivide it Tower of Hanois with one fewer disks, where you're trying to put them onto the other non-starting rod. Um ... example: for T(6,3) ...
    • Solve for T(5,3) where you're trying to get to rod B instead of C, put disk 6 on rod C, then solve for T(5,3) where you're starting on rod B instead of A.
    • Solve for T(4,3) where you're trying to get to rod C, then put disk 5 on rod B, then solve for T(4,3) where you're trying to get to B instead of C and starting on C.
    • ... and so forth.
  • To solve T(x,3) in the least possible moves, if you have an odd number of disks, start by putting disk 1 on rod C, and if you have an even, start by putting disk 1 on B.
  • I noticed a pattern for the number of moves based on the number of disks:
    • Name: Function of Hanoi (for T(x,3))
    • For x = 0, F(x) = 0
    • For x > 0 (or any value of x for which F(a lesser value of x) is known), F(x) = (2 * F(x-1)) + 1
    • For x < 0, which is silly (or any value of x for which F(a greater value of x) is known), F(x) = (F(x+1) - 1)/2
  • I began to write down the solutions:
    • F(1) = 1
    • F(2) = 3
    • F(3) = 7
    • F(4) = 15
    • F(5) = 31
    • F(6) = 63
  • At which point I saw a much more fun pattern, forcing me to revise the function:
    • For any value of x, F(x) = 2x-1.
  • The puzzle was invented by mathematician Édouard Lucas in 1883, based on a legend about a Vietnamese temple which was in the process of solving a puzzle for T(64,3); the priests of the temple had been working on it according to an ancient prophecy, which said that once the last move was made, the world would end.
  • The solution to T(64,3) would optimally take 18446744073709551615 moves. At a rate of one move for second, this would take about 585 billion years. (For the record, the sun is expected to last only 5 billion more years, and Earth isn't expected to survive.)
  • Adding more pegs makes the process more complicated. T(1,4) still takes 1 move and T(2,4) still takes 3 moves. Solving T(3,4) takes 5 moves; T(4,4) takes 9 moves. I think T(5,4) takes 13 moves, and T(6,4) probably takes 17. I'm not sure how accurate this is or if I'm doing something wrong, but that's point where I gave up.

9 Comments (auto-closed) (rss feed)

Joseph Staleknight

Interesting mathematical deductions.

I bet this game's popular in Gensokyo, right?

The Watcher

Something tells me Ran and Yukari could solve something like this as a fun noonday activity.

eidrag

Adding more pegs will lead to more variable, which is "where the hell I should put the next ring?" In the original one it is either that one or the another pegs.

John Evans

/ Modified by Dizzy H. Slightly Voided:

T(a,b) for a<b = 2a-1.

John Evans

...sorry, I missed the note about special characters. >_<

T(a,b) for a<b = 2a-1.

Young Demon Lord

Something tells me Ran and Yukari could solve something like this as a fun noonday activity.

Something tells me that in the Gensokyo version of this game, just for added fun, Yukari would have an actual tower prepared, with floors that get smaller as you go up, and she'd move floors of it around as instructed by the player (or she'd just do it herself as she played).

But hey, it'd be an awesome game! :-D

Off-topic: If there's one thing I love about Webkit, it's re-sizable text fields. I can give myself editing room that I'm comfortable with. Muffin, if you're about to ask me what my preferred text field size is, I do not have preferred dimensions prepared. I just resize it until it's "big enough".

Wait, does playing with text field sizes make me like the Internet version of Yukari? I'm manipulating borders, after all. :-D

North4

You hurt my brain sometimes.

Also, I remember a puzzle like this in the first Mass Effect, but wasn't aware it had a name.

John Evans

Game developers often go for classic puzzles like this when making minigames and such things. I seem to recall a Towers of Hanoi in KotOR 2...unless I'm misremembering...

Twilightdusk

It was either in KotOR or KotOR 2, it was guarding something on Koribin.