Compound of head + scratcher. Literal sense 1873, figurative 1971.
head-scratcher (plural head-scratchers)