Andy_U

Копай в динамическое программирование.
UPDATE
> А потом, увы, перебор, если я правильно понял условие задачи
хе-хе, не хочет копать Andy_U

# строим всевозможные комбинации кирпичей длинной 25
nxt, rows = [(3,), (4,)], []
while nxt:
    cur, nxt = nxt, []
    for row in cur:
        for brick in 3, 4:
            le = row[-1] + brick
            if le < 23:
                nxt.append(row + (le,))
            elif le == 25:
                rows.append(frozenset(row))

# все комбинации длинны 25 лежат в листе rows, т.е. занумерованы
# строим лист, где по номеру каждой комбинации
# лежит список номеров неконфликтующих комбинаций
friendly_row = [[i for i, b in enumerate(rows) if not (a & b)] for a in rows]

nxt = [1] * len(rows)  # в первом слое может лежать любая комбинация
for _ in range(10 - 1):  # есть же один слой
    cur, nxt = nxt, [0] * len(rows)
    for i, n in enumerate(cur):
        for j in friendly_row[i]:
            nxt[j] += n
print(sum(nxt))

UPUPDATE: разгоним рекурсивное решение

cache = {}

def build_tail(height, row):
    if height == 9:
        return neighbours_number[row]
    if (height, row) in cache:
        return cache[height, row]
    cache[height, row] = res = sum(build_tail(height + 1, i) for i in acceptable_neighbours[row])
    return res

rows = {i for i in itertools.permutations([3, 3, 3, 4, 4, 4, 4], 7)} | \
       {i for i in itertools.permutations([3, 3, 3, 3, 3, 3, 3, 4], 8)}

acc_rows = [set(itertools.accumulate(row[: -1])) for row in rows]
acceptable_neighbours = [[i for i, b in enumerate(acc_rows) if not (a & b)] for a in acc_rows]
neighbours_number = [len(i) for i in acceptable_neighbours]

print(sum(build_tail(1, i) for i in range(0, len(acc_rows))))