Идеи реализации
Пред. Глава 42. Полимино След.

Идеи реализации

Рекурсивный подход

Каждая из фигур n-полимино получается из некоторой фигуры n − 1 -полимино следующим образом: на каждой стороне n − 1 -полимино вырастает n-я клетка. Пронумеруем стороны так, как показано на рисунке:

Таблица иллюстрирует положения отростков (зелёный цвет), выросших на сторонах:

01234567

Среди построенных тетрамино нашлись равные: № 1=№ 2, № 5=№ 6.

Это соображение позволяет искать n-полимино рекурсивно: 

для того, чтобы найти все n-полимино, нужно:
	если n=1, то:
		возвратить список, состоящий из единственной одноклеточной фигуры;
	конец если
	найти все n−1-полимино;
	для каждой найденной фигуры n−1-полимино:
		для каждой её стороны:
			добавить на этой стороне «отросток» в виде новой клетки;
			добавить построенную фигуру в список найденных n-полимино;
		конец цикла
	конец цикла
	сократить список найденных n-полимино, удалив оттуда
		«плохие», т. е. неодносвязные, а также в каждом классе равных друг
		другу фигур оставляя по одному представителю;
	возвратить переработанный список найденных фигур;
конец процедуры

Поскольку приведённый алгоритм работает с фигурами в терминах сторон, а не клеток, удобно описывать фигуры в этих же самых терминах.

Предлагаем кодировать фигуры как замкнутые ломаные с единичными горизонтальными и вертикальными сторонами, направленными вправо, вверх, влево и вниз. Фигура — это последовательность сторон, но не каждая последовательность сторон есть фигура: ломаные могут быть незамкнутыми, могут иметь самопересечения.

Стороны фигур бывают четырёх типов, поэтому каждую можно было бы кодировать парой битов, упаковывая эти пары в байты (по 4 штуки), а байты — в строку. Однако манипуляции с битами — сложное занятие (см. «Манипуляции с отдельными битами в строке»). Лучше кодировать стороны символами R=right, U=up, L=left, D=down, а фигуру целиком — как строку, составленную из таких символов. Следует учесть, что одну и ту же замкнутую ломаную можно, стартуя из начальной вершины, обходить как против часовой стрелки, так и по часовой стрелке:

Нам всё время кажется, что фигуры «T» на этом рисунке склонились друг к другу, хотя мы точно знаем, что это не так. Оптический обман зрения?

против часовой стрелкипо часовой стрелке
DRDRURULLLRRRDLDLULU

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

При выборе стандартного (против часовой стрелки) порядка обхода контура фигуры слева от стороны всегда находится клетка фигуры, а справа пусто:

Вырастание отростка на стороне — это замена символа, кодирующего эту сторону, на три символа:

→
…R…→…DRU…

Ещё три рисунка…

После появления отростка может возникнуть такая ситуация (отросток на стороне № 5):

→
RRUULDLD→RRUULLDRLD

Разрез на фигуре появился благодаря только что сформулированному правилу преобразования кодирующей строки при появлении отростка. Этот разрез нам совершенно не нужен: на его сторонах нарушается требование о том, чтобы справа от стороны было свободное место, и поэтому на сторонах разреза не должен появиться отросток (он как раз появляется справа; в отсутствие свободного места справа он наложится на какую-то клетку фигуры). С разрезами нужно немедленно бороться.

Борьба может происходить так: если стороны разреза не сходятся в начальной точке ломаной, тогда кодирующая строка содержит подряд два символа, обозначающих противонаправленные стороны: R и L, U и D. Таким образом из кодирующей строки следует исключить последовательности LR, RL, UD, DU. Важно не забыть и про другой случай, когда стороны разреза сходятся в начальной точке. Тогда «противоположные» символы встретятся в начале и конце кодирующей строки. Их тоже следует удалить. Рисунок иллюстрирует борьбу с разрезом:

→
RRUULLDRLD→RRUULLDD

Появление отростка может привести к появлению глубоких разрезов (отросток на стороне № 10):

→
RRUUULLDRDLD→RRUUULLDRDULDD

Лечение таких разрезов должно происходить в два этапа:

→
→
RRUUULLDRDULDD→RRUUULLDRLDD→RRUUULLDDD

Отсюда вывод: нужно устранять разрезы до тех пор, пока их не останется.

А почему глубина разрезов, образующихся при появлении отростка, не может превышать двух? Если бы такие разрезы могли образоваться, они окружали бы клеточку-отросток с трёх свободных сторон (четвёртой стороной отросток примыкает к клетке исходной фигуры). Это означало бы, что в исходной фигуре уже была дырка, анклав, а такие фигуры неодносвязны. Но на каждом этапе у нас строятся лишь односвязные фигуры, а те, что не удовлетворяют этому требованию, выбраковываются. Подробнее проблему контроля за односвязностью мы рассмотрим в разделе «Утрата односвязности».

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

