I've been doing a lot of puzzles lately, both authoring and solving, and I'm starting to identify common trends and themes. Here's a first crack at a taxonomy of puzzle elements:

• Constraint Satisfaction - This is where you have a lot of options of how to place / name / order elements, and a few rules governing how you'll do it. The traditional gridded logic puzzle fits into this category, as does Sudoku. Perhaps this one can be split apart further for better precision
• Physical Construction - This is where you have a set of tangible objects which need to be assembled without instructions. The jigsaw puzzle fits into this category, as do puzzles like tangrams.
  
• Mapping - This is where information is presented in one form, and needs to be converted into another. Puzzlehunt-style puzzles rely heavily on this as a means of arriving at a final solution - for example, a Go board where the stones should be read as Braille letters. A few common mapping techniques:
• Braille
• NATO Alphabet (Alpha, Bravo, Charlie, Delta...)
• Semaphore
• Naval Flag Code
• Pigpen Cipher
• Letter Substitution (There are a few common forms of letter substitution)
• Caesar Shifts, the most popular being the symmetric ROT-13
• Atbash Cipher
• Cryptograms (Symmetric or Asymmetric)
• (Note that cryptograms are different from most letter substitutions in that they require you to derive the mapping. This means they're more suitable for longer passages of text where the solver can be expected to make reasonable inferences (the fact that a common three-letter word is "the," for example.))
• Cryptography - As distinct from mapping, this is where information has deliberately been encrypted, either with a secure method (and presumably the puzzle is to obtain a key), or with an insecure method (and presumably the puzzle is to exploit the flawed encryption). I can only think of a few good uses of this in a puzzle that I've seen.
  
• Physical Challenge - Not really a puzzle, but I include it because at puzzling events it's often presented alongside puzzles, or as part of one. Generally when physical challenge is incorporated in a puzzle, it's in the form of having to physically enact a solution to another class of puzzle, or physically gather data or other components for a puzzle.
• Metapuzzles - This describes a class of puzzles that cannot be solved without some amount of data that is not present initially, but is obtained by solving other puzzles.
• Maze - We all know what a maze is, I hope. Is this just a type of constraint satisfaction, or is there something else to it? I think it's a distinct class of puzzle - it's not generally the constraints that make a maze interesting, but the fact that it's challenging to reduce the complexity enough to solve it.
• Information Surplus / Needle-in-a-haystack - This is the class of puzzles that have way too much information at hand, often to conceal a simpler puzzle of another form. (For example, a story which uses one NATO word per paragraph - strip away the extraneous information, and this is just a mapping from NATO words to letters.
• Trivia - Puzzles that rely on some amount of cultural knowledge, such as a crossword.
• Wordplay - Puzzles that rely on the lexical properties of words, such as anagrams or beheadments.
• Recognition - This is another barely-a-puzzle that's usually incorporated into another puzzle - recognizing an object or place on the basis of a representation. (For a very pure example, consider Games Magazine's recurring "Eyeball Benders" feature, with photographs of objects in extreme close-up.)
• Metaphoric Analogy - This is the class of puzzle where a description of one thing actually refers to another. Riddles go here, but so does a puzzle from this year's puzzlehunt that described a set of monks with the names of the apostles battling and winning recruits in various cities - textual cues indicated that the battles were actually hands of poker, and the monks were actually the cards.

This is a first draft. What am I missing? Which categories don't make sense or need further explanation? What puzzles have you seen that you'd like me to try to analyze in this framework?

After a first round of review, I'll try to analyze some puzzles in this framework and see if it works well. My ultimate goals are to be able to use these techniques to help me design puzzles, and to give me a toolkit to look at a puzzle I'm having trouble with and try to solve it by considering all the types of puzzles I've seen before.