|
|
|
Proger10 |
|
|||
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 16.12.2008 Репутация: нет Всего: нет |
Стоит задача: сгенерировать сканворд, который полностью заполнен словами и заданиями. Как можно это сделать? Ломаю голову несколько дней и так, и сяк, но кроме тупого перебора ничего не приходит. Перебор - до тех пор пока случайно не разместятся нужные слова на нужных позициях с нужными стрелками (следующими от заданий).
Но нужно тут подключать какую-то логику, чтобы удалять мешающие слова, пробовать добавлять новые и т.д. Затык происходит в том месте, что если мы ставим два слова вертикально рядом, то не факт, что у нас по горизонтали окажутся действующие слова, это же по всем горизонталям наших слов они должны оказаться... в общем, голова кругом, не могу придумать адекватного решения. Может подскажете хоть что-то? |
|||
|
||||
Proger10 |
|
|||
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 16.12.2008 Репутация: нет Всего: нет |
Закрадывалась идея - может снять шаблон с готового сканворда, закинуть в прогу-генератор и пусть она под шаблон перебирает до потери пульса? Но идиотство, скорее всего, у такого шаблона единственное решение. Оно его и найдёт через несколько часов/дней.
|
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Именно так - перебором. Имеется БД со словами и их определениями (возможно, несколько альтернативных к одному слову), и заполнение ведётся обычным подбором. Из оптимизации возможно разве что создание индекса расположения пар букв (для троек уж больно будет дофига), и после добавления очередного слова скан на отсутствие несуществующих пар.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Proger10 |
|
|||
Опытный Профиль Группа: Участник Сообщений: 312 Регистрация: 16.12.2008 Репутация: нет Всего: нет |
Но как организовать такой перебор. Тут нужен какой-то интеллектуальный алгоритм. Вот примеры таких сканвордов:
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 Это жесть, честно говоря. Ума не приложу как это можно сделать. В голове обрывочно вырисовывается что-то типа перебора с откатом до определённого шага, чтобы отменить последующие результаты когда зашли в тупик и продолжить ещё раз. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Именно так - перебор с откатами.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |