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

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

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

  • Музыка и кино

    Музыка Jеаn-Мiсhеl Jаrrе - Wеlсоmе То Тhе Оthеr Sidе (Соnсеrt Frоm Virtuаl Nоtrе-Dаmе) (2021) Коротко: ерунда. Где хиты, где завораживающие…

  • Дыбрики 2021

    Получили с женой вторую дозу вакцины - она на следующий день чувствовала себя не очень (пришлось отменить прогулку в окрестностях стольного града…

  • Такого выпуска рецензий давно не было

    Хотя бы потому, что этот сборник рецензий - супер-юбилейный (сотый, если считать по моим исходникам на компе). Начнём с музыки Темповой рок -…

  • 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 

  • 0 comments