→

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

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

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

Петли длины 2 — это разрезы, с которыми мы уже справились. Оставшиеся петли могут охватывать хотя бы одну клетку плоскости, и поэтому их длины начинаются с четырёх.

Мысленно очертим вокруг дырки наименьший прямоугольник с горизонтальными и вертикальными сторонами. Анклав окружён со всех сторон клетками фигуры, значит, со всех четырёх сторон от прямоугольника имеется участки границы фигуры с суммарной длиной как минимум четыре. Часть фигуры, попавшая в примыкающие к прямоугольнику со всех четырёх сторон два столбца и две строки попадут ещё участки границы общей длиной не менее восьми: в каждом из двух столбцов — слева и справа — по два отрезка (сверху и снизу); в каждой из двух строчек — снизу и сверху — ещё по два (слева и справа). Таким образом получается, что периметр фигуры превышает длину петли как минимум на двенадцать единиц.

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

Как мы уже заметили, в строке, кодирующей петлю, «противоположные» символы (R и L, D и U) встречаются только парами. Действительно, при обходе петли от начала до конца мы возвращается в прежнюю вершину. Это означает, что количество сдвигов вправо равно количеству сдвигов влево (аналогично, вниз и вверх). Строка кодирует петлю тогда и только тогда, когда в ней равны количества букв R и L и равны количества букв D и U.

Как проверить равенство двух n-полимино, рассматривая их кодирующие строки?

Напомним, фигуры считаются равными, если они получаются друг из друга поворотом на угол, кратный 90°. При повороте на 90° (вокруг начальной вершины) каждый символ R в кодирующей строке заменяется на U, U на L, L на D и D на R:

 U 
L↺R
 D 

Кроме того, наш способ кодирования фигур избыточен: по-разному кодируются фигуры, отличающиеся только лишь выбором начальной вершины. Вот если бы кодирующую строку свернуть в кольцо…

Рисунок...

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

Таким образом одну и ту же фигуру можно закодировать самое большее 4 ⁢ s способами, где s — количество её сторон (=вершин), а 4 — повороты на 0°, 90°, 180° и 270°.

Один из возможных подходов к проверке равенства фигур заключается в следующем. Сравнивая фигуру A с фигурой B, мы находим множество всевозможных строк, кодирующих фигуру A, и проверяем, входит ли срока, кодирующая фигуру B, в это множество. Этот подход может оказаться затратным, если фигуры придётся сравнивать часто.

Есть и альтернатива. Как только фигура появилась на свет, или как только изменилась (появился отросток), нужно найти множество эквивалентных строк, кодирующих фигуру и отличающихся друг от друга всевозможными поворотами и различными вариантами выбора начальной точки ( 4 ⁢ s вариантов, среди которых могут быть и одинаковые). Затем выбираем в этом классе эквивалентности по единым правилам какой-то один элемент (назовём его каноническим представителем класса). В качестве такого канонического представителя подойдёт наименьшая в смысле лексикографического порядка строка (то есть та, которая идёт раньше других по алфавиту). На неё и нужно заменить кодирующую данную фигуру строку. Этот процесс будем называть канонизацией кодирующей строки.

Пример...

Если каждая фигура будет задана каноническим образом, их будет легко сравнить — достаточно сравнить кодирующие строки: фигуры равны тогда и только тогда, когда равны их кодирующие строки.

В каком виде будущая программа будет выводить найденные n-полимино?

Простейший метод вывода, который очень легко запрограммировать — вывод кодирующих строк: 

% ./polyomino.pl 4
0	[DDDDRUUUUL]
1	[DDDRRULUUL]
2	[DDDRURULUL]
3	[DDDRUURULL]
4	[DDRDRUULUL]
5	[DDRRUULL]
6	[DDRURUULDL]

Второй метод сложнее для реализации. Это вывод изображений фигур (с помощью значков ▒ и пробелов): 

% ./polyomino.pl 4
==== 0  [DDDDRUUUUL]
▒
▒
▒
▒
==== 1  [DDDRRULUUL]
▒
▒
▒▒
==== 2  [DDDRURULUL]
▒
▒▒
▒
==== 3  [DDDRUURULL]
▒▒
▒
▒
==== 4  [DDRDRUULUL]
▒
▒▒
 ▒
==== 5  [DDRRUULL]
▒▒
▒▒
==== 6  [DDRURUULDL]
 ▒
▒▒
▒

Ещё один возможный метод вывода результатов: создание графических файлов. Описание фигуры при помощи строки, кодирующей её контур, наводит на мысль использовать векторный графический формат, например, SVG. Векторный формат тоже описывает контуры фигур. Вот как выглядит векторный файл, содержащий изображение фигуры «» тетриса: 

