I'd suggest that maybe "puzzle" has a slightly different connotation than "problem".

I think a "puzzle" is a concrete instance of a more formal and abstract "problem".

So I don't think claiming to solve an instance (or many!) of a problem is inappropriate.