Самый длинный путь - эта задача нерешаема, т.к. в самом начале игры змейка будет просто кругами бегать ВЕЧНО, ведь нет запрета на посещение одной и той же клетки.
Но вы решаете совсем другую задачу.
У вас задача съесть точку и удлинить змею, но не уткнуться в себя самого.
Для этого задаёте список правил, которые, с большой долей вероятности, позволят эту точку избегать:
2. двигаться вдоль границ игрового поля
1. двигаться вдоль тела змейки
3. ВАЖНО! не создавать петли. т.е. приближаясь к хвосту/стенке нежелательно оставлять незаполненные области
4. избегать движения к точке
5... ещё что-нибудь, что сразу в голову не приходит
X. делать пункты 1-4 на несколько ходов вперёд. Допустим, на 50 щагов вперёд можно без проблем просчитываь. Если на 47 шаге скушали точку, при этом оставались пустые клетки, то отматываете назад и пробуете двигаться в другие стороны.