　一般に石が $n$ 個並べる方法が $T_n$ 通りとする．石を $n$ 個並べる方法であって，先頭がそれぞれ赤・青・黄・緑であるような方法は $T_{n-4},T_{n-3},T_{n-2},T_{n-1}$ 通りあるから，$T_n=T_{n-1}+T_{n-2}+T_{n-3}+T_{n-4}$ が成立する．$T_{1}=4$ ,  $T_{2}=7$ ,  $T_{3}=13$ ,  $T_{4}=25$ から順に計算すれば，$T_{9}=\mathbf{673}$ を得る．

----
補足：これは $T_0=T_{-1}=T_{-2}=T_{-3}=1$ として計算でき，結局テトラナッチ数列に一致する．なお，$T_{n+1}=2T_{n}-T_{n-4}$ と変形してから計算した方が早いだろう．
公式解説
https://onlinemathcontest.com/contests/omc203/editorial/4410
　赤・青・黄・緑それぞれの石が十分な数あり，これらの石あわせて $9$ 個を，赤の右隣は青，青の右隣は黄，黄の右隣は緑であるように左右一列に並べます．ただし，一番右の石が緑である必要はありません．このような条件で並べる方法は何通りありますか？