Данный код представляет результат моего брейншторма относительно поиска решения этой задачи. Код был портирован с PHP на Java после того как я упёрся в производительнось PHP7. Алгоритм работает с задаваемой величиной доски и с задаваемой стартовой позицией.
Код не был адаптирован под удобочитаемость и понятность (плюс это первый мой код на Java), по-этому описываю принцип его работы здесь. Задача решается "в лоб" классическим перебором с некоторыми улучшениями. Сначала о классическом переборе.
Каждый ход наш конь должен выбрать один из нескольких вариантов движения по доске. Этот вариант выбирается из массива допустимых шагов, которых у коня в шахматах 8. Таким образом, если первым в массиве мы выбираем идти вверх и влево, то так и происходит. А если выходим за границу доски или эта позиция уже посещалась, то пробуем пойти по следующему шагу из массива шагов. Чаще всего таким образом конь заходит в тупик. Используется метод обхода в глубину, так как количество шагов прохождения до тупика или полного покрытия доски несравнимо меньше хранения в памяти всех развилок, появляющихся при каждом шаге (я пробовал обход в ширину... 16Гиг оперативки выедало достаточно быстро :) После тупика конь возвращается на шаг назад и пробует пойти используя другой ход из массива возможных ходов. Так и происходит полный перебор.
Улучшение заключается в манипуляции массивом возможных ходов. По аналогии с методом обхода лабиринта, в котором могут быть двойные развилки, у обходящего есть правила "левой руки" либо "правой руки". То есть каждую развилку мы проходим в левый ход пока не достигнем тупика, отходим до развилки (задом) и используем следующий вариант из возможных (правый ход). В данном случае улучшение с манипуляцией массивом заключалось бы в том, чтобы перестать поворачивать влево, если мы перебрали очень много неудачных вариантов, вернуться в начало и попробовать обходить лабиринт поворачивая вправо. Так и с конём. Задаётся лимитирующее количество итераций, по наступлению которого данный массив возможных ходов признаётся неэффектвным и делается ещё одна попытка обхода используя другой массив возможных ходов. Таким образом алгоритм находит не только первый возможный обход всей доски, но и самый эффективный массив возможных ходов, который приводит к самому короткому обходу. Количество всех возможных вариантов массива возможных ходов - 40320.
При таком подходе был найден идеальный массив возможных вариантов для доски с размером стороны 5. Количество итераций было равно 24 (5*5-1). Также с помощью этого улучшения у меня начала решаться задача для доски с размером 8 и даже 9. Минусом данного улучшения является то, что алгоритм не всегда отрабатывает успешно (упирается в лимит) при некоторых "плохих" начальных позициях.
В перспективе можно было бы озаботиться перебором не только массива возможных вариантов, но и способом обхода всех вариантов этого массива, дабы сократить общее время работы алгоритма поиска наилучшего массива возможных вариантов.