隣り合う2桁が3の倍数にならない条件は，桁の値の和が3で割り切れないことと同値です（$10\\equiv1\pmod3$なので）。したがって各桁を剰余クラス $0,1,2$ に置き換えて，隣接するクラスの和が $0$ にならない列を数え，かつ全体の和が $0$ となるものに対応する実際の桁の取り方を掛け合わせればよいです。具体的には長さ $k(\ge2)$ の位置における各クラスの桁の選び方の個数は次のとおりです：クラス $0$ は先頭以外で4通り（0,3,6,9），先頭では0を除いて3通り（3,6,9），クラス $1,2$ はそれぞれ3通り（1,4,7 と 2,5,8）。これを使って次の漸化式で動的計画法により数え上げます。位置 $i\ (1\le i\le N)$，最後の桁の剰余を $a\in\{0,1,2\}$，これまでの和の剰余を $s\in\{0,1,2\}$ として状態数を

DP[i][s][a] と定め，初期条件は i=1 で DP[1][a][a]=3（$a=0,1,2$），遷移は

DP[i+1][(s+b)\bmod3][b] += DP[i][s][a] * c(b) （ただし a+b

ot\equiv0\pmod3）

で，ここで $c(0)=4$（2桁目以降），$c(1)=c(2)=3$ です。最後に答は DP[N][0][0]+DP[N][0][1]+DP[N][0][2] になります。

この方法で逐次計算すれば任意の $N(\ge3)$ について具体的な個数が得られます。例えば実際に計算すると $N=3$ のときは 162 個，$N=4$ のときは 1218 個となります（一般 $N$ については上のDPで簡単に求まります）。