Существует обширная литература по занимательным задачам и их решениям, причем одна из наиболее известных серий книг принадлежит М. Гарднеру [1 — 3]. Среди таких задач весьма интересен класс логических головоломок, которые обычно решаются эвристически, а корректность их решения доказывается средствами математической логики [4, 5], правда, весьма редко с использованием теории конечных автоматов. В настоящей статье демонстрируется программное решение одной из таких головоломок для его визуализации на основе программирования с явным выделением состояний [6]. Эта задача известна как «Задача о преступниках». О ней сообщил от Н.Н. Шамгунов, трехкратный чемпион Урала по программированию [7]. Сформулируем ее.

Задача о преступниках

Суд приговорил десять преступников к наказанию.

  1. Каждый из них будет сидеть в отдельной камере, не имея возможности общаться с остальными заключенными.
  2. Ежедневно утром, начиная с первого дня заключения, одного из них будут отводить в карцер, а вечером того же дня возвращать назад в камеру.
  3. В карцере есть лампочка, которую находящийся в карцере заключенный сможет включать и выключать. Надзиратели должны тщательно следить за тем, чтобы сидящие в карцере не оставляли друг другу никаких посланий. При этом надзиратели сами не будут ни включать, ни выключать лампочку.
  4. Заключение закончится в тот день, когда кто-то из осужденных сообщит надзирателю о том, что каждый из десяти преступников побывал в карцере хотя бы один раз. Если это окажется правдой, то все десять преступников будут отпущены на свободу, в противном случае — их казнят.
  5. До начала заключения преступникам разрешено собраться вместе и разработать план действий, позволяющий им покинуть место лишения свободы в соответствии с правилами задачи.
  6. Заключенным не известен порядок, в котором будут они сидеть в карцере, но им сообщили, что согласно плану надзирателей:
    • каждый заключенный побывает в карцере;
    • после выхода из него заключенный вновь попадает туда через конечное число дней.
  7. Предполагается, что ни один из преступников не может ни освободиться, ни умереть иначе как в результате того, что кто-то из заключенных сообщит надзирателю о факте пребывания в карцере каждого преступника.

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

Сложность предложенной задачи состоит в том, что заключенные могут обмениваться информацией только через состояние лампочки (включена, выключена), т.е. используя 1 бит. Из постановки задачи следует, что для освобождения преступникам необходим обмен информацией, так как по крайней мере один из них должен узнать, что остальные побывали в карцере.

Решение

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

Каждый преступник, попадая в карцер, должен руководствоваться следующими правилами.

  1. Все, кроме главаря, обязаны включить лампочку ровно один раз.
  2. Выключать лампочку имеет право только главарь. Выключая лампочку, он узнает о том, что еще один человек побывал в карцере по крайней мере один раз.
  3. Главарем считается преступник, попавший в карцер в первый день. Если до начала заключения лампочка была включена, то главарь в первый день ее выключает. При этом, естественно, он не считает, что кто-то из десяти преступников побывал в карцере до него.
  4. Включать можно только выключенную лампочку, а выключать только включенную. Например, если главарь, в очередной раз попав в карцер, обнаруживает лампочку выключенной, то он не предпринимает никаких действий.
  5. Когда главарь узнает о том, что каждый преступник побывал в карцере, он сообщит об этом надзирателю, который должен освободить заключенных.

Таким образом, основная идея решения рассматриваемой задачи состоит в том, что рядовой преступник (не главарь), включая лампочку, сообщает главарю о том, что побывал в карцере. А выключение лампочки главарем означает, что сообщение принято.

Это словесное решение имеет вид, традиционный для логических головоломок. Приведем более четкую и строгую форму описания решения, используя автоматный подход [6]. Построим конечный автомат, описывающий поведение преступника. Так как до начала заключения все преступники неотличимы друг от друга, то достаточно одного автомата, чтобы описать поведение любого из них. Специфицируем интерфейс этого автомата с помощью схемы связей, показанной на рис. 1.

Рис. 1. Схема связей автомата

