Tower Of Hanoi With Arbitrary Initial Configuration

# How to solve the Tower of Hanoi Puzzle with arbitrary initial and final configurations?

In the basic tower of hanoi puzzle all the disks are initially on one peg (e.g. on the first one).
Example:

____
1                                            1
2                                            2
3                                            3
.                                            .
.                                            .
N                                            N
----- ----- -----                ----- ----- -----
A     B     C                    A     B     C
Initial state                      Final state


But what if the disks are placed on various pegs in the initial configuration, e.g:

____
1
2
3                                     3
1      2     4                               4
----- ----- -----                ----- ----- -----
A     B     C                    A     B     C
Initial state                      Final state


An inductive, non-recursive solution of the the Tower Of Hanoi Puzzle with arbitrary initial configurations was described by
Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle":
http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html

http://en.wikipedia.org/wiki/Mathematical_induction

## Visualization of Tower of Hanoi Puzzle with arbitrary initial configurations

http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/HanoiApplet.html

## Another good description how you can solve a tower of hanoi puzzle with arbitrary start

positions (or if you forget your moves after you started)
http://www.geocities.com/jaapsch/puzzles/hanoi.htm

## Related

### God's algorithm

http://en.wikipedia.org/wiki/God's_algorithm

### States and Transition (interesting related description about state and transition (Tower of Hanoi example)

Among the most pervasive notions in computing is that of "state". We define the state of
a computation as a set of information sufficient to determine the future possible
behaviors. In other words, the state tells us how the system can change. It also can tell us
something about what has happened in the past, if we know it to have been started in a
particular initial state. It doesn't usually tell exactly what has happened, but rather
conveys some abstraction of what has happened.
http://www.cs.hmc.edu/~keller/cs60book/%206%20States%20and%20Transitions.pdf

### Tower of Hanoi (BitHacking)

http://puremass.com/yp/tower2.html

## About Tower of Hanoi : History

There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it. The Tower of Hanoi is a problem often used to teach beginning programming, in particular, as an example of a simple recursive algorithm.

If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 600 billion years (operation taking place is $\frac2}^{64{60 \times 60 \times 24 \times 365.2425}$) . [1] (In context, the universe is currently about 13.7 billion years old.)
Source: http://wapedia.mobi/en/Tower_of_Hanoi#2.

keywords: generalized Towers of Hanoi problem, arbitrary initial configuration

### Related materials

Intuitive Hanoi - The Tower of Hanoi Revisted with Objects
http://openbookproject.net//py4fun/tower/tower.html

Tower of Hanoi (Applet Simulation)
http://www.cut-the-knot.org/recurrence/hanoi.shtml

Iterative solutions to Hanoi:
http://www.cut-the-knot.org/recurrence/hanoi.shtml
=> New fast iterative computer algorithms for the Tower of Hanoi puzzle
http://hanoitower.mkolar.org/algo.html

How to solve the tower of hanoi puzzle
http://wipos.p.lodz.pl/zylla/games/hanoi-ex.html

All kind of mathematic and computer science puzzles
http://www.cut-the-knot.org/index.shtml

page revision: 10, last edited: 12 Apr 2008 08:50