Одна из первых действительно интересных задач по математике, с которыми я столкнулся формулируется так: "из шахматной доски вырезали две противоположные по диагонали угловые клетки, можно ли оставшуюся часть разрезать на "доминошки" — фигурки из двух клеток, у которых одна сторона общая?". У нее очень простая формулировка, в отличие от великой теоремы Ферма она имет простое, элегантное, но неочевидное решение (если вы знаете решение задачи, то попробуйте применить его к фигуре справа).
В этой статья я расскажу о нескольких алгоритмах, которые умеют покрывать доминошками произвольную клетчатую фигуру на плоскости, если это возможно, находить ситуации, когда это невозможно и считать количество возможных замощений доминошками.
Nota bene! Материал этой статьи — это усеченный вариант вот этого jupyter-notebook, все картинки и анимации, которые вы увидите в статье, сгенерированы кодом из этого ноутбука (правда анимаций не будет в github предпросмотре). К слову, картинки из заголовка также сгенерированы с помощью python/matplotlib
import matplotlib.pyplot as plt
from matplotlib import colors as mcolors
colors = dict(mcolors.BASE_COLORS, **mcolors.CSS4_COLORS)
# Sort colors by hue, saturation, value and name.
by_hsv = sorted((tuple(mcolors.rgb_to_hsv(mcolors.to_rgba(color)[:3])), name)
for name, color in colors.items())
names = [name for hsv, name in by_hsv if name not in {'black', 'k', 'w', 'white', 'crimson', 'royalblue', 'limegreen', 'yellow', 'orange'}]
import random
random.shuffle(names)
names = ['crimson', 'royalblue', 'limegreen', 'yellow', 'orange', *names]
names.append('red')
names.append('white')
names.append('black')
def fill_cell(i, j, color, ax):
ax.fill([i, i, i + 1, i + 1, i], [j, j + 1, j + 1, j, j], color=color)
def draw_filling(filling):
if filling is not None:
n = len(filling)
m = len(filling[0])
fig = plt.figure(figsize=(m * 0.75, n * 0.75))
ax = fig.add_axes([0, 0, 1, 1])
ax.get_xaxis().set_visible(False)
ax.get_yaxis().set_visible(False)
for name, spine in ax.spines.items():
spine.set_visible(False)
spine.set_visible(False)
for i, row in enumerate(filling):
i = n - i - 1
for j, cell in enumerate(row):
fill_cell(j, i, names[cell], ax)
for i in range(n + 1):
ax.plot([0, m], [i, i], color='black')
for i in range(m + 1):
ax.plot([i, i], [0, n], color='black')
plt.close(fig)
return fig
else:
return None
Сделать это невозможно, и этому есть красивое и простое объяснение:
- На оставшейся части доски 30 черных и 32 белых клетки
- Каждая доминошка состоит из одной черной и одной белой клетки
- Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток
Динамическое программирование по профилю
Про динамического программирования есть статья на хабре, которая даже содержит пример с покрытием доминошками, я немного расширю этот пример.
Основная суть динамического программирования заключается в том, чтобы придумать для исходной задачи какие-то промежуточные подзадачи так, чтобы их можно было легко друг через друга выразить. Например, если мы хотим вычислить двухсотое число Фибоначчи, то для этого можно последовательно вычислить все числа Фибоначчи вплоть до нужного нам применяя соотношение
Аналогично можно вычислить число "сочетаний" , воспользовавшись одним из следующих рекуррентных соотношений
Для задачи "можно ли замостить доминошками прямоугольник ?" к сожалению подобных простых соотношений не существует. Тем не менее, если мы рассмотрим более широкий класс фигурок, то такие соотношения уже станут возможными, главное чтобы это не были слишком маленькие классы и динамическое программирование не превратилось в банальный перебор.
Посмотрим на следующий класс фигурок: у нас есть прямоугольник , на строке присутствуют первые клеток, остальные задаются профилем, на строке первые клеток задаются профилем, остальные не участвуют. Профиль — это последовательность нулей и единичек длины : если на -ой позиции профиля единичка, это значит что в этой фигуре есть соответствующая клетка, всего профилей (красные клетки — единички, синие — нули).
Профиль однозначно задается числом (его бинарное представление вплоть до разрядов является последовательностей нулей и единичек).
Прямоугольник соответствует фигуре с , и нулевым профилем. На фигурках такого типа мы можем считать две основные функции
- Максимальное возможное число покрытых доминошками клеток в этой фигуре
- Количество способов полностью покрыть доминошками эту фигуру
Давайте обозначим за количество способов замостить такую фигурку, тогда и при этом выражается через сумму нескольких , по большому счету переход от к — это перебор трех случаев: поставить вертикальную доминошку, если это возможно
горизонтальную доминошку, если это возможно
и пропустить занятую клетку. В случае, если мы пытаемся понять, какое максимальное число клеток фигурки возможно замостить, то сумма заменяется на максимум и добавляется один несложный переход — пропуск свободной клетки. Важным моментом также является то, что мы можем заранее вырезать несколько клеток, принципиально от этого ничего не поменяется.
Давайте теперь попробуем реализовать это (кода будет много, так что большинство я вынесу в спойлер). Зададим интересующий нас прямоугольник как множество строк из точек и решеток (точка — свободная клетка, решетка — занятая), пока все клетки будут свободными, потом потихоньку будем какие-нибудь вырезать
tiling = [
'........',
'........',
'........',
'........',
'........',
'........',
'........',
'........',
]
Начнем с
def count_tilings(tiling):
n = len(tiling)
m = len(tiling[0])
if ((n + 1) * m * 2 ** m) <= 10000000:
dp = [[[(0 if k != 0 or j != 0 or mask != 0 else 1) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]
for k in range(n):
for j in range(m):
for mask in range(2 ** m):
# Вертикальная доминошка
if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask & (1 << j)) == 0:
dp[k + ((j + 1) // m)][(j + 1) % m][mask + (1 << j)] += dp[k][j][mask]
# Горизонтальная доминошка
if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:
dp[k + ((j + 1) // m)][(j + 1) % m][mask + (2 << j)] += dp[k][j][mask]
# Клетка занята
if ((1 << j) & mask) != 0 or tiling[k][j] != '.':
dp[k + ((j + 1) // m)][(j + 1) % m][(mask | (1 << j)) - (1 << j)] += dp[k][j][mask]
return dp
dp = count_tilings(tiling)
print(dp[8][0][0])
получаем
12988816
Сверяемся с википедией, пока все в порядке. Давайте еще на всякий случай проверим, количество способов замостить полоску — должно получиться число Фибоначчи.
tiling_fib = [
'..',
'..',
'..',
'..',
'..',
'..',
'..',
'..'
]
dp = count_tilings(tiling_fib)
for i in range(8):
print(dp[i][0][0], end=' ')
1 1 2 3 5 8 13 21
Что ж, поехали дальше, проверим на доске с вырезанными углами
tiling_no_corners_opposite = [
'.......#',
'........',
'........',
'........',
'........',
'........',
'........',
'#.......',
]
dp = count_tilings(tiling_no_corners_opposite)
print(dp[8][0][0])
0
Супер. Допустим вычислять количество мы научились, может найдем хотя бы одно конкретное замощение для наглядности?
def cover_if_possible(tiling, dp=None):
if dp is None:
dp = count_tilings(tiling)
n = len(dp) - 1
m = len(dp[0])
if dp[n][0][0] == 0:
return None
result = [[-1 if tiling[i][j] == '#' else 0 for j in range(m)] for i in range(n)]
num = 0
k = n
j = 0
mask = 0
while k > 0 or j > 0:
#print(k, j, mask)
prev_j = j - 1
prev_k = k
if prev_j == -1:
prev_j += m
prev_k -= 1
# Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask
# Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее
# самого подсчета динамики
for prev_mask in range(2 ** m):
if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and dp[prev_k][prev_j][prev_mask] != 0:
mask = prev_mask
result[prev_k][prev_j] = num
result[prev_k + 1][prev_j] = num
#print(f'Vertical at ({prev_k}, {prev_j}) ({prev_k + 1}, {prev_j})')
num += 1
break
elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:
mask = prev_mask
result[prev_k][prev_j] = num
result[prev_k][prev_j + 1] = num
#print(f'Horisontal at ({prev_k}, {prev_j}) ({prev_k}, {prev_j + 1})')
num += 1
break
elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:
mask = prev_mask
break
j = prev_j
k = prev_k
return result
filling = cover_if_possible(tiling)
draw_filling(filling)
Слишком просто, давайте вырежем несколько клеток
tiling_random = [
'........',
'#.#.....',
'..#.....',
'........',
'........',
'........',
'........',
'...#....'
]
filling_random = cover_if_possible(tiling_random)
draw_filling(filling_random)
Попробуем теперь сделать тоже самое для замощения максимальной возможной части фигуры
def maxmimum_cover(tiling):
n = len(tiling)
m = len(tiling[0])
if ((n + 1) * m * 2 ** m) <= 10000000:
dp = [[[(n * m if k != 0 or j != 0 or mask != 0 else 0) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]
for k in range(n):
for j in range(m):
for mask in range(2 ** m):
next_k, next_j = k + ((j + 1) // m), (j + 1) % m
# Вертикальная доминошка
if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask & (1 << j)) == 0:
dp[next_k][next_j][mask + (1 << j)] = min(dp[next_k][next_j][mask + (1 << j)], dp[k][j][mask])
# Горизонтальная доминошка
if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:
dp[next_k][next_j][mask + (2 << j)] = min(dp[next_k][next_j][mask + (2 << j)], dp[k][j][mask])
# Клетка занята
if ((1 << j) & mask) != 0 or tiling[k][j] != '.':
dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask])
# Клетка не занята, рассмотриваем случай её пропуска
else:
dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask] + 1)
return dp
def cover_maximum_possible(tiling, dp=None):
if dp is None:
dp = maxmimum_cover(tiling)
n = len(dp) - 1
m = len(dp[0])
result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]
num = 0
k = n
j = 0
mask = 0
while k > 0 or j > 0:
#print(k, j, mask)
prev_j = j - 1
prev_k = k
if prev_j == -1:
prev_j += m
prev_k -= 1
# Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask
# Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее
# самого подсчета динамики
for prev_mask in range(2 ** m):
# Раньше мы здесь проверяли, что количество вариантов в этой ветке не 0, сейчас нужно
# проверить, что эта ветка ведет к максимальному покрытию
if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
mask = prev_mask
result[prev_k][prev_j] = num
result[prev_k + 1][prev_j] = num
num += 1
break
elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
mask = prev_mask
result[prev_k][prev_j] = num
result[prev_k][prev_j + 1] = num
num += 1
break
elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
mask = prev_mask
break
elif ((1 << prev_j) & prev_mask) == 0 and tiling[prev_k][prev_j] == '.' and (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] + 1 == dp[k][j][mask]:
mask = prev_mask
break
j = prev_j
k = prev_k
return result
И попробуем фигурку из заголовка
tiling_custom=[
'...####',
'....###',
'......#',
'#.#....',
'#......',
'##.....',
'###...#',
]
filling = cover_maximum_possible(tiling_custom)
draw_filling(filling)
Опа! Не получилось, в общем так и должно было быть. Прежде, чем пойти дальше пару слов о сложности алгоритмов. Всего фигурок , все переходы константные, отсюда асимптотика , которая может быть улучшена до если добавить транспонирование в случае, если . Построение конкретного замощения в приведенных реализациях имеет сложность , но можно сделать так, чтобы было просто , но это банально больше кода.
Замощение с помощью решения задачи о максимальном паросочетании
Возвращаясь к черно-белой раскраске как на шахматной доске можно заметить интересную интерпретацию задачи замощения доминошками. Давайте посмотрим на граф, в котором клетки фигуры — это вершины, ребрами соединены клетки, имеющие общую сторону. Так вот, доминошка в этом графе — это как раз ребро. Если раскрасить граф в шахматном порядке, то внезапно можно обнаружить, что этот граф — двудольный, черные — одна доля, белые — другая. Если переформулировать задачу замощения наибольшего числа клеток в терминах этого графа, то получается, что нужно найти максимальное по размеру множество ребер такое, чтобы вершины являлись концом не более одного ребра. В общем то, это довольно известная задача о максимальном паросочетании. Давайте попробуем её применить для решения этой задачи, тут получится даже с анимацией, приведу базовый алгоритм Куна для нахождения максимального паросочетания.
def check_valid(i, j, n, m, tiling):
return 0 <= i and i < n and 0 <= j and j < m and tiling[i][j] != '#'
def find_augmenting_path(x, y, n, m, visited, matched, tiling):
if not check_valid(x, y, n, m, tiling):
return False
if (x, y) in visited:
return False
visited.add((x, y))
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if not check_valid(x + dx, y + dy, n, m, tiling):
continue
if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):
matched[(x + dx, y + dy)] = (x, y)
return True
return False
def convert_match(matched, tiling, n, m):
result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]
num = 0
for x, y in matched:
_x, _y = matched[(x, y)]
result[x][y] = num
result[_x][_y] = num
num += 1
return result
def match_with_flow(tiling):
result_slices = []
n = len(tiling)
m = len(tiling[0])
matched = dict()
# Для наглядности визуализации
rows = list(range(n))
columns = list(range(m))
random.shuffle(rows)
random.shuffle(columns)
result_slices.append(convert_match(matched, tiling, n, m))
for i in rows:
for j in columns:
if (i + j) % 2 == 1:
continue
visited = set()
if find_augmenting_path(i, j, n, m, visited, matched, tiling):
result_slices.append(convert_match(matched, tiling, n, m))
return result_slices
Здесь даже получается проанимировать процесс
sequencial_match = match_with_flow(tiling_custom)
Суть алгоритма Куна (да и любого другого алгоритм для нахождения максимального паросочетания) заключается в нахождении "аугментирующих путей". В терминах доминошек это цепочка из доминошек, у которой рядом с доминошками на концах есть по свободной клетке, такие цепочки можно заменить на цепочки большей длины, охватывающие те же клетки и заполняя две свободные клетки рядом с концами цепочки. Более того, основное утверждение, на котором работают все алгоритмы нахождения максимального паросочетания, заключается в том, что если такой цепочки не удается найти, то значит большего замощения нам не получить.
UPD. Для последнего примера простое обоснование на основе черно-белой раскраски не работает. Насколько мне известно, есть два общих критерия для существования полного замощения:
- Теорема Холла (теорема о свадьбах)
Проверка условий этой теоремы вычислительно сложнее, чем построить максимальное паросочетание. - Условие высоты Тёрстона про это я мало что знаю
Недавно меня навели на очень интересную статью про замощения, там в том числе описывается про использовании групп для доказательства невозможности различных замощений.
Бонус! Раскраска планарного графа в 5 цветов.
Для визуализации замощения я использовал отдельный цвет для каждой доминошки. К сожалению некоторые цвета не очень хорошо смотрятся, а некоторые плохо контрастируют друг с другом. В этом случае подобрать цвета для хорошего контраста не так уж просто, особенно если доминошек много. Зато можно использовать меньше цветов: доминошки, которые не находятся рядом друг с другом можно раскрасить в одинаковый цвет, тогда визуально все еще будет понятно, как именно выглядит покрытие. В общем то это классическая задача о раскраске вершин планарного графа. Любой планарный граф можно покрасить в 4 цвета, правда хорошего алгоритма для такой покраски нет. Зато есть довольно простой алгоритм для покраски в 5 цветов, когда правда все еще много, и я его мало тестировал (если необходим 5ый цвет, то возможны баги)
def color_5(filling):
result = [[i for i in row] for row in filling]
# Строим граф
domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]
domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]
degree = [0 for i in range(max(map(max, filling)) + 1)]
n = len(filling)
m = len(filling[0])
for i, row in enumerate(filling):
for j, num in enumerate(row):
if num >= 0:
domino_tiles[num].append((i, j))
for i, tiles in enumerate(domino_tiles):
for x, y in tiles:
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
a, b = x + dx, y + dy
if 0 <= a and a < n and 0 <= b and b < m and filling[a][b] >= 0 and filling[a][b] != i and filling[a][b] not in domino_neighbours[i]:
domino_neighbours[i].add(filling[a][b])
degree[i] += 1
# Первым делом нужно найти такой порядок вершин, все вершины имели не больше 5 соседей среди
# предыдущих. Такой существует в силу того, что граф планарный, а найти его эффективнее всего
# по очереди находя вершину наименьшей степени и удаляя её из графа, так мы получаем обратный порядок
active_degrees = [set() for i in range(max(degree) + 1)]
for i, deg in enumerate(degree):
active_degrees[deg].add(i)
reversed_order = []
for step in range(len(domino_tiles)):
min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) > 0])
domino = active_degrees[min_degree].pop()
reversed_order.append(domino)
for other in domino_neighbours[domino]:
if other in active_degrees[degree[other]]:
active_degrees[degree[other]].remove(other)
degree[other] -= 1
active_degrees[degree[other]].add(other)
# Теперь перебираем в обратном порядке и либо красим в еще не занятый цвет,
# если есть свободный из 5 цветов, иначе находим цепочку из чередующихся цветов,
# которые могут быть перекрашены. Такая найдется в силу планарности
colors = [-1 for domino in domino_tiles]
slices = [draw_filling(result)]
for domino in reversed(reversed_order):
used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]
domino_color = len(used_colors)
for i, color in enumerate(sorted(set(used_colors))):
if i != color:
domino_color = i
break
if domino_color < 5:
colors[domino] = domino_color
for x, y in domino_tiles[domino]:
result[x][y] = domino_color
slices.append(draw_filling(result))
continue
# Начиная отсюда код я не тестировал, не нашел примера
c = 0
other = [other for other in domino_neighbours[domino] if colors[other] == c]
visited = set([other])
q = Queue()
q.put(other)
domino_was_reached = False
while not q.empty():
cur = q.get()
for other in domino_neighbours[cur]:
if other == domino:
domino_was_reached = True
break
if color[other] == c or color[other] == c + 1 and other not in visited:
visited.add(other)
q.put(other)
if not domino_was_reached:
for other in visited:
color[other] = color[other] ^ 1
for x, y in domino_tiles[other]:
result[x][y] = color[other]
color[domino] = c
for x, y in domino_tiles[domino]:
result[x][y] = c
slices.append(draw_filling(result))
continue
# Проделываем тоже самое для 2 и 3.
c = 2
other = [other for other in domino_neighbours[domino] if colors[other] == c]
visited = set([other])
q = Queue()
q.put(other)
domino_was_reached = False
while not q.empty():
cur = q.get()
for other in domino_neighbours[cur]:
if other == domino:
domino_was_reached = True
break
if color[other] == c or color[other] == c + 1 and other not in visited:
visited.add(other)
q.put(other)
for other in visited:
color[other] = color[other] ^ 1
for x, y in domino_tiles[other]:
result[x][y] = color[other]
color[domino] = c
for x, y in domino_tiles[domino]:
result[x][y] = c
slices.append(draw_filling(result))
return result, slices
Если вы собираетесь использовать этот код, то обратите внимание, что там происходит отрисовка каждого шага — это было нужно для анимации, что сильно замедляет алгоритм. Если вам нужна только конечная покраска, то уберите весь код, задействующий переменную slices.
Ну и наконец попробуем один из примеров, который был чуть раньше
domix32
Настолько известная, что я впервые о ней услышал. Какой-то сложный способ объяснить можно ли замостить шахматную поверхность доминошками. Понятно, что есть условная задача замощения максимальным доступным количеством этих домино, только не дано критерия для замощения случаев когда необходимый инвариант не соблюден.
Если попытаться класть домино на шахматную поверхность, то можно увидеть, что она будет затрагивать ровно одну белую и ровно одну черную клетку, что является инвариантом для полного замощения. Соотвественно, чтобы узнать можно ли замостить полностью произвольную форму шахматной поверхности достаточно посчитать равняется ли количество черных клеток количеству белых. Популярная конфигурация на КДПВ с вырезаными углами удаляет две белых клетки на белой диагонали, поэтому замостить домино полностью нельзя. Вторая конфигурация не замощается полностью по тому же принципу.
malkovsky Автор
Ровно это объяснение я даю в самом начале под спойлером, во второй конфигурации 16 белых и 16 черных клеток
petropavel
во второй надо на угол смотреть. левый верхний, где квадрат 3х3 плюс еще две клетки, примыкающие справа. Там 6 черных и 5 белых. Чтоб его можно было накрыть, нужно положить как минимум одну доминошку, которая накрывает черную клетку в этой фигуре и белую клетку рядом. Но все соседние клетки черные, то есть так доминошку положить нельзя.
domix32
Да, я похоже разучился считать. Я в первый раз насчитал 17 черных. Посыпаю голову пеплом
malkovsky Автор
Ничего страшного, бывает