Your

my $inversions = 1;
while ($inversions % 2) {
    @board = (0, shuffle(1..15));
    $inversions = 0;
    for my $x (1 .. 15) {
        for my $y ($x + 1 .. 15) {
            $inversions++ if $board[$x] > $board[$y];
        }
    }
}
[download]

bothers me a little, because the code is asserting we have one inversion, and then that we have none, and then counting them. It seems… wrong, somehow, to assert at the start that we have one inversion, beginning counting them — especially because that assertion is followed immediately by a contradictory one. So I switched it to

my $inversions;
do {
  $inversions = 0;
  @board = (0, shuffle(1..15));
  # @board = (1,0,2..15); # for testing
  for my $x(1..15) {
    for my $y($x+1..15) {
      ++$inversions if $board[$x]>$board[$y]
    }
  }
} while $inversions % 2;
[download]

I'd appreciate your letting me know what you think.