Кто-либо видел, что программирование озадачивает подобный этому?

Основная идея заключается в следующем: при определении того, что находится в строке 3, вас не волнует, что находится в строке 1, а только то, что находится в строке 2.

Итак, давайте назовем, как построить Слой 64x1 - «сценарий строки». Вы говорите, что существует около 3300 строковых сценариев. Это не так уж плохо.

Давайте вычислим функцию:

f (s, r) = количество способов поместить номер сценария строки «s» в строку «r» и законно заполнить все строки выше «r» ".

(Я считаю, используя строку" 1 "вверху и строку" 10 "внизу)

ПРЕКРАТИТЕ ЧИТАТЬ СЕЙЧАС, ЕСЛИ ВЫ ХОТИТЕ ИЗБЕГАТЬ СПОЙЛЕР.

Теперь четко (нумеруем наши строки от 1 до 10):

f (s, 1) = 1

для всех значений «s».

Кроме того, и здесь приходит понимание, (Используется Mathematica -ish нотация)

f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]

где «подходит» - это функция, которая принимает два номера сценария и возвращает «1», если вы можете легально разместить эти две строки друг над другом, и «0» если не можешь. При этом используется понимание, потому что количество разрешенных способов размещения сценария зависит только от количества способов разместить над ним сценарии, совместимые в соответствии с «подбором».

Теперь подборки можно предварительно вычислить и сохранить в 3328 на 3328 массив байтов. Это всего лишь около 10 мегабайт памяти. (Меньше, если вы придумаете и сохраните его как битовый массив)

Ответ очевиден просто

Sum[ f(i, 10) , {i, 1, 3328} ]

Я решил аналогичную задачу для соревнования по программированию, выложив плиткой длинный коридор плиткой разной формы. Я использовал динамическое программирование: для любой панели есть способ построить ее, выкладывая по одной строке за раз. В конце каждого ряда может быть конечное число фигур. Итак, для каждого количества строк, для каждой формы я вычисляю, сколько способов сделать эту строку. (Для нижней строки есть ровно один способ создать каждую форму.) Затем форма каждой строки определяет количество фигур, которые может принять следующая строка (т.е. никогда не выравнивать пробелы). Это число конечно для каждой строки, и фактически, поскольку у вас есть кирпичи только двух размеров, оно будет небольшим. В итоге вы тратите постоянное время на каждую строку, и программа быстро завершается.

Чтобы представить форму, я бы просто составил список из 4 и 6,

Вот мой ответ. Это Haskell, среди прочего, вы получаете bignums бесплатно.

РЕДАКТИРОВАТЬ: теперь он фактически решает проблему за разумное время.

БОЛЬШЕ РЕДАКТИРОВАНИЯ: с разреженной матрицей на моем компьютере это занимает полсекунды .

Вы вычисляете все возможные способы мозаичного размещения строки. Допустим, есть N способов выложить строку плиткой. Составьте матрицу NxN. Элемент i, j равен 1, если строка i может появиться рядом со строкой j, в противном случае - 0. Начните с вектора, содержащего N единиц. Умножьте матрицу на вектор, столько раз, сколько будет высота стены минус 1, затем просуммируйте полученный вектор.

module Main where
import Data.Array.Unboxed
import Data.List
import System.Environment
import Text.Printf
import qualified Data.Foldable as F
import Data.Word
import Data.Bits

-- This records the index of the holes in a bit field
type Row = Word64

-- This generates the possible rows for given block sizes and row length
genRows :: [Int] -> Int -> [Row]
genRows xs n = map (permToRow 0 1) $ concatMap comboPerms $ combos xs n
  where
    combos [] 0 = return []
    combos [] _ = [] -- failure
    combos (x:xs) n =
      do c <- [0..(n `div` x)]
         rest <- combos xs (n - x*c)
         return (if c > 0 then (x, c):rest else rest)
    comboPerms [] = return []
    comboPerms bs =
      do (b, brest) <- choose bs
         rest <- comboPerms brest
         return (b:rest)
    choose bs = map (\(x, _) -> (x, remove x bs)) bs
    remove x (bc@(y, c):bs) =
      if x == y
         then if c > 1
                 then (x, c - 1):bs
                 else bs
         else bc:(remove x bs)
    remove _ [] = error "no item to remove"
    permToRow a _ [] = a
    permToRow a _ [_] = a
    permToRow a n (c:cs) =
      permToRow (a .|. m) m cs where m = n `shiftL` c

-- Test if two rows of blocks are compatible
-- i.e. they do not have a hole in common
rowCompat :: Row -> Row -> Bool
rowCompat x y = x .&. y == 0

-- It's a sparse matrix with boolean entries
type Matrix = Array Int [Int]
type Vector = UArray Int Word64

-- Creates a matrix of row compatibilities
compatMatrix :: [Row] -> Matrix
compatMatrix rows = listArray (1, n) $ map elts [1..n] where
  elts :: Int -> [Int]
  elts i = [j | j <- [1..n], rowCompat (arows ! i) (arows ! j)]
  arows = listArray (1, n) rows :: UArray Int Row
  n = length rows

-- Multiply matrix by vector, O(N^2)
mulMatVec :: Matrix -> Vector -> Vector
mulMatVec m v = array (bounds v)
    [(i, sum [v ! j | j <- m ! i]) | i <- [1..n]]
  where n = snd $ bounds v

initVec :: Int -> Vector
initVec n = array (1, n) $ zip [1..n] (repeat 1)

main = do
  args <- getArgs
  if length args < 3
    then putStrLn "usage: blocks WIDTH HEIGHT [BLOCKSIZE...]"
    else do
      let (width:height:sizes) = map read args :: [Int]
      printf "Width: %i\nHeight %i\nBlock lengths: %s\n" width height
             $ intercalate ", " $ map show sizes
      let rows = genRows sizes width
      let rowc = length rows
      printf "Row tilings: %i\n" rowc
      if null rows
        then return ()
        else do
          let m = compatMatrix rows
          printf "Matrix density: %i/%i\n"
                 (sum (map length (elems m))) (rowc^2)
          printf "Wall tilings: %i\n" $ sum $ elems
                  $ iterate (mulMatVec m) (initVec (length rows))
                            !! (height - 1)

И результаты ...

$ time ./a.out 64 10 4 6
Width: 64
Height 10
Block lengths: 4, 6
Row tilings: 3329
Matrix density: 37120/11082241
Wall tilings: 806844323190414

real    0m0.451s
user    0m0.423s
sys     0m0.012s

Хорошо, 500 мс, я могу жить с этим.