coolwolf0 - Северный наблюдатель (coolwolf0) wrote,
coolwolf0 - Северный наблюдатель
coolwolf0

Программируя "для дома, для семьи"

Поскольку FreeRSS официально поставлен на полку и не получит в ближайшее время никаких изменений, решил я осуществить давно запланированную затею: переписать генератор судоку с Перла на Пайтон. Заодно планировалось улучшить алгоритм генерации и сочинить новую оценочную функцию. Что же получилось?

Основная алгоритмическая часть была написана буквально за пару вечеров. Из имеющихся в сети примеров я выбрал три самых "крутых", поигрался с ними и понял, что использовать оттуда ничего нельзя. Один пример базировался на какой-то экзотической Сишной библиотеке, которая на обычную виндузовую персоналку не ставилась ни в какую. Второй пример был функционально неполным, то есть поле генерировал, но головоломку не делал. Третий пример реализовывал мой старый алгоритм, уже плохо себя зарекомендовавший в Перл-версии.

В результате было решено воплотить следующий алгоритм: начинаем с корректно заполненного случайным образом поля; на каждом шаге освобождаем по одной ячейке при условии, что новое состояние заведомо приведёт к однозначному решению. Для этого пришлось реализовать алгоритм повторяющий стратегию человека, то есть поиск возможного хода путём применения трёх стандартных приёмов (заполнение последнего недостающего числа, поиск единственного варианта постановки в под-квардратах и поиск "исключительной" позиции, когда на это место другое число просто невозможно поставить). Если последовательное применение этих эвристик приводит к решению, значит можно двигаться дальше. В противном случае освобождается другая ячейка. Если все варианты дают отрицательный результат приходится делать полный бектрекинг, то есть разыгрывать матрицу с начала. Возможно я перемудрил с повторением "человеческой" стратегии, ибо судоку на математическом уровне решается путём анализа подмножеств, но практика показала, что результат вполне себя оправдал.

В результате я дошёл до знаменитого пародокса "может ли бог сотворить камень, который не сможет приподнять?", то есть программа генерирует столь сложные судоку, что мне самому приходится ломать голову, как же их решить (и это при том, что решение "человеческим" способом гарантированно есть). А ведь у судоку есть ещё несколько дополнительных уровней сложности: неоднозначность последней позиции и исключение вариантов на основании опосредованной трассировки строк/столбцов. Если применить хоть один из них, то головоломки станут совсем зубодробительными.

Между прочим, поддавшись атмосфере фабричной штамповки программ у нас на работе, я даже сподобился оформить основную часть в виде класса, и даже накатал 18 (sic!) юнит-тестов. Как ни странно, один из них нашёл реальный баг!

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 4 comments