Составляем кроссворды

Разгребал старые книги в шкафу. Нашел экземпляр Чарльза Уэзерелла «Этюды для программистов». 1982 г, друзья! Одна из задач мне понравилась настолько, что я решил её запрограммировать в свободное время.

Называется она «Крисс-Кросс или эвристическое составление головоломки». Автор позаимствовал этюд из еще более древней книжки — Армбрастера Ф. «Компьютерные кроссворды», 1974 г.

Кроссворд  по вашим словам

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

Кроме кроссворда, где нужно угадывать слова, есть, оказывается, более простая задача — крисс-кросс. Тут слова угадывать не надо, так как список слов сразу дан и нужно заполнить им заданную сетку. А сетку как раз и рисует программа.

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

Кроме поиска решения, эта задача предполагает оптимизацию решения. Я поиграл с разными вариантами, остановившись на таком критерии — наиболее оптимальным считается решение с большим числом перекрестий и/или меньшей площадью.

Я вывожу не более пяти найденных компоновок кроссвордов. Поиск ограничен во времени, т.к. выполняется на стороне сервера.