解説

盤面 $S$ が与えられた時の遷移の仕方が $f(S)$ 通りであるとすると，以下が成り立ちます．
　

• $S$ が【終了条件】を満たす時，$f(S)=1$
• $S$ が【終了条件】を満たさない時，$S$ の空きマスに石を $1$ つ置くことで遷移する可能性がある盤面を $S_1,S_2,\dots,S_k$ とすると $f(S)=\displaystyle\sum_{i=1}^{k}f(S_i)$

以上を再帰関数によって実装すれば良いです．盤面の状態は配列や $2$ 進数を用いて管理することができます．