Paseos de una ficha en un tablero

Los números $1,2,3,\ldots,n^2$ se colocan en las casillas de una cuadrícula de $n\times n$, en algún orden, un número por casilla. Una ficha se encuentra inicialmente en la casilla con el número $n^2$. En cada paso, la ficha puede avanzar a cualquiera de las casillas que comparten un lado con la casilla donde se encuentra. Primero, la ficha viaja a la casilla con el número 1, y para ello toma uno de los caminos más cortos (con menos pasos) entre la casilla con el número $n^2$ y la casilla con el número 1. Desde la casilla con el número 1 viaja a la casilla con el número 2, desde allí a la casilla con el número 3, y así sucesivamente, hasta que regresa a la casilla inicial, tomando en cada uno de sus viajes el camino más corto. El recorrido completo le toma a la ficha $N$ pasos. Determine el menor y el mayor valor posible de $N$.