examples/TetraminoTExample.svgSVG
<?xml version="1.0" encoding="UTF-8"?>
<svg
	xmlns="http://www.w3.org/2000/svg"
	version="1.1"
	width="75"
	height="50"
	>
	<path
		d="M 0 0 v 25 h 25 v 25 h 25 v -25 h 25 v -25 z"
		fill="red"
		/>
</svg>

Здесь следует обратить внимание на элемент path. Он описывает форму фигуры. Значение M 0 0 v 25 h 25 v 25 h 25 v -25 h 25 v -25 z его атрибута d означает следующее: встать в точку с координатами 0 0 (M 0 0), сдвинуться вниз на 25 единиц (v 25), затем вправо на 25 (h 25), …, вверх на 25 (v -25), и, наконец, замкнуть путь (z). Замкнуть путь — значит провести отрезок из последней точки в самую первую. Только лишь замкнутые пути можно закрашивать без осложнений. Цвет закрашивания указывается в атрибуте fill.

Изображения в формате SVG можно просматривать программой InkView из пакета inkscape (запускается командой inkview), см. рисунок 42.1. «Скриншот программы InkView». Программа display из пакета imagemagick тоже позволяет просматривать изображения в разнообразных форматах, и, в частности, SVG. Наконец, многие современные веб-броузеры могут показывать SVG-файлы в окне, и, кроме того, показывают SVG-вставки в веб-страницах. Например, все изображения, кроме скриншота, которые вы видите на этой странице (или не видите, если используете неполноценный броузер), выполнены в формате SVG и внедрены в текст страницы, имеющий формат XHTML.

Рисунок 42.1. Скриншот программы InkView
Скриншот программы InkView


И SVG, и XHTML имеют сходную структуру, и это не удивительно: оба этих формата основаны на XML — расширяемом языке разметки (eXtensible Markup Language). Существует множество других форматов, имеющих ту же основу. XML и его приложения заслуживают отдельного разговора. Хотя этот разговор сильно уведёт нас в сторону от изучения языка Perl, мы, считая XML-технологии важными, уделим внимание этой теме в разделе «XML и его приложения».

Сейчас лишь приведём пример вывода программы в режиме XHTML+SVG для n = 3 : 

examples/out/Polyomino3.xhtmlXHTML
<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg">
<head>
<title>3-полимино</title>
<style type="text/css">
@namespace url("http://www.w3.org/1999/xhtml");
@namespace svg url("http://www.w3.org/2000/svg");
body
{
	font-size: 20pt;
}

svg|path
{
	fill: red;
	stroke: black;
}
</style>
</head>
<body>
<table>
<tr>
<td>0</td>
<td>
<svg:svg
	version="1.1"
	viewBox="-18 -18 72 144"
	width="72"
	height="144"
	>
	<svg:path d="M 0 0 v 108 h 36 v -108 h -36 z"/>
</svg:svg>
</td>
<td><code>DDDRUUUL</code></td>
</tr>
<tr>
<td>1</td>
<td>
<svg:svg
	version="1.1"
	viewBox="-18 -18 108 108"
	width="108"
	height="108"
	>
	<svg:path d="M 0 0 v 72 h 72 v -36 h -36 v -36 h -36 z"/>
</svg:svg>
</td>
<td><code>DDRRULUL</code></td>
</tr>
</table>
</body>
</html>

Тело этого XHTML-документа состоит из трёхколоночной таблицы. Первый её столбец предназначен для номера фигуры, вторая — для её SVG-изображения, а третья — для кодирующей строки. Примеры вывода программы для других значений n вы найдёте по ссылкам: Polyomino4.xhtml, Polyomino5.xhtml, Polyomino6.xhtml, Polyomino7.xhtml, Polyomino8.xhtml, Polyomino9.xhtml, Polyomino10.xhtml.

[Внимание]Внимание

Будьте поосторожнее с последней ссылкой: столь огромный документ (2.3M) может привести ваш броузер в состояние искусственной комы.

В работе

Пожалуй, самое сложное в нашей программе — запрограммировать вывод фигур по клеткам. Это нужно для вывода фигур в режиме ASCII-графики. Придётся преобразовать контурное описание фигуры в список клеток, которые её составляют. Предлагаем подход, который проиллюстрируем на примере замысловатой фигуры на рисунке 42.2. «Преобразование контурного описания полимино в клеточное»:

Рисунок 42.2. Преобразование контурного описания полимино в клеточное


Будем использовать две системы координат: i j и x y . Начало первой из них находится в левом нижнем углу наименьшего прямоугольника, содержащего фигуру. Начало второй — в начальной точке контура. Координатные оси обоих систем направлены стандартным образом. Координаты любой точки, как нетрудно видеть, связаны соотношениями: i = x − x min , j = y − y min , где x min и y min  — координаты левого нижнего угла описанного прямоугольника в системе координат x y . Или, если угодно, i = x + i 0 , j = y + j 0 , где i 0 и j 0  — координаты начальной точки контура фигуры в системе координат i j .

