Этюды для программистов

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

Указания исполнителю. Качество схем крисс-кросса пропорционально их «связанности», т. е., чем теснее в среднем слова переплетены с соседями, тем интереснее головоломка. Связанность можно измерять по-разному: как отношение площади схемы к площади наименьшего объемлющего прямоугольника; как среднее число пересечений на слово; как среднее число пересечений на букву; как минимальное число пересечений на слово. При генерации головоломок крисс-кросс для массовых изданий использовалась коммерческая программа, но головоломки получались неинтересные — слишком длинные и извилистые. Когда ваша программа заработает, позаботьтесь об увеличении связанности.

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

Инструментовка. К решению задачи имеется много подходов, но в любом случае нужны гибкие структуры данных, чтобы отслеживать продвижение программы, и средства для удобной работы с цепочками литер и образцами. Напрашиваются языки Снобол и PL/I. В Паскале есть подходящие структуры данных, но средства для работы с цепочками придется создавать самому.

Длительность исполнения. Одному исполнителю на 4 недели. Еще неделя на графический вывод.

Литература

Армбрастер (Armbruster F.). Computer Crosswords, Troubadour Press, San Francisco, CA, 1974.

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

Мазлак (Mazlack L. J.). Machine Selection of Elements in Crossword Puzzles: An Application of Computational Linguistics. SIAM J. Comput., 5, 1, pp. 51–72, March 1976.

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

8 Тезей, или Автоматическое построение лабиринтов

Тезей должен был найти выход из Критского лабиринта или погибнуть от руки Минотавра. Но что поразительно: найти вход в лабиринт — задача не менее трудная.

Здесь не представляется возможным описать все мыслимые лабиринты, да это и не требуется. Мы займемся простыми лабиринтами, построенными на прямоугольнике m×n, где m, n — положительные целые числа. Внутри и на границах прямоугольника поставлены стенки по ребрам покрывающей его единичной квадратной сетки. Чтобы построить из прямоугольника лабиринт, выбьем одну единичную стенку на одной из сторон прямоугольника (получится вход в лабиринт); выбьем одну единичную стенку на противоположной стороне (получится выход) и еще удалим какое-то число строго внутренних стенок. Говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде ломаной, не имеющей общих точек со стенками. Решение единственно, если любые два таких пути проходят через одни и те же внутренние ячейки сетки. На рис. 8.1 приведен пример лабиринта 6×6.

Рисунок 8.1. Пример лабиринта.

Тема. Напишите программу, которая по исходным данным m и n строит прямоугольный лабиринт m×n (проверьте, допустимы ли заданные m и n). Предусмотрите, чтобы программа при каждом обращении к ней порождала разные лабиринты. Лабиринт должен иметь единственное решение, и, чтобы получившийся лабиринт был интересным, все ячейки должны быть соединены с основным путем, дающим решение. Если в вашем распоряжении имеется хорошее графическое устройство, используйте его для изображения лабиринтов, в противном случае придумайте систему обозначений для записи лабиринтов или выводите лабиринты на АЦПУ.