I certainly think that you could solve a puzzle and still have it down as meditation. In fact, that's sort of what a zen koan is. However, a koan would be designed to be tough to crack, but simple in structure (as opposed to complex). There's something to be said for learning to operate the brain in ways that are different to the sort of logical, problem solving kind of operational state that I'm sure many here (myself included) spend most of their time in. A koan is designed to make that part tired until it gives up. In that way, the inability to make progress with the puzzle itself is a design feature of a koan. But working on it produces a sort of meta-progress that has to do with the mind. Meditation is weird in that way, in that it's not about learning to play the piano, but learning to play the piano player. So to speak.
Also, boredom goes away eventually. Single minded, laser focus attention is one thing that this practice cultivates, and the kind of focus that I'm talking about is mutually exclusive with boredom.
Also, the shit your brain will make up and entertain you with once the chatter dies down is absolutely fascinating all in itself.