Hmm, te conviene crear un arreglo de enteros que represente el tablero, es decir 8 x 8, y que en cada posición coloques el valor de las posibilidades que tenés para moverte a este, por ejemplo:
int[][] accesibilidad = {
{2, 3, 4, 4, 4, 4, 3, 2},
{3, 4, 6, 6, 6, 6, 4, 3},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{4, 6, 8, 8, 8, 8, 6, 4},
{3, 4, 6, 6, 6, 6, 4, 3},
{2, 3, 4, 4, 4, 4, 3, 2}
};
Esto te daria las posibilidades que tiene el caballo de acceder desde cada posición hacía otra. Ahora lo que tendrías que hacer es actualizar este arreglo por cada paso del caballo. Si empiezas en la esquina izquierda, a esta le tendrias que colocar 0 porque ya no puedes acceder a esta, y a TODAS las posiciones a las que tienes acceso desde esta le restas 1. Esto es porque de ahora en más esas posiciones van a poder ser accedidas desde menos lugares.
En fin, creo que esto resolvería tu duda, no se si me explique bien, cualquier cosa me dices.