But if I can accept the challenge I'd present a commandline version of the 15 puzzle that is a bit longer than your (25 vs 15 lines) but always poses resolvable games.. ;=)

unless ($^W){use strict; use warnings;}
use List::Util qw(shuffle first);
my @tbl = ([1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]);
my $e = [3,3];
for (1..$ARGV[0]||1000) {
  my $new = (shuffle &ad($e))[0];
  $tbl[$e->[0]][$e->[1]] = $tbl[$new->[0]][$new->[1]];
  $tbl[$new->[0]]->[$new->[1]] = 16;
  $e = [$new->[0],$new->[1]];
}
while(1){
  print +(join ' ',map{$_==16?'  ':sprintf '%02s',$_}@{$tbl[$_]}),"\n"
+ for 0..3;
  my $m = <STDIN>;
  chomp $m;
  die "Enter a number to move!" unless $m;
  my $tile=first{$tbl[$$_[0]]->[$$_[1]]==$m}map{[$_,0],[$_,1],[$_,2],[
+$_,3]}0..3;
  my $new=first{$tbl[$$_[0]]->[$$_[1]]==16}&ad(grep{$tbl[$$_[0]]->[$$_
+[1]]==$m}
          map {[$_,0],[$_,1],[$_,2],[$_,3]}0..3);
  if ($new){$tbl[$$new[0]][$$new[1]]=$m;$tbl[$$tile[0]][$$tile[1]]=16;
+}
  system ($^O eq 'MSWin32' ? 'cls' : 'clear');
}
sub ad{
      my $e = shift; grep {$_->[0]<4 && $_->[1]<4 && $_->[0]>-1 && $_-
+>[1]>-1}
      [$$e[0]-1,$$e[1]],[$$e[0]+1,$$e[1]],[$$e[0],$$e[1]-1],[$$e[0],$$
+e[1]+1]
}
[download]

Never reached such square brackets density..

L*

But it only takes one additional line (with a tiny bit of reshuffling and a very small golf trick involving // ) to get it to pose only resolvable games :)

#!/usr/bin/perl
use Tk;
use strict;
my ($mw, $hole, @a) = new MainWindow;
1 while @a = (map($_->[0], sort {$a->[1] <=> $b->[1]} map [$_, rand],
  1..15), 0), 1 & map { grep{ $a[$'] > $_ } @a[$_ + // .. 14] } 0..13;
sub xy { -row => $_[0] % 4, -column => int $_[0] / 4 }
for my $ii (0..15) {
  my ($num, $i, $but) = ($a[$ii], $ii);
  $hole = $i, next unless $num;
  $but = $mw->Button(-text => $num, -width => 2, -height => 2, -comman
+d
    => sub { $but->grid(xy(($i,$hole) = ($hole,$i))) if abs $i - $hole
    == 4 or abs $i - $hole == 1 and int $i/4 == int $hole/4
    })->grid(xy $i);
  }
MainLoop;
[download]

The extra line, however, spoils the whole "15 in 15" esthetic :(