Задачка: петли на решётке (оптимистично звучит, правда?)

[singalen]

Есть у меня задача. Кажется простой, но в подробности можно углупляться долго.

Подсчитать количество разных, несамопересекающихся, неизоморфных петель на квадратной решётке.
Дана длина петли N.

Для N=4 ответ - 1:
 _
|_|

Для 6 - 2:
 __
|__|
 _
| |
|_|

Для 8 - 7.
и те де.

Я пока решаю жёстко заоптимизированным перебором. Время расчёта растёт экспоненциально по N с коэффициентом 6. Но такое счастье нам не надо.

Кто придумает хотя бы идею лучшего решения - с меня пиво. Если это будет работающий код - пива будет много :)

Comments

[profuel.livejournal.com]

круто, вот и узнали настоящее название задачи :)

[singalen]

Ну, я её назвал примерно так же.

[profuel.livejournal.com]

а формулу нашел?
так как я кроме данных о кол-вах для размер до 55 (*2) так и не нашел.

[singalen]

Неа. Думаю, там тот же оптимизированный перебор.