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

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

Затык происходит в том месте, что если мы ставим два слова вертикально рядом, то не факт, что у нас по горизонтали окажутся действующие слова, это же по всем горизонталям наших слов они должны оказаться... в общем, голова кругом, не могу придумать адекватного решения. Может подскажете хоть что-то?

Закрадывалась идея - может снять шаблон с готового сканворда, закинуть в прогу-генератор и пусть она под шаблон перебирает до потери пульса? Но идиотство, скорее всего, у такого шаблона единственное решение. Оно его и найдёт через несколько часов/дней.

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

Но как организовать такой перебор. Тут нужен какой-то интеллектуальный алгоритм. Вот примеры таких сканвордов: 
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

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

Именно так - перебор с откатами.