Задача с замощением прямоугольной области L образной плиткой

Question

[Rapt]

Имеется задача:
Требуется ввести длину, ширину области. Вывести количество всех возможных вариантов мощения.

Примеры:
1. Ввод - L = 3, W = 4
Вывод - 4

2. Ввод - L = 69, W = 2
Вывод - 8388608

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

Answer 1

[Илья Попов]

Для решения задач о покрытии есть специальный "Алгоритм X" Дональда Кнута.
На хабре есть хорошая статья на эту тему: habrahabr.ru/post/194410

Comments

[Rapt]

Спасибо, почитаем!

Answer 2

[Rapt]

На другом форуме мне ответили как решить эту задачу комбинаторно, вот код:

# length % 3 = 0; width % 2 = 0
def calculate(length, width):
    degree = (length / 3) * (width / 2)
    print(2 ** degree)
 
if __name__ == "__main__":
    length = input("Enter L: ")
    width = input("Enter W: ")
    
    length = int(length)
    width = int(width)
    
    if length % 3 == 0:
        if width % 2 == 0:
            calculate(length, width)
        else:
            raise AssertionError("Wrong data!")
    elif length % 2 == 0:
        if width % 3 == 0:
            calculate(width, length)
        else:
            raise AssertionError("Wrong data!")
    else:
        raise AssertionError("Wrong data!")
    input()

Площадь двух соединённых плиток 2*3=6 можно взять за единицу, причём плитки могут соединятся двумя способами, а следовательно каждая полученная единица площади может принимать 2 состояния. Число всех состояний для двух единиц 2*2, для трёх 2*2*2 (формула комбинаторики для размещения из n по m), то есть в итоге 2 в степени количества единиц. Переменной degree присваивается количество данных единиц, после чего выводится 2 в степени degree.

Также спасибо @encyclopedist за познавательную статью! По ней сделать решение будет намного интересней!

Answer 3

[Максим Васильев]

Можно попробовать заполнять обасть по рядам.
Каждый ряд разбивать на отрезки (длинной 1 или 2), относящиеся к одной плитке.
Каждое заполнение будет порождать ограничения (шаблон) для заполнения следующего ряда.

Конкретно, каждый новый (не из шаблона) отрезок порождает для следующего ряда два варианта заполнения в смежных клетках.

[_][2][2][_]
[_][1][_][_]

[_][2][2][_]
[_][_][1][_]

[_][_][1][_][_]
[_][2][2][_][_]

[_][_][1][_][_]
[_][_][2][2][_]

Ну только хранить это надо чуть хитрее, чем просто клеточки.

Comments

[Rapt]

Делал подобное - разбивал строки по очереди на 1 и 2, но как-то вдруг забросил, вот код:

w = int(input('Введи w: '))
l = int(input('Введи l: ')) + 1
b = [['[]'] * l] * w
f = 0
n = 0
for i in range(0,w):
    for r in range(0,l):
        n = 0
        while n == 0:
            if f == 0:   #Флаг 0?
                if r == l-1:
                    f = 1
                    print()
                    n = 1
                else:
                    b[i][r] = '[*]'
                    print (b[i][r], end ='')
                    n = 1
            elif f == 1:   #Флаг 1?
                if r == l-1:
                    f = 0
                    print()
                    n = 1
                else:
                    b[i][r] = '[*'
                    f = 2
                    print (b[i][r], end ='')
                    n = 1
            elif f == 2:    #Флаг 2?
                if r == l-1:
                    b[i][r] = '  *]'
                    f = 0
                    print()
                    n = 1
                else:
                    f = 1
                    b[i][r] = '  *]'
                    n = 1
                    print (b[i][r], end ='')

[Максим Васильев]

Вам нужно перебирать все варианты заполнения ряда, поэтому рекурсия неизбежна.
Причём лютая, поскольку каждый сегмент пораждает 2 шаблона следующего ряда.

[Максим Васильев]

не. получается както очень уж сложно