Тестирование проводилось на базе из 155 136 слов на процессоре Intel(R) Core(TM) i5-3210M 2.50GHz.

Для систематизации сеток по сложности генерации введен атрибут «Сложность генерации», который рассчитывается на основании количества слов, их длины и количества пересечений. По факту — более менее стабильно результат можно получать при сложности до 600 единиц. Все что выше — на удачу.

Ниже показано среднее время генерации на 10 попытках для нескольких сеток, расположенных в порядке возрастания сложности генерации.

Сетка № 1

Несложная тестовая сетка для опытов, с небольшим количеством слов.

Подитог: Сетки такой сложности генерируются быстро и стабильно.

Сетка № 2

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

Подитог: Сетки такой сложности в большинстве случаев генерируются довольно быстро, однако, иногда генерация может затянуться на 10 минут и более.

Сетка № 3

Эта довольно сложная сетка оказалась весьма "удобной" для генерации.

Подитог: Благодаря тому что эта сетка очень хорошо фрагментируется и пересечения имеются не на всех буквах длинных слов, программа генерирует его почти мгновенно.

Сетка № 4

А вот эта сетка уже имеет «целевую» сложность. Это полноценный «канадский» кроссворд, правда, далеко не самый сложный.

Подитог: Программа справилась! Успешный результат генерации, в самом крайнем случае, можно получить всего за 17 минут. Среднее время генерации чуть более 4 минут.

Сетка № 5

И, наконец – тот, самый сложный кроссворд, с которого все началось. В нем 72 слова, что не так уж и много. Однако, сложность генерации получилась очень высокой. Основной проблемой для генерации являются четыре самых длинных слова, с которыми пересекаются почти все остальные слова кроссворда. Они как кости скелета, на которые нужно нанизать все остальные слова. Откаты отбрасывает процесс генерации почти на самое начало. Таким образом, процесс генерации этой сетки можно сравнить с Сизифом, толкающим камень в гору. И каждый раз, когда до цели остается совсем немного, камень скатывается к самому началу пути.

Увы – эта вершина осталась непокоренной! Я запускал несколько генераций с разными настройками, с лимитом по длительности до 10 часов, однако ни одна из них не была завершена успешно. Времени явно не хватает. Кто знает, может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!

Резюме

И все-таки да! Генерация кроссворда, даже для самых современных компьютеров, является сложной задачей. Я уверен, что возможности улучшить этот алгоритм далеко не исчерпаны, однако, независимо от возможностей алгоритма и мощности компьютера, всегда можно усложнить сетку кроссворда еще чуть-чуть, чтобы программа пообещала Вам результат, лет, через 20-30…

При желании самим попробовать генератор кроссвордов, Вы можете скачать его на этой странице.

Обсуждение алгоритма и дополнительную информацию, Вы можете найти на Хабрахабре.