Кто может сделать быстрее задачу о "Путешествии Коня"?

Задача похожа на ту, что про 8 ферзей.
Условия: доска 8*8, начальное положение коня безразлично, конь не должен дважды попадать на одну и ту же ячейку доски.
Всего ходов у вас должно получится 64.

 

быстрее чего? (кого)

 

censored
хороший вопрос

 

censored
Наверное быстрее всех?

 

Хорошо бы сначала ферзей до ума довести, а потом уже за следующую задачу браться.

 

Это классика. Врядли алгоритм можно как-то улучшить.

 

Я ещё забыл спросить: у кого-нибудь есть готовая программа, выполняющая задачу о Путешествии коня? У меня есть готовая программа, но она написана на С++, хотя хотелось бы транслировать её в МАСМ (что я сейчас и делаю) для увеличения производительности на моём P3 710 MHz. Я тестил ту, что на С++ - вроде работает правильно. Сам алгоритм не оптимизирован, но 500 000 ходов/сек делает при релиз-компиляции на M!cr0$0ft Visual C++ 6.0 с указанием оптимизации на скорость

 

Я бы добавил прогу, но не знаю как её постить в форуме!!! Если знаете - подскажите как.

 

Попробуйте сделать алгоритм быстрее того, что у меня. Я ещё доработаю программу и потом выложу её. Дня 2 уйдёт на это...

 

Я алгоритм сам придумывал. А есть классический алгоритм этой головоломки и если есть, то где найти его?

 

cpp_and_wasm
Помню, на олимпиаде как раз попалась эта задача. Потом нашёл в сети кучу ресурсов с готовыми решениями. Совсем недавно опять наткнулся на эту самую головоломку, но уже в какой-то книге.

Погуглить.

 

ДЕРЖИТЕ ПРОЕКТ!!! ЗАЦЕНИТЕ, НО СИЛЬНО НЕ РУГАЙТЕ!!! У меня компиляция прошла нормально. Жаль вот, что не на ассемблере писал , но скоро будет!

 

"BishopTravel.zip" - задача точно про коня ?

 

У меня на доске 8х8 "ходит" со скоростью ~50 млн. ходов/сек и останавливаться и не думает

 

НУ, извините, если неправильно обозвал... )))))

 

хе-хе!!! Если я правильно подсчитал, то на доске 8*8 может быть 64! комбинаций, т.е. 1,2688693218588416410343338933516e+89 ходов!!!

 

Если нужно просто обойти всю доску как можно быстрее, то есть одна эвристика. При каждом ходе выбирать поле с которого меньше всего возможностей сходить на ещё неиспользованное поле. Когда-то давно воевал с этой задачей. Конь упорно не хотел идти в угол (это был единственный вариант) и переберал массу лишних вариантов.

====

В зависимости от поля конь имеет возможность переместиться на следующее количество полей

2 возможности - 4 поля
3 - 8
4 - 20
6 - 16
8 - 16

Учитывая что уже конь использовал одну возможность как вход в текущее поле, то имеем.

1^4+2^8+3^20+5^16+8^16 < 8^17 ~ 2*10^15

Так как в реальности многие возможности уже будут невозможны, реальное число вариантов гораздо меньше.

 

Когда-то в школе мы от нефиг делать на уроках играли в игру: кто больше сделает ходов конём по доске. Играли, пока не обнаружилось, что если выйти из угла и идти вдоль стенок (ближайшие две клетки к ней), то две внешние полосы заполняются тривиально, а в центре остаётся ещё один неправильный квадрат (4 на 4) такого вида (расположение выреза мы, вроде как вольны выбирать сами, но наличие его обязательно, т. к. нормальное хождение по кругу с прохождением углов возможно только на досках 3n-типа):
1000
1000
0000
0000
заполнение которого чуть посложнее, но тоже возможно.
Дык вот, к чему я это всё: есть довольно простая и понятная траектория по которой можно гонять коня без всякого перебора. Задача сводится к поиску способа как посадить на неё коня из произвольной точки.
Имхо выйдет быстрее перебора

 

А для произвольной доски ?

 

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