Список разборов

начинать мы можем со всех цифр кроме 0 и 8 значит из 8 цифр. Из каждой цифры ходом коня есть только 2 хода.

А значит ответ длинное число 8 * 2 * 2 * 2 * 2...(цифра 2 n-1 раз)

Хорошая задачка на динамику и длинную арифметику... Создаем матрицу A[n][10] типа BigInteger. Элемент A[i][j] - количество номеров длины i, заканчивающихся на цифру j. Далее зная количество номеров длины i и то, что после 0 может идти 4 или 6, после 1...