Задачи с доминошками на собеседованиях

По личному опыту, могу сказать, что довольно популярными на собеседованиях являются задачи, так или иначе связанные с покрытиями доминошками каких-либо поверхностей. Условия могут варьироваться, но суть у всех остается одна.

Пример 1.

Имеется шахматная доска 8 на 8 клеток, левый нижний и правый верхний углы которой отрезаны.
задача с доминошками
Можно ли полностью покрыть такую доску доминошками размера 2×1 клетку?

На доске остается четное число клеток (62), так что на первый взгляд решение возможно. Однако, давайте сделаем одну очень простую вещь:
задача с доминошками-2
Мы раскрасили клетки через одну. Теперь все становится очевидным. Каждая доминошка может занимать строго две клетки: одну белую и одну черную. Других вариантов не дано. Смотрим, какие клетки на доске отрезаны – обе черные, соответственно мы имеем 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
# формирование матрици инцидентности опущено для краткости
# оно тривиально
# Например, для доски 2x2 с номерами клеток:
#  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!)

2 Responses to “Задачи с доминошками на собеседованиях”

  1. Michael says:

    Пример 3.
    <<Однако в первом случае также еще возможен вариант, где все <<доминошки расположены вертикально,

    Это какой случай? Объясните плз, никак не доходит 🙁

  2. alexey says:

    Это так:

Leave a Reply