Путь коня или какова польза ограничений?
Есть простая оптимизация - из всех возможных ходов из текущей клетки перебирать сначала те, которые ведут в клетку с наименьшим количеством возможных следующих ходов (это надо проверить и все ходы через один ход и посмотреть, а обойдены ли те клетки уже). Эта оптимизация как раз заставит коня ходить сначала вокруг стенки и по спирали подходить к центру.
Для больших полей вообще может иметь смысл перестроить алгоритм на определение самой "зажатой" на текущий момент клетки (той, в которую можно попасть из наименьшего количества клеток и при этом хотя бы одна из них уже занята) - и выстраивания кратчайшего пути до нее. Возвращаясь, если такой путь приводит к недостижимым клеткам.