Hanoi Challenge

We are all familiar with the towers of hanoi puzzle. It was most recently discussed at Recursion: The Towers of Hanoi problem. In the puzzle you have 3 pegs and a series of disks sorted from largest to smallest on one peg. You want to transfer the disks to another peg, moving one disk at a time and never putting a larger disk on a smaller one. The solution is well-understood, and there is only one way to make real progress at any move.

But most of us have not seriously thought about the case where there are 4 or more pegs to work with. In one sense this problem is easier - after all you can ignore all but 3 pegs and recycle the existing solution. However if you use the extra pegs, you can be more efficient. How much more efficient? Nobody knows for sure. Nobody has managed to prove what the most efficient general algorithm is for 4 pegs. Let alone 5 or more.

So here is the challenge: how efficient of programs can people come up with to solve the Hanoi puzzle with 3 or more pegs and an arbitrary number of disks? Let me specify this in more detail...

Let's have our hanoi programs take 2 arguments on the command line, the number of pegs available and the number of disks. The program will name the pegs A, B, C, etc. All of the disks start on peg A. They need to wind up on peg B. Each move is announced as follows:

(disk): (peg from) -> (peg to)
[download]

Putting this together, we expect something like this:

$ ./hanoi.pl 3 3
1: A -> B
2: A -> C
1: B -> C
3: A -> B
1: C -> A
2: C -> B
1: A -> B
[download]

