Here's my attempt:

#!/usr/bin/perl
use strict;

my $pegs  = shift;
my $disks = shift;

my @pegs = (0, 'A' .. 'Z')[1 .. $pegs];
my %pegs = map { $_ => [] } @pegs;
$pegs{A} = [ 1 .. $disks ];

move($disks, @pegs);

sub move {
    my ($num, $from, $to, @rest) = @_;

    return unless $num;

    if ($num == 1) {
        my $d = shift @{ $pegs{$from} };
        print "$d: $from -> $to\n";
        unshift @{ $pegs{$to} }, $d;
        return;
    }

    $num--;

    for my $i (0 .. $#rest) {
        move( int(($num + $#rest - $i)/@rest),
              $from => $rest[$i],
              @rest[ grep { $_ > $i } 0 .. $#rest ], $to);
    }

    my $d = shift @{ $pegs{$from} };
    print "$d: $from -> $to\n";
    unshift @{ $pegs{$to} }, $d;

    for my $i (reverse 0 .. $#rest) {
        move( int(($num + $#rest - $i)/@rest),
              $rest[$i] => $to,
              @rest[ grep { $_ > $i } 0 .. $#rest ], $from);
    }

}
[download]

Analysis: In the 3-peg version, we reduce the problem of moving N disks to a problem of moving N-1 disks. This is because we have only one peg of "scratch" space, and all disks on top of the largest one must go to the "scratch" peg.

With more than 3 pegs, we have more scratch space, so we can split the problem up more evenly between the multiple scratch pegs. So this is what we do here. When moving N disks, we split the N-1 disks above us as evenly as possible among the available scratch space. (this is the int(($num + $#rest - $i)/@rest) business, it's just a fancy way of splitting up the disks so that if the piles can't be divided exactly evenly, the first piles will get the extras). Then we move the bottom disk to the destination, and move the subpiles back (in reverse order of course!)

The problem is assigning the subproblems their scratch space. The trick is that if a subpile was moved after us, it has larger disks than us, and can be used for scratch. But we can't use subpiles that were moved before us, because they contain smaller disks. This is why we have the grep { $_ > $i } @rest. Of course, we can also use the source and destination pegs when appropriate, just like in the 3-peg case, so they are added to the scratch space in the recursive call as well.

We can get a great improvement from having more pegs:

10 disks with 3 pegs: Solved in 1023 moves
10 disks with 4 pegs: Solved in 57 moves
10 disks with 5 pegs: Solved in 35 moves
10 disks with 6 pegs: Solved in 29 moves
10 disks with 7 pegs: Solved in 27 moves
10 disks with 8 pegs: Solved in 25 moves
10 disks with 9 pegs: Solved in 23 moves
10 disks with 10 pegs: Solved in 21 moves
10 disks with 11 pegs: Solved in 19 moves
[download]

In fact, going from 3 pegs to 4 pegs is the most important, because instead of reducing the problem size by 1, we split it roughly in half every time (having 2 scrach pegs). This takes us from exponential number of moves needed to O(n log n). Then as the number of pegs approaches the number of disks, we approach O(n) number of moves, which makes sense because we only need to move each disk at most twice.