#echo 5 3 3 1 | gawk -f kt.awk # the very very slow way
#echo 5 3 3   | gawk -f kt.awk # the fast way
BEGIN { split("2  2 -2 -2 1  1 -1 -1",X)
        split("1 -1  1 -1 2 -2  2 -2",Y) }
      { N=$1; Slow=$4; move($2,$3,0) }
function move(x,y,m,  i) {
    if (cantMove(x,y)) return 0
    P[x,y] = ++m
    if (m == N^2) exit printBoard()
	Slow ? tryAllMoves(x,y,m) : tryBestMove(x,y,m) 
}
function cantMove(x,y) { 
	return P[x,y] || x < 1 || x > N || y < 1 || y > N 
}
function printBoard(   i,j) {
   for(i=1;i<=N;i++) {
       for(j=1;j<=N;j++) printf(" %3s",P[i,j])
       print "" }
}
function tryAllMoves(x,y,m,    i) {
	for(i in X) move(x+X[i],y+Y[i],m) 
    P[x,y]=0 # if we get here, then all moves have failed 
}
function tryBestMove(x,y,m,    i) { 
	i = bestMove(x,y)
	move(x+X[i],y+Y[i],m) 
}
function bestMove(x,y,   c,min,out,i) {
   #Warnsdorff's rule: go to where their are fewest next moves
   min = N^2 + 1 # an impossibly large number of blank cells
   for(i in X) 
       if (! cantMove(x+X[i],y+Y[i])) {
             c = countNext(x+X[i],y+Y[i])
             if (c < min) {min = c; out = i }}
   return out
}
function countNext(x,y,     out,i) {
   for(i in X) out += (! cantMove(x+X[i],y+Y[i])) 
   return out
}