Rats! I figured someone would beat me to a solution. I haven't looked closely at hossman's. I came up with the solution without looking at any references. Mine has configurable parameters, produces some elementary stats, and is shorter :P. It can be improved I'm sure, but I was just happy to finish it. Specifically, instead of rebuilding the entire hash, the changed key/values could be updated. TIMTOWTDI!

use strict;
my @slots;
my $max = 10;
my $empty = 0;
my $sum_moves = 0;
my %rlookup;
my $trials = 3;
my $min_moves = $max*$max;
my $max_moves = 0;

# initialize @slots
$slots[$_] = $_ for (0..$max);
srand time;

for my $ct (1..$trials) {
   # randomize @slots
   for (1..$max) {
      my $rand = int(rand $max) + 1;
      ($slots[$_], $slots[$rand]) = ($slots[$rand], $slots[$_]);
   }

   %rlookup = ();
   build_hash();
   my $moves = 0;
   my $unordered = inorder();
   while ($unordered || $empty) {
      print join " ", @slots, " \$empty: $empty  ";
      if ($slots[0] != 0) {
         print "move($rlookup{$empty}, $empty);\n";
         $slots[$empty] = $rlookup{$slots[$empty]};
         $slots[$rlookup{$empty}] = 0;
         $empty = $rlookup{$empty};
      } else {
         print "move($unordered, $empty);\n";
         ($slots[$empty], $slots[$unordered]) = ($slots[$unordered], $
+slots[$empty]);
         $empty = $unordered;
      }
      $moves++;
      build_hash();
      $unordered = inorder();
   }
   print join " ", @slots, " \$empty: $empty\n";
   print "Trial: ", pack("A5", $ct), "  Moves: $moves\n\n";
   $min_moves = $moves if $moves < $min_moves;
   $max_moves = $moves if $moves > $max_moves;
   $sum_moves += $moves;
}

print "Number of slots: $max\n";
print "Trials: $trials\n";
print "Average Moves: ", $sum_moves / $trials, "\n";
print "Minimum Moves: ", $min_moves, "\n";
print "Maximum Moves: ", $max_moves, "\n";

sub inorder {
   my $i;
   for (1..$max) {
      $i = $_;
      last if $_ != $slots[$_];
   }
   return $i % $max;
}

sub build_hash {
  $rlookup{$slots[$_]} = $_ for (0..$max);
}
[download]

Sample Output

0 2 3 7 6 4 10 5 8 9 1  $empty: 0  move(1, 0);
2 0 3 7 6 4 10 5 8 9 1  $empty: 1  move(10, 1);
2 1 3 7 6 4 10 5 8 9 0  $empty: 10  move(6, 10);
2 1 3 7 6 4 0 5 8 9 10  $empty: 6  move(4, 6);
2 1 3 7 0 4 6 5 8 9 10  $empty: 4  move(5, 4);
2 1 3 7 4 0 6 5 8 9 10  $empty: 5  move(7, 5);
2 1 3 7 4 5 6 0 8 9 10  $empty: 7  move(3, 7);
2 1 3 0 4 5 6 7 8 9 10  $empty: 3  move(2, 3);
2 1 0 3 4 5 6 7 8 9 10  $empty: 2  move(0, 2);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 1      Moves: 9

0 5 8 10 6 2 9 3 7 1 4  $empty: 0  move(1, 0);
5 0 8 10 6 2 9 3 7 1 4  $empty: 1  move(9, 1);
5 1 8 10 6 2 9 3 7 0 4  $empty: 9  move(6, 9);
5 1 8 10 6 2 0 3 7 9 4  $empty: 6  move(4, 6);
5 1 8 10 0 2 6 3 7 9 4  $empty: 4  move(10, 4);
5 1 8 10 4 2 6 3 7 9 0  $empty: 10  move(3, 10);
5 1 8 0 4 2 6 3 7 9 10  $empty: 3  move(7, 3);
5 1 8 3 4 2 6 0 7 9 10  $empty: 7  move(8, 7);
5 1 8 3 4 2 6 7 0 9 10  $empty: 8  move(2, 8);
5 1 0 3 4 2 6 7 8 9 10  $empty: 2  move(5, 2);
5 1 2 3 4 0 6 7 8 9 10  $empty: 5  move(0, 5);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 2      Moves: 11

0 6 7 4 5 2 3 1 8 9 10  $empty: 0  move(1, 0);
6 0 7 4 5 2 3 1 8 9 10  $empty: 1  move(7, 1);
6 1 7 4 5 2 3 0 8 9 10  $empty: 7  move(2, 7);
6 1 0 4 5 2 3 7 8 9 10  $empty: 2  move(5, 2);
6 1 2 4 5 0 3 7 8 9 10  $empty: 5  move(4, 5);
6 1 2 4 0 5 3 7 8 9 10  $empty: 4  move(3, 4);
6 1 2 0 4 5 3 7 8 9 10  $empty: 3  move(6, 3);
6 1 2 3 4 5 0 7 8 9 10  $empty: 6  move(0, 6);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 3      Moves: 8

Number of slots: 10
Trials: 3
Average Moves: 9.33333333333333
Minimum Moves: 8
Maximum Moves: 11
[download]

--Jim

Update: Hmmm . . . after much thought, this approach uses the first out-of-sequence slot for the initial move. Once the initial move is made, the rest is optimal, but it raises a potential flaw--perhaps by pre-testing each of the unordered initial moves, the optimal solution for any given trial could be determined. I'll do some more experimenting and post the results.