上の行から順番に値を埋めていくことを考えます。 現在 \(i\) 行目に着目していることにします。\(i-1\) 行目と \(i-2\) 行目に書き込まれた値がわかっており、\(i-2\) 行目以前は問題文中の条件を満たしているものとします。 マスの個数は \(12\) 個なので直前 \(2\) 行の値の状態は最大で \(2^{12}\) 通り存在します。 これらの状態それぞれについて、\(i\) 行目への値の書き込み方を試し、\(i-1\) 行目が問題文中の条件に違反しないかどうかを判定しながら更新すればよいです。

この bitDP は行数を \(N\)、列数を \(M\) として \(O(NM 8^{M})\) で実行可能で十分高速です。 余談ですが、この問題は \(O(NM 4^{\min(N,M)})\) で解くこともできます。