4Peg Hanoi

Solving the original puzzle with 64 disks and 3 pegs might take a while, as there is a total of 18,446,744,073,709,551,615 moves, which is 2⁶⁴-1. Even if you gave the monks lots of RedBull so that they can do one move a second, it still takes 584,942,417,355 years, which is (2⁶⁴-1) div (365*24*60*60). Adding a fourth peg, we can reduce the number of moves down to 18433, which might roughly take 5 hours.

To move all disks from the first peg to the last peg, the tower is split up. The top-most k disks are moved to a spare peg using 4 pegs, the remaining disks are moved to the final peg using 3 pegs and then the top-most k disks are moved to the final peg using 4 pegs. So how are the top-most disks moved using 4 pegs? They are just being split up again applying the same principle. So we have an overall amount of moves of 2 times the number of moves to move k disks using 4 peg plus moving n-k disks using 3 peg. It's up to us to find the best split-point k for n disks. The most common technique for that is to build a look-up table for optimal k's, otherwise we would end up in computing the same thing for several times.

The following look-up table was written by Tony Field:

ts = (0,0) : (1,0) : [minimum[(2*fst(ts!!k)+2^(d-k)-1,k) | k <-[1..d-1]] | d<-[2..]]

This is a quite complex, but very neat double list comprehension. The inner list comprehension is

[(2*fst(ts!!k)+2^(d-k)-1,k) | k <-[1..d-1]

[minimum [...] | d<-[2..]]

It just picks the minimum element of the first list comprehension and defines d. The function ts contains some initial values because it accesses itself in the inner list comprehension. Explaining this code is somehow easier than writing it. There obviously is a lots of work in that line. The function builds an infinite list, but as just single elements are accessed, the programm will always terminate. The tuples being produced contain the number of moves using the optimal k and the k itself. The number of disks can be obtained by the index of that tuple. The first ten elements of ts are the following

[(0,0),(1,0),(3,1),(5,1),(9,1),(13,2),(17,3),(25,3),(33,4),(41,5)]

To get the number of moves out of it, we can access the table like this

nMoves n  = fst (ts!!n)

nMoves 4 = 9
nMoves 64 = 18433
nMoves 1718 = 2⁶⁴+1
This means 1718 disks take about the same number of moves as 64 disks in the original Hanoi puzzle with 3 pegs.

The actual Hanoi function looks like this

mov tbl 0 f t v v' = []
mov tbl n f t v 0  = mov tbl (n-1) f v t 0 ++ [(f,t)] ++ mov tbl (n-1) v t f 0
mov tbl n f t v v' = mov tbl (tbl!!n) f v' t v ++ mov tbl (n-(tbl!!n)) f t v 0 ++ mov tbl (tbl!!n) v' t f v

The function takes in the lookup-table "tbl", the number "n" of disks being moved and 4 pegs (from, to, via, via').
The base case is that 0 disks are being moved, in this case an empty list is returned.
The second case is the 3Peg algorithm. The unused 4^th peg is set to 0 and that's how the function recognizes that 3Peg and not 4Peg should be performed.
The last line is the actual 4Peg algorithm and all it does is, "move k disks from f to v', move n-k disks from f to t, move k disks from v' to t".

The function can easily be called passing it the look-up table (it only needs the second element of each tuple!) and a couple of integer arguments. A function which calls the hanoi function would look like this

moves n = mov (map snd ts) n 1 4 2 3

Putting it all together we get code with 4 significant lines and 2 additional ones for calling the functions

ts = (0,0) : (1,0) : [minimum[(2*fst(ts!!k)+2^(d-k)-1,k) | k <-[1..d-1]] | d<-[2..]]

nMoves n  = fst (ts!!n)

moves n = mov (map snd ts) n 1 4 2 3
mov tbl 0 f t v v' = []
mov tbl n f t v 0  = mov tbl (n-1) f v t 0 ++ [(f,t)] ++ mov tbl (n-1) v t f 0
mov tbl n f t v v' = mov tbl (tbl!!n) f v' t v ++ mov tbl (n-(tbl!!n)) f t v 0 ++ mov tbl (tbl!!n) v' t f v