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_ID) - $t0, "\n" ;