Но таки да, хотя бы в два раза вычисления можно сократить, тут я совсем поленился. Чтобы не рассматривать ветки, начинающиеся, скажем, ходом (1,1) -> (3,2), клетку (3,2) надо удалить из начальной области, а чтобы в ней заканчивать — сделать ее целевой.
Тогда ожидаемо находится в два раза меньше вариантов за вдвое меньшее время.
Т.е у 7х6 всего в 4 раза больше циклов, чем у 6х6? Хм, что-то у меня уже пятый день лопатит и закончить не может. Да уж, нетороплив.
А для 8х8, если верить википедии, количество циклов составляет 13 триллионов, а незамкнутых маршрутов еще на три порядка больше. В лоб не подсчитаешь.
Я тоже вначале думал делить пополам, но потом понял, что это не учитывает симметрию и количество геометрически различных циклов так не подсчитаешь. А Хаскель удобен для экспериментов. Из-за компактности кода идеи проверяются быстро. Да и в первой статье я писал, что плясал от языка, я его изучаю для общего развития, как, можно сказать, локомотива функциональной парадигмы.
Интересная идея. В принципе реализовать несложно. Надо отсортировать список возможных ходов по определенному признаку. А сложность сортировки даже меньше квадрата
Тогда ожидаемо находится в два раза меньше вариантов за вдвое меньшее время.
А для 8х8, если верить википедии, количество циклов составляет 13 триллионов, а незамкнутых маршрутов еще на три порядка больше. В лоб не подсчитаешь.