По постановке и решению задачи построим граф переходов автомата с пятью состояниями:

  • «Никогда не включал лампочку»;
  • «Главарь»;
  • «Однажды включал лампочку»;
  • «Освобождение»;
  • «Казнь».

Граф переходов, использующий эти состояния, приведен на рис. 2.

Рис. 2. Граф переходов, описывающий решение задачи

Для соответствия графа постановке задачи введено состояние «Казнь», которое недостижимо, так как решение задачи корректно.

Программная реализация решения

Для визуализации решения, представленного в виде автомата, написана программа на языке C++ . Код программы включает два класса: «Надзиратель» (Jailer) и «Преступник» (Criminal).

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

«Надзиратель» генерирует события, вызывая реализованные в классе «Преступник» соответствующие методы (обработчики событий), которые, в свою очередь, вызывают автомат, описывающий поведение преступника.

В классе «Преступник» описаны следующие основные поля:

  • состояние соответствующего автомата (_y0);
  • счетчик, используемый главарем (_counter) для учета побывавших в карцере преступников;
  • номер текущего дня.

Каждый преступник имеет доступ к глобальной переменной, описывающей состояние лампочки (lamp). Автомат (его граф переходов изображен на рис. 2), а также описанные выше входные и выходные воздействия реализованы в виде методов класса «Преступник». Дополнительно в класс «Преступник» включены методы протоколирования. Для простоты их реализации в этот класс добавлен массив строк с названиями состояний. Каждый экземпляр этого класса обеспечивает вывод в отдельный поток.

В приложении 2 приведены два протокола: для рядового преступника и для главаря. Из протоколов следует, что преступники были освобождены на 93-й день заключения. Ясно, что для других запусков программы, вследствие случайности выбора порядка помещения преступников в карцер, эта величина может измениться (но она не может быть меньше 11).

Изложенное подтверждает следующее высказывание: «...протоколы (истории вычислений) являются конструкциями, вскрывающими механизм работы программы, и поэтому среди теоретиков программирования складывается представление, что множество протоколов лучше характеризуют программу, нежели сам исходный программный текст» [8].

Сравнение с аналогичным решением

На следующий день после постановки Н.Н. Шамгуновым задачи описанное выше решение было ему послано, а от него было получено подтверждение о правильности такого решения. Через некоторое время на форуме сайта http://www.softcraft.ru развернулась дискуссия по поводу этой задачи. После чего решение, близкое к изложенному, было предложено И. Дехтяренко [9], и уже на его основе В.С. Любченко выполнил имитационное моделирование задачи [10].

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

Заключение

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

Существуют также другие задачи о преступниках [1, 2] и пленниках [11], но они выходят за рамки данной статьи. Программа доступна на сайте http://is.ifmo.ru (раздел «Статьи»).

Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 «Разработка технологии автоматного программирования».

Литература
  1. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1999.
  2. Гарднер М. Математические досуги. М.: Мир, 2000.
  3. Гарднер М. Математические новеллы. М.: Мир, 2000.
  4. Кулик Б.А. Логические основы здравого смысла. СПб.: Политехника, 1997.
  5. Кулик Б.А. Логика естественных рассуждений. СПб.: Политехника, 2001.
  6. Шалыто А.А., Туккель Н.И. Программирование с явным выделением состояний. // Мир ПК. 2001. № 8, 9.
  7. http://is.ifmo.ru Раздел «Мысли». Задачи на сообразительность. Задача о преступниках.
  8. Ершов А.П. Смешанные вычисления // В мире науки. 1984. № 6.
  9. Дехтяренко И. Форум сайта http://www.softcraft.ru. Тема №35 «Задача о преступниках».
  10. Любченко В.С. Задача о преступниках. http://softcraft.ru/auto/ka/crimes/crimes.shtml.
  11. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.

ОБ АВТОРАХ

Максим Александрович Мазин — студент кафедры «Компьютерные технологии» Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУ ИТМО). E-mail: mazine@rain.ifmo.ru.

Анатолий Абрамович Шалыто — профессор кафедры «Компьютерные технологии» СПбГУ ИТМО. E-mail: shalyto@mail.ifmo.ru.