Построение поля для кроссворда

#c++ #алгоритм

Не могу придумать алгоритм. У нас есть список слов, не важно какой длины. Необходимо
построить поле для кроссворда при участии данных слов. Данная задача есть в книге "Этюды
программирования".

На данный момент мои рассуждения такие:


отсортировать слова по количеству букв
представить данное поле как двумерный char-массив
в центр поля поместить самое длинное слово и начать работать от него
слова должны читаться строго слева на право и сверху вниз


Как именно вставлять слова, да так чтобы одно слово могло не просто пересекаться
с другим, а с несколькими?

UPD

Посмотрел на кроссворды и понял, что количество вертикальных и горизонтальных слов
всегда пропорционально, плюс/минус одно-два. Значит, необходимо реализовать две функции
- одну для горизонтальных, другую для вертикальных. И вызывать их друг за другом через
рекурсию пока не будут использованы все слова.

UPD 
(прошу прощения за качество изображения, рисовал в гимпе быстро)



Необходимо ввести такое понятие как красная зона, чтобы не было "слипания" слов.

UPD

Нашел статью http://habrahabr.ru/post/166471/, прочтение исходного кода ничего не дало.

UPD

Еще одна зацепка найдена. Книга : Мозговой М.В. "C++ Мастер класс 85 нетривиальных
проектов, решений и задач". Есть способ реализации построения кроссворда, только он
завязан на том что у нас уже дана определенная сетка и достаточной большой список слов,
который не будет использоваться весь.
    

Ответы

Ответ 1

У меня есть некоторая идея алгоритма, но скорее всего она не самая оптимальная.  


Сортируем базу слов, чтобы самые длинные располагались в начале;  
Создаем двумерный символьный массив размерностью N x N, где N можно взять в 1.5 -
2 раза больше, чем самое длинное слово из имеющегося списка;  
По горизонатли в середину массива помещаем самое длинное слово;  
Выбираем следующие по длине слово, у которого хоть 1 буква совпадает с первым, и
размещаем его в нужном месте по вертикали;  
Далее реализуем цикл, пока не выберем все слова из нашей базы, или не завершатся
возможные позиции для добавления слов:  


Поочередно выбираем, добавляем ли мы новое слово по вертикали, или
по горизонтали;   
Проходим по строкам, или столбцам массива, через 1 (так обеспечим отсутствие "слипания"
слов, если добавляем по горизонтали, двигаемся по строкам, иначе - по столбцам), ищем
стоки/столбцы, в которых присутствуют обрамленные пустыми ячейками единичные символы,
сохраняем эти символы и размер промежутков между ними в элемент некоторого списка,
  например, из комбинации строк:

.гиппопотам. 
.  
.  
.    
.пароход.  
.   
.комод.  


Можно было бы составить вот такие элементы списка: г-3-п-1-к, п-3-р-1-м, о-3-х-1-д,
о-3-д, и т.д. (Как именно формировать такие элементы списка, чтобы их потом было удобно
разбирать - отдельный вопрос, можно формировать регулярное выражение, а может даже
лучше не переносить сами буквы из массива, а добавлять в список структуру вида  

{   
    направление(гориз./верт.);   
    количество букв;    
    номер строки начала;   
    номер столбца начала;   
}


И сопоставлять со словами буквы из массива по заданной в этой структуре позиции).
Список формируем по убыванию количества букв в сформированных элементах.  
Проходим по базе слов, выбирая поочередно начиная с самых длинных, и сопоставляем
с элементами в списке, пока не найдем слово, буквы и их положение в котором совпадают
с элементом из сформированного нами на предыдущем шаге списка.   
Размещаем найденное слово в нужной позиции в массиве, если его размер позволяет и
оно не перекрывает какое-то другое слово в той же строке (иначе, продолжаем проход
по базе), исключаем его из базы, возвращаемся в начало цикла.  
Если слов не осталось, или ни одного совпадения не нашлось (даже с 1 буквой) ни при
вертикальном добавлении, ни при горизонтальном, значит все что могли мы построили,
выходим из цикла.   



UPD:
Пример для добавления слова, пересекающегося с двумя по вертикали:  

.........
..г...ф..  
..р...а..  
..а...в..
..ф...н..


передвигаясь по строкам через одну, мы можем составить элементы списка р-3-а, ф-3-н
для этих двух слов, если мы будем использовать в качестве элемента списка вышеописанную
структуру, то для строки номер 3 мы получим :
направление - горизонталь
количество букв - 2
номер строки начала - 2 (если учесть привычный отсчет в массиве с 0)
номер столбца начала - 2  

Пройдя по базе, мы обнаружили, что под первый элемент списка подходит слово "трубка",
мы знаем смещение первой совпавшей буквы в массиве - (строка 2, столбец 2), значит
можем высчитать и положение первой буквы найденного нами слова, и поместить его в массив
(строка 2, столбец 1).


Ответ 2

Почитайте эти статьи:


«Алгоритм формирования кроссвордов»,
«Построение кроссвордов с помощью языка Wolfram Language (Mathematica)».


Вкратце, составление кроссвордов — нетривиальная задача, требующая большой базы слов.
При этом нет никаких гарантий, что все слова получится уложить в сетку.

Добавлено. Красная зона легко реализуется добавлением пробелов в начало и конец каждого
слова.