Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
радиопередатчик, антидепрессанты, присовокупление — прекрасно!
если по делу: у вас слово «облака» используется дважды, надо бы как-то это пофиксить, мне кажется )
а вообще было интересно, спасибо
если по делу: у вас слово «облака» используется дважды, надо бы как-то это пофиксить, мне кажется )
а вообще было интересно, спасибо
Нет проблем: заодно протянем в рекурсию множество использованных слов (
Результат:
used):def search(masks: Map[Word, String], assignment: Map[Word, String], used: Set[String]) {
...
for (variant <- cache(mask); if !used(variant)) {
...
search(newVariants, assignment.updated(word, variant), used + variant)
}
}
// Исходный вызов
search(words.map(w => (w, "?" * w.letters.length)).toMap, Map.empty, Set.empty)
Результат:
амака агто капп
набор крец авиа
икела кеке турн
налогообложение
акарид неле
алате алпари
клод тучи ортер
лесопереработка
уриил асоп туан
гептод адало
цикл чапура
тирокальцитонин
элен кущи олита
тьма игин нитон
афар некк атара
Интересно, существует такой человек, который честно, без заглядываний в словарь, знает значения всех этих слов?
акаст ахум ахум
лагер алоа лара
анами рокк ерма
Читая, я подумал, что это заклинание вызова дьявола, и только радиопередатчик вернул меня в действительность и помог понять, что это всё-таки реальные слова на русском языке.
ахум тоже дважды. Давайте исправляйте )
По-моему, автор изобретает велосипед.
Это типичная задача SAT.
Это типичная задача SAT.
Так как данная задача явно в NP, то, конечное ее можно свести к SAT. Давайте попробуем оценить его размеры.
Пусть переменная xi,j — слово номер i из словаря стоит на месте слова j из кроссворда. С учетом, того что имеет смысл рассматривать только слова подходящей длины, для последнего кроссворда у меня получилось 536 тысяч таких переменных. Кроме того, что бы не плодить сложных дизъюнктов, то для каждого квадрата, стоящего на пересечении двух слов введем переменную yi,c — в квадрате номер i стоит буква с. Это еще 6 тысяч переменных.
При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
В целом, получилась задача, которую в случае «везения» могут решить современные SAT-солверы. Но, к сожалению, могут и не решить. В любом случае, ста строчками кода там дело не обойдется.
Пусть переменная xi,j — слово номер i из словаря стоит на месте слова j из кроссворда. С учетом, того что имеет смысл рассматривать только слова подходящей длины, для последнего кроссворда у меня получилось 536 тысяч таких переменных. Кроме того, что бы не плодить сложных дизъюнктов, то для каждого квадрата, стоящего на пересечении двух слов введем переменную yi,c — в квадрате номер i стоит буква с. Это еще 6 тысяч переменных.
При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
В целом, получилась задача, которую в случае «везения» могут решить современные SAT-солверы. Но, к сожалению, могут и не решить. В любом случае, ста строчками кода там дело не обойдется.
> При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
Откуда такое число?
(Атомов в смысле клозов ?)
Откуда такое число?
(Атомов в смысле клозов ?)
повезло с random-омом, кроссворд быстро генерируется где-то в одном из 20 случаев
А если не повезло, то сколько работает?
Если не повезло — то непредсказуемо долго. Оценка 1 из 20 запуска получена с лимитом времени пару минут (ждать дольше не хватало терпения).
Фактически, это стратегия «если быстро не нашел, рандомизируй и ищи снова». В общем случае ее рекомендовать нельзя, но в этом, из-за специфики задачи — работает.
Фактически, это стратегия «если быстро не нашел, рандомизируй и ищи снова». В общем случае ее рекомендовать нельзя, но в этом, из-за специфики задачи — работает.
А вот 5x5 квадрат (10 слов по 5 букв со всеми пересечениями) ваша программа сможет посчитать и за сколько?
У меня с помощью SAT за несколько секунд считается.
У меня с помощью SAT за несколько секунд считается.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О переборе на примере генерации кроссвордов