Recursion, Catalan Numbers & Generating Functions · Hard problem

Eight people each choose a floor from $\{1,2,3,4\}$, forming a sequence $s_1,s_2,\dots,s_8$. How many such sequences satisfy $|s_{i+1}-s_i|\le 1$ for every $i$?