Sure, that's a valid way of looking at puzzles.
But let me ask you: why isn't exploration part of the story too? Stories aren't just about conflicts, they're also about settings. If I read a short story which paints a vivid picture of a world the character's a part of, and that world's really interesting, I say "Great story!". Why make the division between environments and activities in those environments, when they're all just parts of the story?
For that matter, what about pixel hunts? How is that not part of the story? Isn't the character looking around for something to use part of that character's story? You create a collection of random junk, only for that junk to turn out to be useful in the end. That might not be a particularly
compelling story, but hey, it's a story.
What about minigames? Aren't those a part of the story?
Have I confused you yet? Then my work here is done!