a puzzle - a problem(s), the (common) solution of which is not known by any known paradigm or theory..
a paradox - problem, whose intersubjectivelly accepted solution exists already, but it contradict another solution or intuitive approach.