| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Как генерировать сканворды? |
| Автор: Proger10 19.12.2016, 02:27 |
| Стоит задача: сгенерировать сканворд, который полностью заполнен словами и заданиями. Как можно это сделать? Ломаю голову несколько дней и так, и сяк, но кроме тупого перебора ничего не приходит. Перебор - до тех пор пока случайно не разместятся нужные слова на нужных позициях с нужными стрелками (следующими от заданий). Но нужно тут подключать какую-то логику, чтобы удалять мешающие слова, пробовать добавлять новые и т.д. Затык происходит в том месте, что если мы ставим два слова вертикально рядом, то не факт, что у нас по горизонтали окажутся действующие слова, это же по всем горизонталям наших слов они должны оказаться... в общем, голова кругом, не могу придумать адекватного решения. Может подскажете хоть что-то? |
| Автор: Proger10 19.12.2016, 03:03 |
| Закрадывалась идея - может снять шаблон с готового сканворда, закинуть в прогу-генератор и пусть она под шаблон перебирает до потери пульса? Но идиотство, скорее всего, у такого шаблона единственное решение. Оно его и найдёт через несколько часов/дней. |
| Автор: Akina 19.12.2016, 07:48 |
| Именно так - перебором. Имеется БД со словами и их определениями (возможно, несколько альтернативных к одному слову), и заполнение ведётся обычным подбором. Из оптимизации возможно разве что создание индекса расположения пар букв (для троек уж больно будет дофига), и после добавления очередного слова скан на отсутствие несуществующих пар. |
| Автор: Proger10 19.12.2016, 23:58 |
| Но как организовать такой перебор. Тут нужен какой-то интеллектуальный алгоритм. Вот примеры таких сканвордов: http://30r.biz/images/st/gol/sk/20x30/01/b/Skanvord-20x30-n-24.1-Klon-b.jpg http://30r.biz/images/st/gol/sk/20x30/01/b/Skanvord-20x30-n-42-Gorozhanin-b.jpg http://30r.biz/images/st/gol/sk/20x30/01/b/Skanvord-20x30-n-46-Vakuum-b.jpg Это жесть, честно говоря. Ума не приложу как это можно сделать. В голове обрывочно вырисовывается что-то типа перебора с откатом до определённого шага, чтобы отменить последующие результаты когда зашли в тупик и продолжить ещё раз. |
| Автор: Akina 20.12.2016, 07:50 |
| Именно так - перебор с откатами. |