О переборе на примере генерации кроссвордов

[gcooler]

радиопередатчик, антидепрессанты, присовокупление — прекрасно!
если по делу: у вас слово «облака» используется дважды, надо бы как-то это пофиксить, мне кажется )
а вообще было интересно, спасибо

[StupidSolver]

Нет проблем: заодно протянем в рекурсию множество использованных слов (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)

Результат:

амака агто капп 
набор крец авиа 
икела кеке турн 
налогообложение 
акарид неле     
   алате алпари 
клод тучи ортер 
лесопереработка 
уриил асоп туан 
гептод адало    
    цикл чапура 
тирокальцитонин 
элен кущи олита 
тьма игин нитон 
афар некк атара 

[mapron]

В верхнем правом углу: авун, пири, пане — это точно русские нарицательные? я таких слов нагуглить не могу. 11,12,13 по вертикали.
Откуда базу брали слов?
авун — молитва,
пири, роберт.
Пане, Армейн.
Да, если не ограничиваться нарицательными (кроссворд же), то все в порядке. Извините.

[mapron]

Ай, невнимательный я. Еще раз извините, про базу все понятно.

[mapron]

del

[AndrewN]

Интересно, существует такой человек, который честно, без заглядываний в словарь, знает значения всех этих слов?

[StupidSolver]

Хотя бы один смысл я знаю только у 26 слов из этого кроссворда (40%). Так что шансов разгадать — никаких. Можно попробовать взять менее суровый словарь, но я не знаю где.

[Starche]

акаст ахум ахум
лагер алоа лара
анами рокк ерма

Читая, я подумал, что это заклинание вызова дьявола, и только радиопередатчик вернул меня в действительность и помог понять, что это всё-таки реальные слова на русском языке.

[Scratch]

ахум тоже дважды. Давайте исправляйте )

[Scratch]

уже увидел выше что переделали

[andy_p]

По-моему, автор изобретает велосипед.
Это типичная задача SAT.

[StupidSolver]

Так как данная задача явно в NP, то, конечное ее можно свести к SAT. Давайте попробуем оценить его размеры.
Пусть переменная x_i,j — слово номер i из словаря стоит на месте слова j из кроссворда. С учетом, того что имеет смысл рассматривать только слова подходящей длины, для последнего кроссворда у меня получилось 536 тысяч таких переменных. Кроме того, что бы не плодить сложных дизъюнктов, то для каждого квадрата, стоящего на пересечении двух слов введем переменную y_i,c — в квадрате номер i стоит буква с. Это еще 6 тысяч переменных.
При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.
В целом, получилась задача, которую в случае «везения» могут решить современные SAT-солверы. Но, к сожалению, могут и не решить. В любом случае, ста строчками кода там дело не обойдется.

[andy_p]

> При таком кодировании, число атомов в формуле будет примерно равно удвоенной суммарной длине слов, то есть около 2.8 миллионов.

Откуда такое число?
(Атомов в смысле клозов ?)

[StupidSolver]

Атомов как составляющих клозов.
Сами клозы будут иметь вид «если в клетке стоит такая-то буква, то допустимы только слова, имеющие эту букву в соответствующей позиции», а так же «в одной клетке не может стоять две разные буквы».

[andy_p]

«в одной клетке не может стоять две разные буквы»
можно заменить на «хотя бы одна буква» — это один клоз для клетки.

2.8 миллиона никак не получится.

[ENargit]

повезло с random-омом, кроссворд быстро генерируется где-то в одном из 20 случаев

А если не повезло, то сколько работает?

[StupidSolver]

Если не повезло — то непредсказуемо долго. Оценка 1 из 20 запуска получена с лимитом времени пару минут (ждать дольше не хватало терпения).
Фактически, это стратегия «если быстро не нашел, рандомизируй и ищи снова». В общем случае ее рекомендовать нельзя, но в этом, из-за специфики задачи — работает.

[andy_p]

А вот 5x5 квадрат (10 слов по 5 букв со всеми пересечениями) ваша программа сможет посчитать и за сколько?
У меня с помощью SAT за несколько секунд считается.