Хаскель — ход конем

[wormball]

Помнится, я в 2002 году на трубо-паскале делал 15*15 за несколько секунд на 80486.

[voyager-1]

Когда-нибудь эту же задачу на квадрате 5*5 можно будет закодить в одну строку на каком-нибудь ядрёном потомке Haskell-я и Ruby. Но она всё равно будет требовать для выполнения несколько секунд работы квантового компьютера на миллион кубитов.

Да, и по поводу строки

Никто не говорил что она будет короче этой)

[aamonster]

Стоп. Вы ищете не все решения, а только одно, я правильно понял?
Тогда следует использовать эвристику — стараться идти в клетку, из которой доступно меньше всего ходов.

Если попробуете — расскажите, какой эффект дало.

[shale]

Спасибо за подсказку, прекрасно работает. Подредактировал статью.

[WinPooh73]

В зачитанной в детстве до дыр книге Гика "Шахматы и математика" эта задача подробно разбиралась. Запомнилась основная эвристика — правило Варнсдорфа: из возможных клеток очередной ход коня надо делать на ту, откуда есть МЕНЬШЕ возможных продолжений. Несмотря на всю контр-интуитивность, стратегия работала как часы на самых разных досках! Вы не пробовали добавить эту эвристику в свою программу и сравнить эффективность алгоритмов?

[shale]

Интересная идея. В принципе реализовать несложно. Надо отсортировать список возможных ходов по определенному признаку. А сложность сортировки даже меньше квадрата

[shale]

Вау! Невероятно! Работает! 25x25 меньше, чем за минуту. Спасибо, придется подкорректировать статью.

[shale]

А если убрать проверку на связность, то и 50x50.

[shale]

И отдельное спасибо за книжку.