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 :(