Замощение доминошками

[domix32]

задача о максимальном паросочетании

Настолько известная, что я впервые о ней услышал. Какой-то сложный способ объяснить можно ли замостить шахматную поверхность доминошками. Понятно, что есть условная задача замощения максимальным доступным количеством этих домино, только не дано критерия для замощения случаев когда необходимый инвариант не соблюден.
Если попытаться класть домино на шахматную поверхность, то можно увидеть, что она будет затрагивать ровно одну белую и ровно одну черную клетку, что является инвариантом для полного замощения. Соотвественно, чтобы узнать можно ли замостить полностью произвольную форму шахматной поверхности достаточно посчитать равняется ли количество черных клеток количеству белых. Популярная конфигурация на КДПВ с вырезаными углами удаляет две белых клетки на белой диагонали, поэтому замостить домино полностью нельзя. Вторая конфигурация не замощается полностью по тому же принципу.

[malkovsky]

Ровно это объяснение я даю в самом начале под спойлером, во второй конфигурации 16 белых и 16 черных клеток

[petropavel]

во второй надо на угол смотреть. левый верхний, где квадрат 3х3 плюс еще две клетки, примыкающие справа. Там 6 черных и 5 белых. Чтоб его можно было накрыть, нужно положить как минимум одну доминошку, которая накрывает черную клетку в этой фигуре и белую клетку рядом. Но все соседние клетки черные, то есть так доминошку положить нельзя.

[domix32]

Да, я похоже разучился считать. Я в первый раз насчитал 17 черных. Посыпаю голову пеплом

[malkovsky]

Ничего страшного, бывает

[cherv2]

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

[malkovsky]

Я про такую задачу мало что знаю, попробуйте посмотреть вот эту статью

[AKomarov]

спасибо за статью
Заинтересовала не столько задача и ее решение, сколько matplotlib. не щупал его еще. вроде бы все просто и красиво, но не могу понять ваш код:

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))
        ....
        plt.close(fig)
        return fig
    else:
        return None

зачем возвращать закрытый объект fig? разве с ним потом что-то можно сделать?

[malkovsky]

Да, fig можно отрисовать/сохранить. Но в моем случае дело немного в другом: если бы мне нужно было просто отрисовать фигуру, то достаточно было бы просто написать там `plt.show()`, но у меня была цель еще и как-то проанимировать алгоритмы, для этого я сохранял fig в список и потом анимировал его с помощью ipywidgets.