Можно скопировать свой гостевой пост в следующий (залогиенный) и отредактировать как надо, а гостевой потом удалить (модератора попросить, чтобы удалил).

В следующий раз так и сделаю. А пока - что вышло, то вышло.
Так вот, у меня такое подозрение, что решений у этой задачи не восемь, а больше.
Может быть коротких решений восемь.
Просто я что-то не вижу ошибок в длинных решениях.

Короче говоря, задача сформулирована была неправильно !
Тут уже отмечали, что надо наложить требование, чтобы позиции в
решении не повторялись, иначе количество решений просто бесконечно.
Но дело даже не в этом. У этой задаче не 8 решений вообще,
а 8 кратчайших решений. Их задача и должна была предлагать найти.
А найти все решения - вообще малореальная задача.
Возможно вообще нерешаемая в приемлемое время.
У меня вот программа нашла решение в 210 ходов.
И из соображений симметрии должно быть минимум еще одно той-же длины.

Вот я в своей программе положил ограничение - искать решения не длиннее чем в 22 хода :
И она за три минуты находит 8 решений в 22 хода и что более коротких нет.
Короче говоря, у меня получилось, что задача имеет 8 кратчайших
решений в 22 хода (11 ходов белыми и 11 черными).
Вот пример такого решения :
P.S. Если в программе положить максимальную длину решений в 26 ходов,
то за пару часов она найдет 8 решений длиной 22 (11+11) хода и 234 решения
длиной 26 (13+13) ходов и никаких других решений. Похоже, чем длиннее
решения, тем больше у них вариантов, причем с ростом длины количество
вариантов растет взрывообразно. А поскольку известно решение и в 210 ходов,
то возможно, что число ВСЕХ решений - астрономическое.

Я тут подумал, что эту задачу можно поисследовать математически.

1.) Докажем, что черные должны сделать столько же ходов, что и белые
При каждом ходе конь меняет свой цвет.
Дадим коню на черном поле вес ноль, а на белом - вес 1.
Тогда вес всех коней в исходной позиции 3 и в конечной 3, т.е.
и в исходной позиции он нечетный и в конечной нечетный.
Ясно, что любой ход будет менять четность веса всех коней,
поскольку вес ходящего коня будет или увеличиваться на 1
или уменьшаться на 1. Значит после хода белых вес всех
коней стане четным, после хода черных - нечетным и так по кругу.
В конечной позиции он нечетный, а значит конечная позиция будет
достигнута после хода черными, а значит черные сделают столько-же
ходов, что и белые. ЧТД

2.) Докажем, что белые (а значит равно и черные) должны сделать нечетное число ходов.
При каждом ходе конь меняет свой цвет.
Дадим коню на черном поле вес ноль, а на белом - вес 1.
В исходной позиции вес белых коней 1, т.е. нечетный.
В конечной позиции вес белых коней 2, т.е. четный.
На каждом ходу белых четность веса белых коней будеть меняться,
поскольку вес белых коней будет увеличиваться на 1 или уменьшаться на 1.
А значит, чтобы прийти в конечную позицию, белые (а значит равно и
черные) должны сделать нечетное число ходов. ЧТД.

Короче говоря все решения задачи имеют длину (2*n+1)+(2*n+1), где n-целое.
Значит после решений в 11+11 и 13+13 ходов следует ожидать решений
в 15+15 ходов.

3.)Докажем без перебора, что решений менее чем в 9+9 ходов не может быть
Снимем черных коней с доски.
Введем понятие расстояния до нижней строчки доски :
232
111
232
000
Видно, что белым коням, чтобы кратчайшим путем попасть на нижнюю
строчку нужно минимум сделать 2+3+2 = 7 ходов. Значит решений, более
коротких чем 7+7 нет. Но оба белых коня, находящиеся в верхней строчке
в выделенных жирным позициях не могут оба проти путь 2->1->0, поскольку
тогда они должны будут оба попасть в одну и ту-же выделенную жирным
позицию на нижней строчке. Один из белых коней не может пройти
кратчайшим путем, значит он должен сделать минимум на ход больше. Значит
белые должны сделать больше 7 ходов. Значит решения 7+7 не существует,
а тогда решений, более коротких, чем 9+9 нет. ЧТД

