Техногенный дыбр

[coolwolf0]

Что делает программист, когда ему нечего делать? Вытряхивает мусор из клавиатуры? Протирает монитор? Пылесосит системный блок? В принципе так и есть, но помимо этого есть программисты, имеющие чисто профессиональные способы потребления свободного времени. Нет, я не говорю о тяжелом случае из старого советского анекдота "жене сказал, что у любовницы, любовнице - что у жены, а сам работать-работать-работать". Просто моё становление как профессионала тесно связано со всякими побочными компьютерными делами - то программу хакнул, то игру накатал, то библиотеку макросов над ассемблером забацал. Однако, последнее время мне всё как-то не до программирования "для дома, для семьи": дети сами справляются с техникой (дочка - на таблете, сын - на ноутбуке), теща уверенно гоняет всякие карты-шарики-кубики и подводит месячный баланс в экселе, жена смотрит в онлайне фильмы и фейсбучится с подружками, короче - все пристроены. Вот и решил я уделить немного времени своему собственному досугу.Дело в том, что замечательная андроидная программа OpenSudoku имеет ограниченный набор игр (включая публично доступные в сети). И задался я целью самостоятельно накатать программу, которая генерирует судоку заданной сложности в формате этого приложения (фактически - XML). Основная проблема тут - добиться строго определенной сложности головоломки. Я прошерстил интернет на предмет алгоритмов генерации - все они абсолютно игнорируют, или принимают "на глазок" сложность полученных результатов. Поэтому пришлось взять первый попавшийся алгоритм на Перле (ну на чем еще можно генерить головоломки?) и пришить к нему свою оценочную функцию. Тут пришлось вспомнить школьную, да и ВУЗовскую математику: оценочная функция должна быть устойчивой ко всяким граничным ситуациям, отражать сложность процесса решения (а не начального положения на доске), и при этом быть достаточно близкой к "человеческому" фактору оценки сложности. Результат оказался двумерным: сначала моя самодельная процедура пытается решить начальную позицию при помощи чисто "человеческих" приемов (исключение одинаковых чисел по строкам-столбцам-квадратам + вычисление уникального числа в каждой свободной клетке). В результате решения обычно остается некоторое число неопределенных ячеек (опытные игроки решают такие позиции методом перебора с откатом) - это первый фактор: чем больше неопределенности, тем сложнее. Второй фактор складывается из числа заполненных ячеек на каждой итерации решения. Чем меньше счетчик решенных ячеек, тем сложнее было найти решение на этом этапе, - значит для человека эта головоломка явно вызовет затруднение. В результате суммирования относительных величин (с инверсией функции) и деления на общее количество ходов, получаем некий процентный фактор сложности всего решения. При генерации "легких" и "средних" головоломок результат получается довольно быстро, а вот для уровня "hard" пришлось даже модифицировать оригинальный алгоритм, чтобы бедная программа не мучилась, перелопачивая горы сгенерированных строк, не попадающих в двумерный интервал сложности. Обернув всю эту математику в простой интерфейс командной строки я получил генератор, выдающий набор головоломок заданной сложности в формате opensudoku. Результаты выложены на моем сайте в папке 'sudoku' - кто знает меня IRL, заходите на сайт и скачивайте на здоровье.