Понятно. Задача действительно хитрая, но не сказать чтобы сильно интересная. Поэтому давайте решать ее не для мобильного телефона, а для произвольного поля m*n. Конкретно для клавиатуры мобильного телефона можно посчитать хоть на бумажке. Думаю быстрее получится, чем писать даже самую топорную реализацию, честное слово.

Итак, как ходит конь всем известно. Рассчитать возможные ходы из текущей точки не проблема, простой алгоритм. Если начать строить возможные комбинации из конкретно взятой стартовой точки, то получится структура данных - дерево. С вершиной как раз в координатах старта. Таких деревьев будет ровно столько, сколько клеток на поле.

Наиболее простым вариантом работы с деревьями лично мне видится через СуБД, я бы наверное взял closure table, поскольку сразу имеем возможность посчитать глубину прямо через SQL запрос. Что нам собственно и нужно: найти ветвь минимальной длинны из неповторяющихся элементов для каждого из деревьев. Затем наименьшее из них.

Да, зачада имеет довольно высокую вычислительную сложность, хотя нам не нужно каждый раз достраивать дерево до конца. =)