盤面 が与えられた時の遷移の仕方が 通りであるとすると,以下が成り立ちます.
以上を再帰関数によって実装すれば良いです.盤面の状態は配列や 進数を用いて管理することができます.
xxxxxxxxxx
memo = {}
lines = [[0,3,6],[1,4,7],[2,5,8],[0,1,2],[3,4,5],[6,7,8],[0,4,8],[2,4,6]]
def end(x):
for i,j,k in lines:
if x>>i&1 and x>>j&1 and x>>k&1:
return True
return False
def f(x):
if x in memo:
pass
elif end(x):
memo[x] = 1
else:
ans = 0
for i in range(9):
if not x>>i&1:
ans += f(x+(1<<i))
memo[x] = ans
return memo[x]
S = ''
for _ in range(3):
S += input()
X = 0
for i in range(9):
if S[i]=='o':
X += 1<<i
print(f(X))