Untitled

def is_winner(board, player):
    """Check if the given player has won."""
    # Check rows
    for i in range(0, 9, 3):
        if board[i:i+3] == [player] * 3:
            return True
    
    # Check columns
    for i in range(3):
        if board[i::3] == [player] * 3:
            return True
    
    # Check diagonals
    if board[0::4] == [player] * 3:
        return True
    if board[2:7:2] == [player] * 3:
        return True
    
    return False

def is_valid_game_state(board):
    """
    Check if the game state is valid:
    - X's count should be equal to or one more than O's count
    - There shouldn't be two winners
    """
    x_count = board.count('X')
    o_count = board.count('O')
    
    # Check if moves are in valid sequence
    if not (x_count == o_count or x_count == o_count + 1):
        return False
    
    # Check if both players won (impossible)
    x_won = is_winner(board, 'X')
    o_won = is_winner(board, 'O')
    if x_won and o_won:
        return False
    
    # If O won, X shouldn't have played last
    if o_won and x_count > o_count:
        return False
    
    # If X won, they must have played last
    if x_won and x_count <= o_count:
        return False
    
    return True

def get_valid_moves(board):
    """Get list of empty positions."""
    return [i for i, val in enumerate(board) if val == '']

def is_game_over(board):
    """Check if the game is over (winner or full board)."""
    return is_winner(board, 'X') or is_winner(board, 'O') or '' not in board

def count_all_games():
    def dfs(board, is_x_turn):
        # If this is an invalid game state, backtrack
        if not is_valid_game_state(board):
            return 0
        
        # If game is over, we found a valid completed game
        if is_game_over(board):
            return 1
        
        # Try all possible next moves
        count = 0
        player = 'X' if is_x_turn else 'O'
        for move in get_valid_moves(board):
            new_board = board.copy()
            new_board[move] = player
            count += dfs(new_board, not is_x_turn)
        
        return count
    
    # Start with empty board, X plays first
    initial_board = [''] * 9
    return dfs(initial_board, True)

def print_example_game():
    """Print an example valid game for verification."""
    board = [''] * 9
    moves = [0, 4, 1, 3, 2]  # X wins with top row
    for i, move in enumerate(moves):
        board[move] = 'X' if i % 2 == 0 else 'O'
        print(f"\nMove {i+1}:")
        for row in range(3):
            print(' '.join(cell if cell != '' else '_' for cell in board[row*3:(row+1)*3]))
    return board

if __name__ == "__main__":
    total_games = count_all_games()
    print(f"\nTotal number of valid completed games: {total_games}")
    
    print("\nExample of a valid game (X wins):")
    print_example_game()