Атомов как составляющих клозов.
Сами клозы будут иметь вид «если в клетке стоит такая-то буква, то допустимы только слова, имеющие эту букву в соответствующей позиции», а так же «в одной клетке не может стоять две разные буквы».
Так как данная задача явно в NP, то, конечное ее можно свести к SAT. Давайте попробуем оценить его размеры.
Пусть переменная xi,j — слово номер i из словаря стоит на месте слова j из кроссворда. С учетом, того что имеет смысл рассматривать только слова подходящей длины, для последнего кроссворда у меня получилось 536 тысяч таких переменных. Кроме того, что бы не плодить сложных дизъюнктов, то для каждого квадрата, стоящего на пересечении двух слов введем переменную yi,c — в квадрате номер i стоит буква с. Это еще 6 тысяч переменных.
При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
В целом, получилась задача, которую в случае «везения» могут решить современные SAT-солверы. Но, к сожалению, могут и не решить. В любом случае, ста строчками кода там дело не обойдется.
Если не повезло — то непредсказуемо долго. Оценка 1 из 20 запуска получена с лимитом времени пару минут (ждать дольше не хватало терпения).
Фактически, это стратегия «если быстро не нашел, рандомизируй и ищи снова». В общем случае ее рекомендовать нельзя, но в этом, из-за специфики задачи — работает.
Хотя бы один смысл я знаю только у 26 слов из этого кроссворда (40%). Так что шансов разгадать — никаких. Можно попробовать взять менее суровый словарь, но я не знаю где.
Сами клозы будут иметь вид «если в клетке стоит такая-то буква, то допустимы только слова, имеющие эту букву в соответствующей позиции», а так же «в одной клетке не может стоять две разные буквы».
Пусть переменная xi,j — слово номер i из словаря стоит на месте слова j из кроссворда. С учетом, того что имеет смысл рассматривать только слова подходящей длины, для последнего кроссворда у меня получилось 536 тысяч таких переменных. Кроме того, что бы не плодить сложных дизъюнктов, то для каждого квадрата, стоящего на пересечении двух слов введем переменную yi,c — в квадрате номер i стоит буква с. Это еще 6 тысяч переменных.
При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
В целом, получилась задача, которую в случае «везения» могут решить современные SAT-солверы. Но, к сожалению, могут и не решить. В любом случае, ста строчками кода там дело не обойдется.
Фактически, это стратегия «если быстро не нашел, рандомизируй и ищи снова». В общем случае ее рекомендовать нельзя, но в этом, из-за специфики задачи — работает.
used):Результат:
амака агто капп набор крец авиа икела кеке турн налогообложение акарид неле алате алпари клод тучи ортер лесопереработка уриил асоп туан гептод адало цикл чапура тирокальцитонин элен кущи олита тьма игин нитон афар некк атара