Кратчайший путь двух коней

На шахматной доске стоят два коня, также заданы две клетки, в которые необходимо переставить этих коней. Найдите способ переставить коней в заданные клетки за наименьшее количество ходов. Кони ходят по шахматным правилам, порядок ходов не важен, конь не может становиться на клетку, если она занята другим конем.
Входные данные
Во входных данных записаны первоначальные координаты первого и второго коня, затем координаты клеток, в которых должны оказаться первый и второй конь соответственно Каждая координата состоит из латинской буквы a-h и цифры 1-8, написанных слитно.
Выходные данные
Программа должна вывести последовательность ходов коней. Первая строка выходных данных содержит общее число ходов. Последующие строки задают ходы коней, по одному ходу на строку. Первым символом в строке должен быть номер коня (1 или 2), затем, через пробел, координаты клетки, в которую он переставляется. Необходимо вывести только одно из возможных оптимальных решений.
Пример входных данных
a1
с2
c2
a1
Пример выходных данных
4
1 b3
1 d4
2 a1
1 c2