A puzzle, as opposed to a problem, is presumably something you take pleasure in solving, otherwise why are you solving it? I don't think the answer should be so surprising as to challenge credibility, but I think it's all right if one says, "Dammit, why didn't I think of that? "

A real-life puzzle, like the ones we were discussing just now before we got on math, where you are looking for a murderer, may depend on the discovery of some arcane fact — the sort that Sherlock Holmes collected —but the answer to a regular puzzle should not involve some piece of information that is not generally known, nor susceptible to being worked out.