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

Инструментовка. К решению задачи имеется много подходов, но в любом случае нужны гибкие структуры данных, чтобы отслеживать продвижение программы, и средства для удобной работы с цепочками литер и образцами. Напрашиваются языки Снобол и 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.

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

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

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

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

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