Алгоритм генерации кроссворда

Question

Учитывая список слов, как бы вы организовали их в сетку кроссвордов?

Это не должно быть похоже на «правильную» кроссворд, которая является симметричной или что-то в этом роде: просто выведите начальную позицию и направление для каждого слова.

Будут ли доступны какие-либо примеры Java?

Answer 1

Я бы получил индекс каждой буквы, используемой каждым словом, чтобы узнать возможные крестики. Тогда я бы выбрал самое большое слово и использовал его в качестве основы. Выберите следующий большой и пересечь его. Промыть и повторить. Это, вероятно, проблема NP.

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

Трудная часть, которую я нахожу, - это когда невозможно узнать определенный список.

Answer 2

Я кодировал 100% jQuery решение этой проблемы.

Пример демонстрации: http://www.earthfluent.com/crossword-puzzle-demo.html

Исходный код: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

Цель алгоритма, который я использовал:

1. Максимально уменьшите количество неиспользуемых квадратов в сетке.
2. Имейте как можно больше смешанных слов.
3. Вычисление в чрезвычайно быстрое время.

Я опишу алгоритм, который я использовал:

1. Сгруппируйте слова по тем, которые имеют общую букву.

2. Из этих групп построить наборы новой структуры данных («блоки слов»), которая является основным словом (которое проходит через все другие слова), а затем другими словами (которые проходят через основное слово) .

3. Запустите кроссворд с самым первым из этих блоков слов в самой верхней левой части кроссворда.

4. Для остальных блоков слова, начиная с правой нижней части позиции кроссворда, двигайтесь вверх и влево до тех пор, пока не останется больше свободных мест для заполнения. Если пустых столбцов больше, чем влево, двигайтесь вверх и наоборот.