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

[singalen]

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

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

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

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

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

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

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