Задачи с доминошками на собеседованиях
По личному опыту, могу сказать, что довольно популярными на собеседованиях являются задачи, так или иначе связанные с покрытиями доминошками каких-либо поверхностей. Условия могут варьироваться, но суть у всех остается одна.
Пример 1
Имеется шахматная доска 8 на 8 клеток, левый нижний и правый верхний углы которой отрезаны. 
Можно ли полностью покрыть такую доску доминошками размера 2×1 клетку?
На доске остается четное число клеток (62), так что на первый взгляд решение возможно. Однако, давайте сделаем одну очень простую вещь:
Мы раскрасили клетки через одну. Теперь все становится очевидным. Каждая доминошка может занимать строго две клетки: одну белую и одну черную. Других вариантов не дано. Смотрим, какие клетки на доске отрезаны – обе черные, соответственно мы имеем 32 белых и 30 черных клеткок и полностью покрыть такую доску не представляется возможным.
Условия задачи могут варьироваться, но в целом, задачи на возможность-невозможность сразу бросаются в глаза.
Пример 2
Имеется большой куб сыра 3x3x3 состоящий из 27 одинаковых кубиков сыра и мышонок, который съедая один кубик принимается за соседний с ним по грани кубик сыра. Сможет ли мышонок полностью съесть весь сыр, если центральный кубик заменить на несъедобный муляж?
Задача та же самая, только в пространстве, а не на плоскости. Считаем клеточки: в изначальном раскладе это 14 на 13, после удаления центрального кубика: 14 на 12 и как следствие, решения нет.
Следующими по популярности идут задачи на подсчет количества вариантов решений.
Пример 3
Даны две доски:
На каждой вырезано по 2 клетке. Количество вариантов покрытия доминошками какой из досок больше? В обоих случаях вырезаны клетки разного цвета, так что все познания с раскраской из предыдущих примеров нам здесь не помогут. Времени на собеседованиях на задачи отводится мало, так что нужно искать какую-то зацепку. А она есть. Исключим из первого варианта все покрытия содержащие вырезанные клетки второй доски, а из второго варианта – первой. (Если так проще представить – то можно считать, что вырезанные клетки изначально покрыты доминошкой – которую нельзя двигать, и, очевидно, что таким образом мы приводим доски к идентичному состоянию и количество вариантов покрытий будет тоже идентичным). После этого рассмотрим нижний угол 3 на 2 клетки. Во втором варианте, левая нижняя клетка может быть покрыта только одним способом. Сопоставим этому покрытию вариант для первой доски:
Оставшася часть за исключением этого угла идентична, соответственно и количество покрытий тоже идентично. Таким образом, каждому варианту покрытия второй доски, сопоставлен вариант покрытия первой доски. Однако в первом случае также еще возможен вариант, где все доминошки расположены вертикально, не соответветсвующий ни одному варианту второй доски. Следовательно, число вариантов покрытия доски с клетками, отрезанными в углу больше.
Пример 4
Найти количество вариантов покрытия доминошками доски 2хN клеток.
Пусть ее можно покрыть X(N) способов. Рассмотрим вариант покрытия левой верхней клетки:
Оставшуюся часть в первом случае можно покрыть X(N-1) способами, а во втором, очевидно, X(N-2).
Так как перечислены все варианты покрытия и никакие из них не будут совпадать, то получаем уравнение X(N) = X(N-1) + X(N-2)
X(1) = 1, X(2) = 2, а Х(N) будет равно N+1 числу последовательности Фибоначчи.
Пример 5
Написать программу, вычисляющую количество способов покрытия доски 3xN клеток доминошками.
Сразу скажу, возможно, для этого примера есть тоже оптимальное решение, но я перейду тут уже от частных решений к общему. По сути, все что стоит за такими задачами можно представить двудольным графом, одно из множеств вершин которого – черные клетки, а другое – белые. Покрытие доминошками – есть не что иное как максимальное паросочетание такого графа. Для его поиска могут применяться различные алгоритмы (например Куна), с подсчетом количества вариантов все несколько сложнее. В любом случае, это за пределами данной статьи.
В заключение, для демонстрации, реализация алгоритма “в лоб” на питоне:
from itertools import combinations
# формирование матрици инцидентности опущено для краткости
# оно тривиально
# Например, для доски 2×2 с номерами клеток:
# 1 2
# 3 4
# это:
# mat = [
# [0, 1, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 1],
# [0, 0, 0, 0]
#]
# 1 => 2, 1 => 3, 2 => 4, 3 => 4
# Обратные направления ( напр. 3 => 1 )
# не представляют для нас интереса
N = len(mat)
# создаем итератор со всеми парами вершин
all_edges = combinations(xrange(N), 2)
# фильтруем по матрице инцидентности
edges = [(x,y) for x,y in all_edges if mat[x][y]]
# отфильтровываем все максимальные варианты
matchings = [tuples for tuples in combinations(edges, N/2) \
if len(set(reduce(lambda x, y: x+y, tuples))) == N]
print len(matchings)
# осторожно, сложность O(N!)
Источник
Замощение доминошками
Одна из первых действительно интересных задач по математике, с которыми я столкнулся формулируется так: «из шахматной доски вырезали две противоположные по диагонали угловые клетки, можно ли оставшуюся часть разрезать на «доминошки» — фигурки из двух клеток, у которых одна сторона общая?». У нее очень простая формулировка, в отличие от великой теоремы Ферма она имет простое, элегантное, но неочевидное решение (если вы знаете решение задачи, то попробуйте применить его к фигуре справа).
В этой статья я расскажу о нескольких алгоритмах, которые умеют покрывать доминошками произвольную клетчатую фигуру на плоскости, если это возможно, находить ситуации, когда это невозможно и считать количество возможных замощений доминошками.
Nota bene! Материал этой статьи — это усеченный вариант вот этого jupyter-notebook, все картинки и анимации, которые вы увидите в статье, сгенерированы кодом из этого ноутбука (правда анимаций не будет в github предпросмотре). К слову, картинки из заголовка также сгенерированы с помощью python/matplotlib
Сделать это невозможно, и этому есть красивое и простое объяснение:
- На оставшейся части доски 30 черных и 32 белых клетки
- Каждая доминошка состоит из одной черной и одной белой клетки
- Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток
Динамическое программирование по профилю
Про динамического программирования есть статья на хабре, которая даже содержит пример с покрытием доминошками, я немного расширю этот пример.
Основная суть динамического программирования заключается в том, чтобы придумать для исходной задачи какие-то промежуточные подзадачи так, чтобы их можно было легко друг через друга выразить. Например, если мы хотим вычислить двухсотое число Фибоначчи, то для этого можно последовательно вычислить все числа Фибоначчи вплоть до нужного нам применяя соотношение
Аналогично можно вычислить число «сочетаний» 
, воспользовавшись одним из следующих рекуррентных соотношений
Для задачи «можно ли замостить доминошками прямоугольник 
?» к сожалению подобных простых соотношений не существует. Тем не менее, если мы рассмотрим более широкий класс фигурок, то такие соотношения уже станут возможными, главное чтобы это не были слишком маленькие классы и динамическое программирование не превратилось в банальный перебор.
Посмотрим на следующий класс фигурок: у нас есть прямоугольник 
, на строке 
присутствуют первые 
клеток, остальные задаются профилем, на строке 
первые клеток задаются профилем, остальные не участвуют. Профиль — это последовательность нулей и единичек длины 
: если на 
-ой позиции профиля единичка, это значит что в этой фигуре есть соответствующая клетка, всего профилей 
(красные клетки — единички, синие — нули).
Профиль однозначно задается числом 
(его бинарное представление вплоть до разрядов является последовательностей нулей и единичек).
Прямоугольник соответствует фигуре с 
, 
и нулевым профилем. На фигурках такого типа мы можем считать две основные функции
- Максимальное возможное число покрытых доминошками клеток в этой фигуре
- Количество способов полностью покрыть доминошками эту фигуру
Давайте обозначим за 
количество способов замостить такую фигурку, тогда 
и при этом выражается через сумму нескольких 
, по большому счету переход от к 
— это перебор трех случаев: поставить вертикальную доминошку, если это возможно
горизонтальную доминошку, если это возможно
и пропустить занятую клетку. В случае, если мы пытаемся понять, какое максимальное число клеток фигурки возможно замостить, то сумма заменяется на максимум и добавляется один несложный переход — пропуск свободной клетки. Важным моментом также является то, что мы можем заранее вырезать несколько клеток, принципиально от этого ничего не поменяется.
Давайте теперь попробуем реализовать это (кода будет много, так что большинство я вынесу в спойлер). Зададим интересующий нас прямоугольник как множество строк из точек и решеток (точка — свободная клетка, решетка — занятая), пока все клетки будут свободными, потом потихоньку будем какие-нибудь вырезать
Сверяемся с википедией, пока все в порядке. Давайте еще на всякий случай проверим, количество способов замостить полоску 
— должно получиться число Фибоначчи.
Что ж, поехали дальше, проверим на доске с вырезанными углами
Супер. Допустим вычислять количество мы научились, может найдем хотя бы одно конкретное замощение для наглядности?
Слишком просто, давайте вырежем несколько клеток
Попробуем теперь сделать тоже самое для замощения максимальной возможной части фигуры
И попробуем фигурку из заголовка
Опа! Не получилось, в общем так и должно было быть. Прежде, чем пойти дальше пару слов о сложности алгоритмов. Всего фигурок 
, все переходы константные, отсюда асимптотика 
, которая может быть улучшена до 
если добавить транспонирование в случае, если 
. Построение конкретного замощения в приведенных реализациях имеет сложность , но можно сделать так, чтобы было просто 
, но это банально больше кода.
Замощение с помощью решения задачи о максимальном паросочетании
Возвращаясь к черно-белой раскраске как на шахматной доске можно заметить интересную интерпретацию задачи замощения доминошками. Давайте посмотрим на граф, в котором клетки фигуры — это вершины, ребрами соединены клетки, имеющие общую сторону. Так вот, доминошка в этом графе — это как раз ребро. Если раскрасить граф в шахматном порядке, то внезапно можно обнаружить, что этот граф — двудольный, черные — одна доля, белые — другая. Если переформулировать задачу замощения наибольшего числа клеток в терминах этого графа, то получается, что нужно найти максимальное по размеру множество ребер такое, чтобы вершины являлись концом не более одного ребра. В общем то, это довольно известная задача о максимальном паросочетании. Давайте попробуем её применить для решения этой задачи, тут получится даже с анимацией, приведу базовый алгоритм Куна для нахождения максимального паросочетания.
Здесь даже получается проанимировать процесс
Суть алгоритма Куна (да и любого другого алгоритм для нахождения максимального паросочетания) заключается в нахождении «аугментирующих путей». В терминах доминошек это цепочка из доминошек, у которой рядом с доминошками на концах есть по свободной клетке, такие цепочки можно заменить на цепочки большей длины, охватывающие те же клетки и заполняя две свободные клетки рядом с концами цепочки. Более того, основное утверждение, на котором работают все алгоритмы нахождения максимального паросочетания, заключается в том, что если такой цепочки не удается найти, то значит большего замощения нам не получить.
UPD. Для последнего примера простое обоснование на основе черно-белой раскраски не работает. Насколько мне известно, есть два общих критерия для существования полного замощения:
- Теорема Холла (теорема о свадьбах)
Проверка условий этой теоремы вычислительно сложнее, чем построить максимальное паросочетание. - Условие высоты Тёрстона про это я мало что знаю
Недавно меня навели на очень интересную статью про замощения, там в том числе описывается про использовании групп для доказательства невозможности различных замощений.
Бонус! Раскраска планарного графа в 5 цветов.
Для визуализации замощения я использовал отдельный цвет для каждой доминошки. К сожалению некоторые цвета не очень хорошо смотрятся, а некоторые плохо контрастируют друг с другом. В этом случае подобрать цвета для хорошего контраста не так уж просто, особенно если доминошек много. Зато можно использовать меньше цветов: доминошки, которые не находятся рядом друг с другом можно раскрасить в одинаковый цвет, тогда визуально все еще будет понятно, как именно выглядит покрытие. В общем то это классическая задача о раскраске вершин планарного графа. Любой планарный граф можно покрасить в 4 цвета, правда хорошего алгоритма для такой покраски нет. Зато есть довольно простой алгоритм для покраски в 5 цветов, когда правда все еще много, и я его мало тестировал (если необходим 5ый цвет, то возможны баги)
Если вы собираетесь использовать этот код, то обратите внимание, что там происходит отрисовка каждого шага — это было нужно для анимации, что сильно замедляет алгоритм. Если вам нужна только конечная покраска, то уберите весь код, задействующий переменную slices.
Ну и наконец попробуем один из примеров, который был чуть раньше
Источник
