Here's my solution.
It's surely not optimal, but it's a very basic extension to the 3-peg solution, so the code is very short.
It uses O(d1/(p-3))
moves
O(2d/(p-2))
moves for the solution with d disks and
p pegs (I'm too lazy to calculate the exact numbers).
(Updated fomula again. The O sign is meant if p
is constant but d->inf)
Update: this is probably very suboptimal for more than 4 pegs.
#!/usr/local/bin/perl
use warnings; use strict;
$ARGV[0] =~ /(\d+)/ or die;
my $pegs = $1;
$ARGV[1] =~ /(\d+)/ or die;
my $disks = $1;
{
my @pegnames = "A" .. "Z";
sub printmove {
my($d, $f, $t) = @_;
print $d, ": ", $pegnames[$f], " -> ", $pegnames[$t], "\n"
}
}
sub rec {
my($n, $s, $d, $t, @o) = @_;
$n > 0 or return;
my $k = @o < $n - 1 ? @o : $n - 1;
#warn "[($n:${\($n-$k)} $s->$d]\n";
rec($n - $k - 1, $s, $t, $d, @o);
printmove($n - $k + $_, $s, $o[$_]) for
0 .. $k - 1;
printmove($n, $s, $d);
printmove($n - $k + $_, $o[$_], $d) for
reverse(0 .. $k - 1);
rec($n - $k - 1, $t, $d, $s, @o);
#warn "[)]\n"
}
rec($disks, 0, 1, 2 .. $pegs - 1);
__END__
