"Ход конем" на python

Когда-то давно, когда компьютеры еще не были так распространены, а единственным устройством способным помочь в расчетах был программируемый калькулятор типа Электроника MK-52/54 (http://ru.wikipedia.org/wiki/Электроника_МК-52, http://rk86.com/frolov/mk-54.htm), в школе мы играли в игру "Ход конем".


Правила игры: Необходимо обойти доску по правилу перемещения шахматного коня с попаданием в каждое поле по одному разу. Начинать можно с любого поля. Возвращаться в начало, то есть совершать обход по замкнутому маршруту, не обязательно.

Естественно вариантов решения данной задачи огромное множество, а перебирать все возможные варианты на мой взгляд было как-то не серьезно. Уже тогда мне было интересно написать программу, которая бы сделала просчет всех возможных вариантов решений. Но писать подобную программу для калькулятора понятное дело было затруднительным, поэтому идея была отложена и как оказалось в долгий ящик. Спустя годы, перебирая старые записи я наткнулся на наброски решения игры "ход конем."

Выкроив пару часов, я воплотил в жизнь давнюю идею, написав на python решение задачи. Скрипт horse_step.py. Как исходные данные скрипт принимает простой текстовый файл с картами доски. Пример карты 5 на 5. Далее, для этой карты производится расчет всех возможных комбинаций путей с указанием числа как тупиковых так и правильных решений.

Прямо сейчас (пока я пишу этот пост) закончил выполнятся скрипт для доски 5 на 5:

deadlock path counter: 14898080, ended path counter: 1728

Было найдено почти 15 миллионов тупиковых путей и 1728 решений, для которых все поля доски пройдены согласно правилам.

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

- использование функций map и filter: для выборки и обработки данных, загрузки карты доски из файла
- lambda с условиями: конструкции вида, lambda x: x in y and x or z

Скрипт horse_step.py доступен на code.google.com. Если можете подсказать более изящные или правильные решения, найдете неточности - я открыт для обсуждения.