The following test driver can be used to test the validity of output (if the programs finish that is - please make sure that they'll finish reasonably quickly). Look in its examples for how to use it.

#! /usr/bin/perl -w
use strict;
use Getopt::Long;
use Pod::Usage;

GetOptions(
  'pegs=i'      => \ my $peg_count,
  'disks=i'     => \ my $disk_count,
  'program=s'   => \ my $program,
  'verbose'     => \ my $verbose,
  'prompt'      => \ my $prompt,
  'help'        => \ my $help,
) or pod2usage(2);
pod2usage(1) if $help;


$verbose ||= $prompt;
$peg_count ||= 3;
$disk_count ||= 4;
$program ||= "./hanoi.pl";

my @pegs;
my %disks;
my $peg = 'A';
for (1..$peg_count) {
  push @pegs, $peg;
  $disks{$peg} = [];
  $peg++;
}
$disks{A} = [reverse 1..$disk_count];

open (PIPE, "$program $peg_count $disk_count |")
  or die "Cannot run '$program': $!";

my $move = 0;
while (<PIPE>) {
  chomp;
  $move++;

  print "Move $move: $_\n" if $verbose;

  die "Move $move: Invalid input '$_'\n"
    unless (/(\d+):\s*(\w+)\s*->\s*(\w+)/);

  my $disk = $1;
  my $from = $2;
  my $to = $3;

  die "Peg '$from' not found on move $move\n"
    unless exists $disks{$from};
  my $pile_from = $disks{$from};

  die "Disk $disk is not on top of peg '$from' at move $move\n"
    unless $pile_from->[-1] == $disk;

  die "Peg '$to' not found on move $move\n"
    unless exists $disks{$to};
  my $pile_to = $disks{$to};

  if (@$pile_to) {
    my $top = $pile_to->[-1];
    die "Disk $disk cannot go on top of disk $top at move $move\n"
      unless $disk < $top;
  }
  pop @$pile_from;
  
  if ($verbose) {
    foreach my $peg (@pegs) {
      print join " ", "$peg ", @{$disks{$peg}};
      print " -" if $peg eq $from;
      print " +$disk" if $peg eq $to;
      print "\n";
    }
    if ($prompt) {
      <STDIN>;
    }
    else {
      print "\n";
    }
  }
  push @$pile_to, $disk;
}

my @with_disks = grep {@{ $disks{$_} }} @pegs;
if (1 == @with_disks and $with_disks[0] eq 'B') {
  print "Solved in $move moves\n";
}
else {
  die "Not solved after $move moves\n";
}

__END__

=head1 NAME

hanoi-driver.pl

=head1 SYNPOSIS

 hanoi-driver.pl [opts]

=head1 OPTIONS

 -h --help       Print help and exit
 --pegs INT      How many pegs to have.  Default 3.
 --disks INT     How many disks to have.  Default 4.
 --program STR   What test program to run.  Default ./hanoi.pl.
 -v --verbose    Keep a running commentary up about each step
 --prompt        Wait for STDIN on each step.  Implies verbose.

=head1 DESCRIPTION

Test driver for programs that solve the hanoi puzzle.  It will
execute the program, study the output, die if any impossible
moves get made or the puzzle is not solved properly, and then
report how many steps it took.

If you set verbose mode it will show the game being played.

=head1 EXAMPLES

This will execute "./hanoi.pl 3 4" and expect to see a
solution to the hanoi puzzle with 3 pegs and 4 disks.

  ./hanoi-driver.pl

This will execute "./hanoi.pl 3 4" and expect to see a
solution to the hanoi puzzle with 3 pegs and 4 disks.
The output will play the solution out.

This will execute "./another_program" and expect to see a
solution to the hanoi puzzle with 5 pegs and 15 disks.

  ./hanoi-driver.pl --program=./another_program --pegs=5 --disks=15

=head1 AUTHOR

Ben Tilly (tilly on perlmonks)
[download]

Of course I have my own solution to offer. But given that I've had more time to think about this than anybody else, I'll not post that until tomorrow.

UPDATE: Added READMORE tag. I thought I had one, but Arunbear noticed that I did not. Fixed.

UPDATE: ambrus noticed that I had the wrong peg in an error message. Oops. Fixed.

Comment on Hanoi Challenge Select or Download Code

Replies are listed 'Best First'.
Re: Hanoi Challenge by blokhead (Monsignor) on Oct 22, 2004 at 19:10 UTC
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. blokhead	[reply] [d/l] [select]
Re^2: Best possible counts for a few test cases (in readmore) (Hanoi Challenge) by tye (Sage) on Oct 22, 2004 at 20:18 UTC
It can be done more efficiently than this. You shouldn't divide the work up evenly. Below are some special cases and the smallest solution sizes possible (I believe) for them. If P is the number of pegs, D is the number of disks, and M is the minimum number of moves for which a solution exists, then: Read more... (406 Bytes) I may write up why this is so, but I suspect someone else is likely to beat me to that. And if you try to figure out why I picked these cases, you'll probably have a good hint for part of a good solution for the general problem. (: - tye	[reply] [d/l]
Re^3: Best possible counts for a few test cases (in readmore) (Hanoi Challenge) by blokhead (Monsignor) on Oct 22, 2004 at 20:30 UTC
I was just realizing something along these lines. It would be better to give a larger proportion of disks to the subpiles which will have more scratch space. How much more, I don't exactly know (yet). I've been trying to come up with a simple way to minimize the recurrence for the general case, but no luck. If all else fails, you could search through all partitions of N-1 to find the best subproblem split, but that's no fun ;) blokhead	[reply]
Re^2: Hanoi Challenge by tilly (Archbishop) on Oct 22, 2004 at 20:21 UTC
I'd suggest revisiting your analysis of how good 4 pegs are. With your program I see: `10 disks with 4 pegs: Solved in 57 moves 20 disks with 4 pegs: Solved in 1137 moves 30 disks with 4 pegs: Solved in 33377 moves 40 disks with 4 pegs: Solved in 1050849 moves` [download] That doesn't look like O(n*log(n)) to me! Does anyone else think that they can do better?	[reply] [d/l]
Re^2: Hanoi Challenge by Elgon (Curate) on Oct 22, 2004 at 19:50 UTC
Blokhead, A query; Surely it is possible only to solve the problem in exactly O(n) when there is one more peg than discs plus one. (It could be that I misunderstand the O(n), O(log n), O(n^2) notation...) Example: In the quickest solution for three pegs and three discs, for example, the large disc moves once, the medium disc moves twice and the smallest disc moves four times. Example 2: Where there are three rings and four pegs, each ring only moves twice. Elgon UPDATE:Thanks to Thor for pointing out my error, below. As a general rule, I find that for n pegs and n discs the number of moves required is 2n + 1. If, however, there are n discs and n + 1 (or more) pegs, then 2n - 1 moves are required. Can someone with a better understanding of the formalisms tell me whether either of these is O(n) ??? It is better either to be silent, or to say things of more value than silence. Sooner throw a pearl at hazard than an idle or useless word; and do not say a little in many words, but a great deal in a few. Pythagoras (582 BC - 507 BC)	[reply]
Re^3: Hanoi Challenge by thor (Priest) on Oct 22, 2004 at 20:16 UTC
Example 2: Where there are three rings and four pegs, each ring only moves twice. Does it? If we're trying to get ring C to peg 4 A -> 1 B -> 2 C -> 4 B -> 4 A -> 4 In the case of n disks and n+1 pegs, the last disk moves only once. thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]
Re: Hanoi Challenge by tilly (Archbishop) on Oct 22, 2004 at 16:34 UTC
And to get things going, I'll post the bad solution that everyone should be able to beat. This ignores all but the first 3 pegs. `#! /usr/bin/perl -w use strict; my $disk_count = pop; solve('A'..'C', reverse 1..$disk_count); sub solve { my ($peg_from, $peg_to, $peg_hold, $first_disk, @rest) = @_; return unless $first_disk; solve($peg_from, $peg_hold, $peg_to, @rest); print "$first_disk: $peg_from -> $peg_to\n"; solve($peg_hold, $peg_to, $peg_from, @rest); }` [download] Again, this makes no use of extra pegs, which you can use to beat it.	[reply] [d/l]
Re: Hanoi Challenge by fruiture (Curate) on Oct 22, 2004 at 18:13 UTC
Well, no idea if this is very efficient, but it seems to solve all situations (the hanoi-driver does not complain) and is based on your code, just generalized. `#! /usr/bin/perl -w use strict; my $peg_count = shift; my $disk_count = shift; my @pegs; { my $p = 'A'; push @pegs , $p++ for 1 .. $peg_count; } solve( [ @pegs ] , reverse 1..$disk_count); sub solve { my ($pegs, $first_disk, @rest) = @_; my $from = shift @$pegs; my $to = shift @$pegs; my $hold = shift @$pegs; return unless $first_disk; solve( [ $from, $hold, @$pegs, $to ] => @rest ); print "$first_disk: $from -> $to\n"; solve( [ $hold, $to, @$pegs, $from ] => @rest ); }` [download] Update: Well, it is absolutely NO more efficient than using 3 pegs anyway, but at least it works. -- http://fruiture.de	[reply] [d/l]
Re^2: Hanoi Challenge by tilly (Archbishop) on Oct 22, 2004 at 18:26 UTC
Good try. It works, but gains nothing in efficiency from using all pegs. Try it with 5 pegs and 4 disks. It takes 15 moves to finish - exactly the same as the 3 peg version. Try solving it by hand. You should have no problem finishing in 7 moves. Can you find a way to have the program to benefit more from using all pegs?	[reply]
Re: Hanoi Challenge by tilly (Archbishop) on Oct 23, 2004 at 17:04 UTC
And here is my solution. Read more... (3 kB) I think that blokhead was headed in this direction and would have gotten there in time. I'm curious about tye's reasoning, and suspect that he was close to the same path that I followed. Here are details. Read more... (2 kB)	[reply] [d/l]
Re: Hanoi Challenge by ambrus (Abbot) on Oct 23, 2004 at 18:33 UTC
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(d^1/(p-3)) moves~~ O(2^d/(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. Read more... (1033 Bytes)	[reply] [d/l]


good chemistry is complicated, and a little bit messy -LW
	PerlMonks