Копай в динамическое программирование.
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))))
