nPeg Hanoi

The towers of Hanoi with a variable number of pegs works just like the 4Peg version, just a little bit more abstract:
What we need is a list of pegs of size n containing the "from"-peg, the "to"-peg and lots of spare pegs. The split point k is calculated and the top-most k disks are moved to a spare peg using the n-peg method. The spare peg then gets deleted from that list which is now used to move the remaining disks to the n'th peg using n-1-peg hanoi method. Finally, the k disks on the spare peg are moved to the n'th peg using the nPeg method again.

In the recursive calls n-1 will eventually turn out to be 3, and this can be easily done on a non-abstract level. This also neccessary for correct termination of the program.

Now to the code.
What we definitely need is a properly working look-up table. In 4Peg hanoi this table is created by referring to numbers of moves of 3Peg hanoi, which can be computed directly. Therefore, in nPeg hanoi we need to refer to the (n-1)Peg table, which might take a while to be computed itself, if we choose a significantly big n.
To minimize the amount of work, the whole table gets precomputed and passed to actual function as a parameter. It starts with the 3Peg table, then computes 4Peg, 5Peg and so on. It actually doesn't terminate. It's an infinite list of tables, where each table has an infinite size... Haskell can deal with that, promise.

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

The first line could actually be substituted into the second one, which would make it a bit shorter and a bit more unreadable. Comparing this to the 4Peg table will tell you that it's still quite similar, as described above.

Just using that table, we can already determine the required moves for n pegs and m disks:

nMoves disks pegs  = fst ((tab!!(pegs-3))!!disks)

As I mentioned before, we need a list of pegs. It's just not possible to program this with static parameters for each peg, or we'll end up in having something like "nPeg hanoi where n < 100" with at least a hundred lines of code. The list should be of the following form:

[<from>, <to>, <spare peg being currently used>] ++ [<list of n-3 spare pegs>]

moves disks pegs = mov (map (map snd) tab) disks ([1, pegs] ++ take (pegs-2) (iterate (+1) 2))

This line creates such a list and passes it to mov, the actual function doing all the moves but not really all the work. "Moves" is the one you should call when testing or playing around with it.

What's left is the actual hanoi function:

mov tbl 0 any = []
mov tbl n [f, t, v]  = mov tbl (n-1) [f, v, t] ++ [(f,t)] ++ mov tbl (n-1) [v, t, f]
mov tbl n (f:t:v:xs) = mov tbl ((tbl!!p)!!n) ([f, v, t]++xs) ++ mov tbl (n-((tbl!!p)!!n)) ([f, t]++xs) ++ mov tbl ((tbl!!p)!!n) ([v, t, f]++xs)
  where p = length xs

So much of hanoi, but it's still not done yet. Although this nPeg algorithm produces a correct result, I strongly doubt it's the optimal solution. When computing the look-up table, we go from 4Peg to 5Peg to 6Peg and so on, without ever coming back, or without ever thinking of the bottom-most disks again after finding k. If we have a large number of disks and a sufficiently big-enough number of pegs 'n', then performing (n-1)Peg hanoi and using the n'th peg as a spare peg for moving the bottom-most disks might already be a better solution. All in all computing an optimal solution would run at a much higher complexity. Hope I'll be able to find some time and a good approach to actually put this into code.