1590s, pusle "bewilder, confound, perplex with difficult problems or questions," possibly frequentative of pose (v.) in obsolete sense of "perplex" (compare nuzzle from nose). To puzzle (something) out "resolve or discover by long cogitation or careful investigation" is by 1781. Related: Puzzled; puzzling.
c. 1600, "state of being puzzled," from puzzle (v.); meaning "perplexing question, difficult problem" is from 1650s; that of "a toy contrived to test one's ingenuity" is from 1814. Puzzle-ring "number of small rings intertwined inseparably with one another that can be arranged as a single ring" is by 1877.