Задача про стену и кирпичи. Как решить?
Ну, я бы начал с решения уравнения в целых положительных числах  3*x+4*y=25. Решений две штуки: (x=3, y=4) и (x=7, y=1). Т.е. у нас 2 класса рядов. Вариантов расположения кирпичей в первом классе 7!/(3!*4!)=35, во втором классе 8!/(7!*1!)=8. Итого 35+8=43 вариантов ряда. Генерируем их. Теперь заполняем матрицу размером 43*43, ставя единички там, где ряды кирпичей (один в столбце, второй в колонке) совместимы с условием отсутствия общей вертикальной щели (для каждого варианта ряда строим множество {L[1], L[1]+L[2], ...  L1+...L[N-1]}, потом очевидно, что ряды "совместимы", если пересечение множеств пустое). Это все быстро и памяти немного надо. На питоне - 30 строк. Кстати, в построенной матрице нулей сильно больше, чем единиц. несколько рядов просто ни с одним другим не совместимы. А потом, увы, перебор, если я правильно понял условие задачи. Типа как в классической задаче "поставить 8 ферзей на шахматную доску, чтобы они не били друг друга". 
Update:
Код на питоне 3.4.3, решающий задачу перебором (кроме получения "классов" рядов),  приведен ниже:import itertools


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


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] # copied from @bobrovskyserg
neighbours_number = [len(i) for i in acceptable_neighbours]

print(sum(build_tail(1, i) for i in range(0, len(acc_rows))))
Время решения ~40 секунд, ответ bobrovskyserg подтверждаю.  Пошел разбираться с его алгоритмом...
Строите матрицу перехода между рядами (43х43, как описано в ответе Andy_U ), потом возводите её в 9-ю степень (поскольку у нас 9 переходов) и считаете сумму всех элементов (поскольку первый и последний ряд могут быть любыми). Всё.
  Работает для любого числа рядов, хоть для триллиона :) Только потребуется быстрое возведение в степень.
  Но это будет число способов построить стену. Если имелось в виду число наборов кирпичей (сколько может быть кирпичей 3x1 и сколько 4x1), то надо подумать, как сделать проще всего.