An instructive solution to the Tower of Hanoi problem
Coding a solution to the classical Tower of Hanoi problem is a standard exercise for students learning a new programming language. Here we offer a solution written in Haskell.
Its main pedagogcal value is illustrating how a non-standard ordering can be the basis for a concise solution.
The initial configuration is the list [[1..n], [], []] where each sublist represents a rod, each integer represents the diameter of a disk on the rod, and the position of each integer within the sublist represents the position of the corresponding disk (left is top). Only the case of three rods is considered.
-
Solution to the problem with n disks on the first rod
hanoi n
-
Print nicely the soluton to the console
mapM_ print $ hanoi n
-
Number of steps in the optimal solution.
length $ hanoi n
Mathematically, it is known that (length $ hanoi n) == 2^n.