Доброго всем времени суток!!! 

До учебы еще целый месяц, делать нечего. Поэтому учу С++ по книге Дейтела. А в ней в разряде "головоломные" раздела на строки предложена задача на генерацию кроссворда (заполненный словами, желательно симметричный) Ну, очевидное решение у меня есть - простой backtracking. Но, по-моему, очень (!) это неэффективно. В сети исходников нет (вроде искал хорошо), но есть куча готовых программ. Может кто, грешным делом, занимался этой проблемой? Подскажите хотя бы идею 

Заранее спасибо   

Уважаемые форумчане! Я конечно понимаю, что спасение утопающих - дело рук самих утопающих. Но неужели мой вопрос окажется неуслышенным?

Я не понял - речь о генерации сетки, заполнении готовой сетки, both?

Akina, 

Генерация готовой сетки по словарю (т.е. both)

как я понял в условии задачи, входные параметры = это только размер кроссворда,  а дальше генерится заполненная сетка со словами

Я, пожалуй, сделал бы следующую вариацию бэктрекинга.

Сначала, создаем базу данных с таблицей, содержащей поля: слово, длина слова, 1-я буква, 2-я буква, ...., 20-я буква. По всем полям  создаем индексы для быстрого поиска.
Запросы типа "найти все слова длины 6 где 2-я буква=А и 5-я буква=Ц" должны выполняться весьма быстро.
Таблица одна, скорее всего целитком влезет в память, поэтому полноценную СУБД задействовать, возможно, особого смысла нет и можно ограничиться самодельной программной реализацией.

Затем генерируем сетку нужной формы и пытаемся ее заполнять (обычный бэктрекинг). Думаю, что для типичных кроссвордов и со словарем в несколько тысяч слов время генерации таким методом будет вполне приемлемым.

В случае, когда словарь мал, алгоритм может сильно зависеть от того, насколько он мал и каковы требования к размеру и форме кроссворда. В грубом варианте, можно перебирать размещения слов на сетке в допустимых границах (действительно тяжелый перебор).

nostromo, 
Во-первых, спасибо за ответ и за участие (к сожалению, пока 100 постов нет  , но я запомню )
во-вторых, получается, что оптимальным вариантом является сначала генерация сетки, а потом ее заполнение? 
Совместить эти процессы никак не получится? или это нерационально?
Тем более если словарь не очень большой

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

Вроде бы, нашел толковый вариант