Вот как доказать без перебора, что решений в 9+9 тоже нет - не знаю.

4.) Докажем, что всегда возможна зеркальная партия
В начальной позиции верхние 6 и нижние 6 клеток являются зеркальными
отображениями друг друга с инверсией цвета. Аналогично и в конечной позиции.
Докажем, что если белые сделали ход, то черные всегда могут сделать
зеркальный ход. Начальная позиция - зеркальная. Если черные будут
делать ход, зеркальный ходу белых, то любая последующая позиция тоже
будет зеркальная. Пусть i-я позиция зеркальная и ход белых.
Белые сделали ход в клетку К. Поскольку до хода белых позиция была
зеркальная то, до хода белых клетка, зеркальная клетке К, была пустой
и для черных коней не под боем. Эта клетка не могла быть занята
в результате хода белых, поскольку никакая клетка не зеркальна себе.
Эта клетка не могла оказаться под боем для черных в результате хода
белых, потому-что ни в какой клетке конь не бьет клетку зеркальную себе.
А значит черные могут сделать зеркальный ход. И это для любой позиции.
Значит возможна зеркальная партия. ЧТД.

Вот как без перебора доказать, что найдется зеркальная партия, решающая задачу
- пока не сообразил. С перебором-то такая партия отыскивается легко.
Вот зеркальная партия из решения в 11+11 ходов, показаны только
зеркальные позиции после ходов черными :
Вообще говоря, я искал закономерности, позволяющие резко оптимизировать
алгоритм по скорости и подобраться к обратной задаче - найти САМОЕ ДЛИННОЕ
решение с неповторяющимися позициями. Но пока без результата.
Зеркальные партии позволяют ходить только белыми, а ход черных идет
автоматом. Но как доказать, что среди решений любой длины найдется
зеркальное - не соображу. А обязательная нечетность ходов белыми в
в решении может быть поможет перебирать сразу двойные ходы белыми

P.S. Поскольку исходная (да и конечная) позиции симметричны относительно
вертикальной прямой, проходящей через центр доски, то зеркальные партии
должны существовать парами. Пара появится как только мы тронем белого
коня в углу доски. Парная партия будет симметричной с ходом белым конем
в другом углу доски. Собственно говоря, приведенные выше два решения 11+11
- это и есть такая симметричная пара.

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

Все эти теор. исследования ни к чему.
Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций и начать проводить траектории по его ребрам из начальной
позиции в конечную, пока эти траектории не закончатся. Здесь будет перебор, но не тупой перебор. Информацию о пройденных траекториях нужно
оставлять в "графской" памяти.

Так просто, из чистого любопытства
За пару суток долбления с макс.глубиной 30 моя программа нашла решений :

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

Число всех позиций с помощью немного упрощенного генератора от garbler'a



ps.
Отсюда и получается оценка длины максимального решения.
число траекторий получается грубо в интервале 2^1334.
Даже если на 3 порядка быстрее вычислять одну траекторию чем у существующих решений (при более 'умном' переборе)
все равно не получить все решения в приемлемое время.

Все решения никому не нужны. Интересует одно, но самое длинное.

Должно быть еще условие невозврата к пройденным позициям, иначе можно любое решение удлинить до бесконечности, делая бесконечно ходы туда-сюда.

Формального доказательства существования гамильтонова пути в графе не существует.
Можно лишь утверждать, что такой путь не больше 667 ходов белыми и соответственно 667 ходов черными.

Поправка:
Можно лишь утверждать, что самый длинный путь не больше 667 ходов белыми и соответственно 667 ходов черными.