Рассмотрим на координатной плоскости i j горизонтальную полосу, состоящую из точек, чьи ординаты принадлежат отрезку j j + 1 (назовём такую полосу j-ой). На нашем рисунке это вторая полоса (она серого цвета).

Определим, какие клетки фигуры принадлежат j-ой полосе. Будем последовательно обходить контур против часовой стрелки, стартуя из начальной точки с координатами i 0 j 0 . Как только встретится вертикальная сторона контура, попавшая в полосу, запомним её абсциссу, добавив в некий список. Для второй полосы, отмеченной на рисунке, получим следующий список: 1 0 4 5 6 2 . Такие списки составим для каждой горизонтальной полосы с номерами от нулевой до самой верхней. Приводим в таблице результаты:

номер полосысписок абсцисс
0 0 3
1 1 0 3 5 6 2
2 1 0 4 5 6 2
3 1 0 6 3

Забегая вперёд, отметим, что такую таблицу удобно разместить в массиве. Индексами в нём будут номера полос (рядов), а значениями — ссылки на анонимные массивы со списками абсцисс. Именно поэтому мы предпочли координатную систему i j , в которой ординаты j играют роль номеров полос, и, кроме того, все неотрицательны. Отрицательные числа нельзя использовать в качестве индексов в массиве.

Обратим внимание на то, что в каждом из списков оказалось чётное количество чисел. Это не так уж удивительно: у ограниченной фигуры её граница пересекает полосу парным образом: вниз — вверх, вниз — вверх…

Теперь упорядочим по возрастанию каждый список абсцисс:

номер полосысписок абсцисс
0 0 3
1 0 1 2 3 5 6
2 0 1 2 4 5 6
3 0 1 3 6

Чудесным образом оказывается, что после такого переупорядочения в каждом списке абсцисс числа, оказавшиеся на чётных местах (нумерацию ведём, как обычно, с нуля) соответствуют движению вниз, а на нечётных — вверх. Немного размышлений, и мы приходим к выводу, что никакого чуда тут нет. Самый левый отрезок границы, попавший в полосу, всегда идёт вниз; тот, который правее — вверх, затем снова вниз, затем вверх… Так что числа в упорядоченных списках можно сгруппировать по парам:

номер полосысписок абсцисс
0 0 3
1 0 1 2 3 5 6
2 0 1 2 4 5 6
3 0 1 3 6

Каждый диапазон вида a b означает, что в данном ряду имеются клетки с абсциссами i, удовлетворяющими неравенствам a ⩽ i < b (считаем абсциссой клетки абсциссу её левой стороны).

Таким образом, фигура, представленная на рисунке, содержит в нулевом (самом нижнем) ряду клетки в нулевом, первом и втором столбцах, в первом ряду — в нулевом, втором и пятом столбцах, во втором ряду — в нулевом, втором, третьем и пятом столбцах, в третьем ряду — в нулевом, третьем, четвёртом и пятом столбцах. Этот результат получен не в результате созерцания рисунка, а чисто алгоритмически.

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

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

new($string)

Конструктор. Создаёт новый объект класса на основе кодирующей строки $string.

canonize()

Канонизирует фигуру, заменяя её кодирующую строку на канонический представитель класса, к которому эта строка принадлежит.

offshut($n)

Конструктор, создающий новое n + 1 -полимино, полученное добавлением отростка на $n-ой стороне объекта Polyomino. Если отросток вырастить невозможно (контур нового n + 1 -полимино оказывается не простым), возвращает значение undef.

toString()

Возвращает кодирующую строку фигуры.

boundingBox()

Возвращает четырёхэлементный массив с координатами левого нижнего и правого верхнего углов фигуры (начальная точка располагается в начале координат).

toSVG()

Возвращает строку, содержащую SVG-документ с изображением фигуры.

toASCII()

Возвращает строку, содержащую ASCII-представление фигуры.

subpath($k, $l)

Возвращает строку, кодирующую часть границы фигуры, начинающуюся с $k-й вершины и длиной $l. Кодирующая строка предполагается свёрнутой в кольцо.

perimeter()

Возвращает периметр фигуры, то есть длину её кодирующей строки.

isSimple()

Возвращает истинное значение, если фигура правильная (её контур прост), и ложное в противном случае.

Вся необходимая информация о фигуре содержится в её кодирующей строке. Поэтому будет разумно реализовать объекты класса Polyomino как ссылки на кодирующие строки.

Пред. Наверх След.
Глава 42. Полимино Начало Разработка
Информатика-54© А. Н. Швец