I don't know what the rules of this game are, but the code below (31 lines) appears to work...

It ran 100x100, from (0,0) to (97, 92) in 0.33secs on my machine, where the OP code did the same in 0.87. Of course I have cheated and removed all the subroutines and changed the way the edges of the board are detected :-)

use strict ;
use warnings ;
use Time::HiRes qw(clock_gettime CLOCK_PROCESS_CPUTIME_ID) ;

my $t0 = clock_gettime(CLOCK_PROCESS_CPUTIME_ID) ;

my ($N, $x0, $y0, $VERBOSE) = @ARGV ;
if ((@ARGV < 4) || ($N < 4) || ($x0 >= $N) || ($y0 >= $N)) {
  die "Use: SIZE [4..] START_X [0..SIZE-1] START_Y [0..SIZE-1] [0,1]\n
+" ;
} ;

my @moves = ([-2,-1], [-1,-2], [-2 ,1],[-1 ,2], [2 ,-1], [1, -2],[2, 1
+],[1, 2]) ;

my @board = ( [(2, 3, (4) x ($N-4), 3, 2, 0, 0)], [(3, 4, (6) x ($N-4)
+, 4, 3, 0, 0)],
              map( { [(4, 6, (8) x ($N-4), 6, 4, 0, 0)] } (1..$N-4) ),
              [(3, 4, (6) x ($N-4), 4, 3, 0, 0)], [(2, 3, (4) x ($N-4)
+, 3, 2, 0, 0)],
              [(0) x ($N+2)], [(0) x ($N+2)] ) ;

for my $move (1..($N * $N) - 1) {
  my ($MIN, $x, $y) = (10, undef, undef) ;
  foreach (@moves) {
    my $vr = \$board[$x0 + $_->[0]][$y0 + $_->[1]] ;
    next if ($$vr == 0) || (--$$vr >= $MIN) ; 
    ($MIN, $x, $y) = ($$vr, $x0 + $_->[0], $y0 + $_->[1]) ;
  } ;
  die "Stuck at ($x0, $y0) at move $move\n" unless defined($x) ;
  print "$move: ($x0, $y0) -> ($x, $y)\n" if $VERBOSE ;
  ($board[$x0][$y0], $x0, $y0) = (0, $x, $y) ;
} ;  

print "Ended at ($x0, $y0) in ", clock_gettime(CLOCK_PROCESS_CPUTIME_I
+D) - $t0, "\n" ;
[download]