Константин Кноп, Konstantin@Knop.com
Опубликовано:
30.3.1998
На одной из первых олимпиад школьников по программированию предлагалась такая задача:
Океан изображен (закодирован) матрицей NxN. Каждый остров - это
"звездочка" в матрице. Задача состоит в построении карты островов только по
кодированной информации о горизонтальном и вертикальном расположении островов.
Чтобы проиллюстрировать этот код, рассмотрим такую "карту":
Числа слева от каждой строки показывают порядок и размеры групп островов в
этих строках. Например, "1 2" в первой строке означает, что в этой строке
находится группа из одного острова, за которой идет группа из двух островов с
океаном произвольной длины слева и справа от каждой группы островов. Аналогичным
образом последовательность "1 1 1" над первым столбцом означает, что в этом
столбце находится три группы с одним островом в каждой, и т. д.
Естественно, вначале на карте нет никаких звездочек - смысл задачи и заключается в том, чтобы их расставить. Если исходные числа подобраны корректно, то расстановка звездочек, во-первых, существует, а во-вторых, может быть найдена чисто логическими рассуждениями.
Покажем, как это можно сделать для уже нарисованной выше карты. Например,
можно начать с заполнения четвертого столбца.Так как там стоят числа "2 3", то в
этом столбце располагаются ровно пять островов: два сверху, потом океан, потом
еще три острова. Но так как высота столбца равна 6, то океан занимает в этом
столбце ровно одну клетку. Таким образом, четвертый столбец уже заполнен. Дальше
аналогично заполняется, скажем, пятая строка. Карта постепенно прорисовывается и
приобретает такой вид:
Теперь, оказывается, последняя строка уже заполнена, и можно легко
восстановить первый и последний столбцы, а затем и вторую строку. Это дает такой
промежуточный результат:
Я не буду лишать читателей удовольствия самим закончить решение этой головоломки. Но все дело в том, что задача "острова в океане" - это не начало истории, а ее середина. А начало ей положил еще на пару лет раньше японец Нишио Тецуя (Tetsuya Nishio). Именно он является автором этого замечательного типа головоломок. Впервые такие задачки - Нишио назвал их paint-by-numbers - были предложены им на международном конкурсе решателей головоломок, состоявшемся в 1990 году. При этом участники состязались между собой на скорость решения серии таких задач (и естественно, на правильность). Головоломки понравились многим - и очень быстро завоевали себе место на страницах самых разных изданий, посвященных головоломкам и занимательным задачам. Печатались они и у нас - в газете "Поле Чудес" - под названием "японские кроссворды".
Вот еще две задачи из серии paint-by-numbers. Первая - 10x10,
вторая - 20x25. И, как обычно, предлагаю к ним в качестве добавки
сверхзадачу для любителей поупражняться в программировании. Добавка, впрочем,
уже сформулирована: надо написать программу, которая сможет самостоятельно
решать задачи типа "островов в океане" для больших карт. (Обратите внимание, что
при картах размера 50x50 полный перебор вариантов уже потребует очень большого
машинного времени, так что этот путь мне представляется тупиковым. А вот если
попробовать применять различные эвристики, наподобие тех, которые использует
человек при решении такой задачи, поиск решения может быть существенно упрощен и
сокращен.) Желаю успехов! Пишите мне, как всегда, на kk@knop.spb.ru
Телефон редакции: (095) 232-2263
E-mail редакции: site@computerra.ru
По вопросам
размещения рекламы обращаться к Алене Шагиной или Ирине Лашковой по телефону +7
(095) 232-2263 или электронной почте reclama@computerra.ru