class TicTacToe:
    def __init__(self):
        self.grid = [" " for _ in range(9)]
        self.human = "O"
        self.ai = "X"
        
    def __str__(self):
        return'\n'.join(' | ' .join(self.grid[3 * i: 3 * (i + 1)]) for i in range(3))

    def available(self):
        return [i for i in range(9) if self.grid[i] == ' ']

    def make_move(self, player, pos):
        if self.grid[pos] == ' ':
            self.grid[pos] = player
            return True
        return False

    def draw(self):
        return all(c != ' ' for c in self.grid)

    def check_winner(self):
        for player in (self.human, self.ai):
            if any(self.grid[x] == self.grid[x + 1] == self.grid[x + 2] == player for x in (0, 3, 6)) or \
                any(self.grid[x] == self.grid[x + 3] == self.grid[x + 6] == player for x in (0, 1, 2)) or \
                self.grid[0] == self.grid[4] == self.grid[8] == player or \
                self.grid[2] == self.grid[4] == self.grid[6] == player:
                    return player
        return None

    def gameover(self):
        return self.draw() or self.check_winner() is not None

    def minimax(self, depth, _max_) :
        winner = self.check_winner()
        if winner == self.ai:
            return 1
        if winner == self.human:
            return -1
        if self.draw():
            return 0

        if _max_:
            best_score = float('-inf')
            for move in self.available():
                self.grid[move] = self.ai
                score = self.minimax(depth + 1, False)
                if score > best_score:
                    best_score = score
                self.grid[move] = " "
            return best_score
            
        else:
            best_score = float("inf")
            for move in self.available():
                self.grid[move] = self.human
                score = self.minimax(depth + 1, True)
                if score <  best_score:
                    best_score = score
                self.grid[move] = " "
            return best_score

    
    def get_best_move(self):
      best_score = float("-inf")
      best_move = None
      for move in self.available():
          self.grid[move] = self.ai
          score = self.minimax(0, False)
          if score > best_score:
              best_score= score
              best_move = move
          self.grid[move] = " "
      return best_move


# game = TicTacToe()
# game.make_move('X', 1)
# game.make_move('O', 2)
# m = game.get_best_move()
# print(m)
# game.make_move("X", m)
# game.make_move('O', 7)
# m = game.get_best_move()
# print(m)
# game.make_move('O', 5)
# m = game.get_best_move()
# game.make_move("X", m)
# game.make_move('O', 0)
# m = game.get_best_move()
# game.make_move("X", m)
# print(m)
# print(game)

# print(game.check_winner())

axes = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]

def isWin(board):
    return any("".join(board[p] for p in axis) in ["XXX","OOO"] for axis in axes)

def validBoards(board="."*9,player=None):
    if player == None:
        yield board  # count the empty board
        for b in validBoards(board,player="X"): yield b # X goes 1st
        for b in validBoards(board,player="O"): yield b # O goes 1st
        return
    opponent = "XO"[player=="X"]
    for pos,cell in enumerate(board):
        if cell != ".": continue
        played = board[:pos]+player+board[pos+1:] # simulate move
        yield played                              # return the new state
        if isWin(played): continue                # stop game upon winning
        for nextBoard in validBoards(played,opponent):
            yield nextBoard # return boards for subsequent moves
c = 0
for b in validBoards():
    c += 1
print(c)