Как генерировать сканворды?

 
0
 
Algorithmen
ava
Proger10 | 19.12.2016, 02:27
Стоит задача: сгенерировать сканворд, который полностью заполнен словами и заданиями. Как можно это сделать? Ломаю голову несколько дней и так, и сяк, но кроме тупого перебора ничего не приходит. Перебор - до тех пор пока случайно не разместятся нужные слова на нужных позициях с нужными стрелками (следующими от заданий).

Но нужно тут подключать какую-то логику, чтобы удалять мешающие слова, пробовать добавлять новые и т.д.

Затык происходит в том месте, что если мы ставим два слова вертикально рядом, то не факт, что у нас по горизонтали окажутся действующие слова, это же по всем горизонталям наших слов они должны оказаться... в общем, голова кругом, не могу придумать адекватного решения. Может подскажете хоть что-то?
Kommentare (4)
ava
Proger10 | 19.12.2016, 03:03 #
Закрадывалась идея - может снять шаблон с готового сканворда, закинуть в прогу-генератор и пусть она под шаблон перебирает до потери пульса? Но идиотство, скорее всего, у такого шаблона единственное решение. Оно его и найдёт через несколько часов/дней.
ava
Akina | 19.12.2016, 07:48 #
Именно так - перебором. Имеется БД со словами и их определениями (возможно, несколько альтернативных к одному слову), и заполнение ведётся обычным подбором. Из оптимизации возможно разве что создание индекса расположения пар букв (для троек уж больно будет дофига), и после добавления очередного слова скан на отсутствие несуществующих пар.
ava
Proger10 | 19.12.2016, 23:58 #
Но как организовать такой перебор. Тут нужен какой-то интеллектуальный алгоритм. Вот примеры таких сканвордов:
http://30r.biz/images/st/gol/sk/20x30/01/b...24.1-Klon-b.jpg
http://30r.biz/images/st/gol/sk/20x30/01/b...orozhanin-b.jpg
http://30r.biz/images/st/gol/sk/20x30/01/b...46-Vakuum-b.jpg

Это жесть, честно говоря. Ума не приложу как это можно сделать. В голове обрывочно вырисовывается что-то типа перебора с откатом до определённого шага, чтобы отменить последующие результаты когда зашли в тупик и продолжить ещё раз.
ava
Akina | 20.12.2016, 07:50 #
Именно так - перебор с откатами.
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
  Akina   Proger10
advanced
Absenden