На этом шаге мы рассмотрим рекурсивное решение этой задачи.

Тримино - многоугольник из трёх равных смежных квадратов. Без учёта вращений и зеркальных отражений тримино бывают только двух типов - типа "I" и типа "L", как показано на рисунке 1.

Рис.1. Типы тримино без вращений и симметрии

Задача укладки тримино - покрыть L-тримино квадратное поле (возможно, с "дырами") размером n*n, где n > 2 есть степень двух. Рисунок 2 поясняет задачу на графическом примере.

Рис.2. Задача укладки тримино

Размер задачи - очевидно, n. Наименьшие экземпляры задачи соответствуют полям размера 2х2, решения для которых тривиальны. На рисунке 3 показана декомпозиция методом "разделяй и властвуй", используемая в рекурсивном условии.

Рис.3. Декомпозиция задачи укладки тримино

Исходное поле (a) поделено на четыре меньших квадратных поля размером n/2 (b). Однако только одно из этих меньших полей будет содержать исходную дыру. Поэтому остальные три поля не являются подзадачами, подобными исходной. Но этот вопрос решается размещением тримино в центре поля так, чтобы три его квадрата стали дырами в меньших полях и тем самым обеспечили бы подобие подзадач исходной задаче (c).

Для графического отображения решения задачи будем использовать пакет Matplotlib. В частности, само тримино можно изобразить шестью отрезками прямой. Но поскольку за счёт поворотов возможны четыре варианта L-тримино (см. рисунок 4), в примере 6.11 определяются четыре вспомогательные функции для каждого из таких случаев.

Рис.4. Вращения L-тримино

Пример 6.11. Вспомогательные функции для рисования тримино

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def draw_L1(x, y):
    plt.plot([x, x + 2], [y + 2, y + 2], 'k-')
    plt.plot([x, x + 1], [y + 1, y + 1], 'k-')
    plt.plot([x + 1, x + 2], [y, y], 'k-')
    plt.plot([x, x], [y + 1, y + 2], 'k-')
    plt.plot([x + 1, x + 1], [y, y + 1], 'k-')
    plt.plot([x + 2, x + 2], [y, y + 2], 'k-')


def draw_L2(x, y):
    plt.plot([x, x + 2], [y + 2, y + 2], 'k-')
    plt.plot([x, x + 1], [y, y], 'k-')
    plt.plot([x + 1, x + 2], [y + 1, y + 1], 'k-')    
    plt.plot([x, x], [y, y + 2], 'k-')
    plt.plot([x + 1, x + 1], [y, y + 1], 'k-')
    plt.plot([x + 2, x + 2], [y + 1, y + 2], 'k-')


def draw_L3(x, y):
    plt.plot([x, x + 2], [y, y], 'k-')
    plt.plot([x, x + 1], [y + 1, y + 1], 'k-')
    plt.plot([x + 1, x + 2], [y + 2, y + 2], 'k-')
    plt.plot([x, x], [y, y + 1], 'k-')
    plt.plot([x + 1, x + 1], [y + 1, y + 2], 'k-')
    plt.plot([x + 2, x + 2], [y, y + 2], 'k-')


def draw_L4(x, y):
    plt.plot([x, x + 2], [y, y], 'k-')
    plt.plot([x, x + 1], [y + 2, y + 2], 'k-')
    plt.plot([x + 1, x + 2], [y + 1, y + 1], 'k-')
    plt.plot([x, x], [y, y + 2], 'k-')
    plt.plot([x + 1, x + 1], [y + 1, y + 2], 'k-')
    plt.plot([x + 2, x + 2], [y, y + 1], 'k-')

Функции получают координаты (x, у) нижнего левого угла квадрата 2х2, охватывающего тримино. Команда plot([x₁, x₂], [у₁, у₂], 'k-'), чертит отрезок прямой между точками (x₁, у₁) и (x₂, у₂).

