When and where did Brainteasers originate?

Huh?

They are probably as old as civilization, and will have developed independently in many places.

Riddles (usually involving allegory or metaphor) are known to have existed in ancient Greece and Judea. Examples are the riddle of the Sphinx, and the riddle of the lion invented by Samson. Rebuses and anagrams were also known in ancient Greece and probably elsewhere in the ancient world as well. Mathematical puzzles go back to ancient Egypt and Babylonia.