В примере 6.12 приводится возможная реализация рекурсивного метода. Процедура должна знать, какую задачу/подзадачу она должна решить. Эта информация задаётся первыми тремя её параметрами. Первые два - это координаты левой нижней точки (x, у) поля, а третий - размер поля (n). Последние два параметра задают положение дырки (в частности, (p, q) определяют левый нижний угол квадрата 1х1). И начальные, и рекурсивные условия используются методом для определения относительного положения дырки и рисования соответствующего тримино. Наконец, в рекурсивном условии метод вызывает себя четырежды с разными параметрами для разных подзадач вместе с новыми дырами в трех из них.

Пример 6.12. Вспомогательные функции для рисования тримино

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def trominoes(x, y, n, p, q):
    if n == 2:
        if y == q:  # дырка в нижней плитке
            if x == p:  # дырка в нижней левой плитке
                draw_L1(x, y)
            else:  # дырка в правом нижнем углу плитки
                draw_L2(x, y)
        else:  # дырка в верхней плитке
            if x == p:  # дырка в верхней левой плитке
                draw_L3(x, y)
            else:  # дырка в правом верхнем углу плитки
                draw_L4(x, y)

    else:
        mid_x = x + n // 2
        mid_y = y + n // 2

        if q < mid_y:  # дырка в нижних квадратах

            if p < mid_x:  # дырка в левом нижнем квадрате
                draw_L1(mid_x - 1, mid_y - 1)
                trominoes(x, y, n // 2, p, q)
                trominoes(x, mid_y, n // 2, mid_x - 1, mid_y)
                trominoes(mid_x, y, n // 2, mid_x, mid_y - 1)
                trominoes(mid_x, mid_y, n // 2, mid_x, mid_y)
            else:  # дырка в правом нижнем квадрате
                draw_L2(mid_x - 1, mid_y - 1)
                trominoes(x, y, n // 2, mid_x - 1, mid_y - 1)
                trominoes(x, mid_y, n // 2, mid_x - 1, mid_y)
                trominoes(mid_x, y, n // 2, p, q)
                trominoes(mid_x, mid_y, n // 2, mid_x, mid_y)    

        else :  # дырка в верхних квадратах

            if p < mid_x:  # дырка в левом верхнем квадрате
                draw_L3(mid_x - 1, mid_y - 1)
                trominoes(x, y, n // 2, mid_x - 1, mid_y - 1)
                trominoes(x, mid_y, n // 2, p, q)
                trominoes(mid_x, y, n // 2, mid_x, mid_y - 1)
                trominoes(mid_x, mid_y, n // 2, mid_x, mid_y)
            else:  # дырка в правом верхнем квадрате
                draw_L4(mid_x - 1, mid_y - 1)
                trominoes(x, y, n // 2, mid_x - 1, mid_y - 1)
                trominoes(x, mid_y, n // 2, mid_x - 1, mid_y)
                trominoes(mid_x, y, n // 2, mid_x, mid_y - 1)
                trominoes(mid_x, mid_y, n // 2, p, q)

В заключительном примере 6.13 приводится фрагмент кода, который можно использовать для вызова метода тримино. Строка 6 создает фигуру, строка 7 устанавливает белый цвет её фона, а ax в строке 8 фиксирует оси внутри фигуры. После определения размера исходного поля (строка 9) в нём наугад выбирается и рисуется дыра (строка 12). Если используется пакет Matplotlib, то прямоугольник можно нарисовать вызовом метода Rectangle. Он получает координаты левой нижней вершины вместе с шириной, высотой и, возможно, другими параметрами. В строке 13 вызывается основной метод, а последние строки подавляют масштабирование, убирают оси внутри фигуры и рисуют её.

Пример 6.13. Вызов метода тримино

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import random
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle


fig = plt.figure()
fig.patch.set_facecolor('white')
ax = plt.gca()
n = 16  # степень 2
p = random.choice([i for i in range(n)])
q = random.choice([i for i in range(n)])
ax.add_patch(Rectangle((p, q), 1, 1, facecolor=(0.5, 0.5, 0.5)))    
trominoes(0, 0, n, p, q)
plt.axis('equal')
plt.axis('off')
plt.show()

Архив с полным текстом приложения можно взять здесь.

Результат работы приложения приведен на рисунке 5.

Рис.5. Результат работы приложения

На следующем шаге мы рассмотрим задачу очертания.

Предыдущий шаг Содержание Следующий шаг