a taxonomy of puzzle elements

First thought: As a taxonomy, this is probably pretty good. As an analytical framework, not so much. It's too big and (for the lack of a better idiom) implementation-specific. I think you're cutting the wrong way here: identify commonalities rather than pigeon-hole.

An example of why I think this isn't quite right: take a Latin square, assign a color to each number, print it on cardboard, cut the pieces in such a way that they fit only in a manner that reassembles the original Latin square and each piece represents an element of the matrix, jumble them, and include a picture of the "modern art" (really, colored Latin square) that the solver must assemble. If I notice that the pieces correspond to elements of a Latin square, I'm doing constraint satisfaction. If I address it like a jigsaw puzzle I'm doing physical construction.

The problem? Most puzzles that I think could fit into the physical construction classification are really about constraint satisfaction and with a simple modification the reverse is generally true. (And I mean this in a more significant manner than just saying "well, this really just modeling an NP problem so it must be SAT")

Hmm. I think that your Latin square example is less a revelation of a flaw in the design than an unclear statement on my part - I don't actually believe that many puzzles at all fit neatly into one of these categories. Rather, I'm looking for the building-blocks of puzzles. For example, a recent puzzle I solved had bands whose song names could be "added" together to form other song names - e.g. Santana and Fiona Apple could be added together to get Michael Jackson (I'll leave finding the song names in question as a bit of a game; ask if you'd like it spoiled). Knowing what songs are by a particular artist is certainly trivia, but I'd argue that merging them together - and selecting song names such that they could be merged together - was constraint satisfaction. These had to be done at the same time; it's impossible to pull them apart into separate steps without being disingenuous about the way people actually solve.

As far as the idea of these categories goes, they're mostly here for three reasons: First, they're here to give me a toolkit. When I'm looking at a new puzzle, it's helpful to be able to say "this looks like it's got constraints to satisfy; these tools (whether cognitive methods, software tools or physical objects) are likely to be useful." Second, they're meant as inspiration when writing puzzles. I write puzzles for events, which means I don't generally sit around waiting for a neat idea to strike. I'm already using a rudimentary version of this list to generate ideas - "what if I took a physical puzzle, and I used a mapping between Norse gods and days of the week ?" Not all the ideas are gems, but it makes it possible to rapidly generate concepts that might make the seed of a new puzzle. Finally, and perhaps most importantly, I want this list to help me recognize the truly original when I stumble across it. If I find a puzzle that doesn't reduce to a category I already know, that means I'm getting a rare opportunity indeed - the chance to think in a completely unfamiliar way. And, once I've understood that puzzle, I can add another category, and merge a new kind of puzzle in with what I already know how to solve and write.

I do think the point about physical construction and constraint satisfaction is an interesting one, though - while I can think of a few physical puzzles that weren't about satisfying constraints, many of them do end up reducing to constraint satisfaction, and I think most of the rest are intended to be solved in a truly physical manner - by manipulating the object until an answer becomes apparent. I might end up rethinking my approach to physical puzzles; thanks!

What would a puzzle consisting of working backwards via logical inference to arrive at a conclusion? I'm thinking about retrograde chess analysis?

Also there are several types of puzzles where a ruleset is given or assumed and some seemingly impossible target is granted: matchsticks puzzles might fall into this category, but also I've seen Magic hand puzzles and Bridge hand puzzles.

I think retrograde chess is definitely constraint satisfaction. I think most other ruleset puzzles are constraint satisfaction as well, though there's a notable exception I think I should add a category for.

Puzzles where a ruleset is assumed, but not explicitly given, and where one of the assumed rules must be violated to solve the puzzle, are a category unto themselves. Let's call them false assumption puzzles. I didn't think of them in the first pass because I don't consider them very good puzzles; they tend to be about a single "a-ha!" moment, and are trivially solved once the moment is past. However, the false assumption can be a powerful element when it's part of a larger puzzle, and I ought to include it, because I do encounter it when solving.

In a minor way, I might consider card or matchstick puzzles where the target really does appear impossible to be in this category, though I think that if you don't need to violate an assumption you are actively holding ("I can't do that!") then it isn't really a very good example.

some very common ones that you left out

pixel hunt
fetch-the-item
recursive conversation tree exhaustion
and the infocom favorite: guess the verb :)

Re: some very common ones that you left out

Hrm. I actually think the next version of this should explicitly call out that it's referring to mental puzzles, I think.

None of those things actually seem to be "puzzles," per se - they're time-extending techniques that many games use in lieu of puzzles. Pixel hunt and conversation tree exhaustion could both be elements of puzzles, if the relevant item / conversation path was in some way inferable from context (I'm thinking about the absurd card game from one of the later Zorks, for example, where you needed to know that there was a certain move that would win, and then make that move), but in general those things appear with nothing but random trial to guide the player.

Guess the verb is more a limitation of the early IF medium, though I'd argue that Nord and Bert elevated it to a puzzle for one shining game..

I do a lot of work with puzzle hunts as well, though I tend to work with the MIT Mystery Hunt, and have yet to make it up to a M$ Puzzle Hunt. Here are a few thoughts based on my own observations.

I don't particularly like the way you've defined "mapping," because for the most part, it seems like straight translation. It seems more reasonable to call it such and then move simple letter-substitution ciphers over to cryptography.

However, you may want to keep the mapping category open and have "translation" as a subset or separate category. For example, there are many puzzles where a set of clues or answers must be mapped in an unexpected way or using an unexpected set. Wry Ergo Dead is a good example.

You may want to broaden "physical construction" to merely "physical manipulation," to account for puzzles are already constructed but need to be modified or perhaps deconstructed.

"Recognition" seems pretty narrowly constructed too. Either you should broaden it, or you should add some companions. I usually refer to these as "identification" and they will tend to overlap either "trivia" or "riddle." Identify music, identify books based on descriptions, identify movies based on quick sketches, etc.

"Information surplus" seems like an awkward phrase, and it implies far more chaff than is usually present. I tend to think of them as "null puzzles" based on "null ciphers." I think it's important, because it ties into the idea of mapping and indexing when the important information is buried in a much smaller amount of chaff (e.g., every answer word has a five-letter palindromic sequence).

And if you're looking at MITMH/M$PH puzzles, you really do need to address ordering and indexing. Some standard letter-pulling techniques (acrostic, telestich, diagonal) might be incorporated into the "information surplus," but indexing usually involves some outside information to direct you to pick a particular letter in a particular case. Ordering can sometimes overlap mapping (where you're mapping to an order in addition to or instead of another item), but not always.

I think you should go with "riddle" as the name for metaphorical analogy. No problem with the definition, but there's a longer history of a riddle being what you describe. (See Nick Montfort's comparison of the riddle to interactive fiction.)

I can think of a few other common elements. Recursion: applying the same solving technique to the answer to get another answer. Follow Directions: exemplified in the Duck Konundrum.

For more ideas, the traditional MITMH document is Acme's "Have You Tried . . . ?" sheet, which is available as a PDF.

Whew. Let me take this in small bite-sized chunks, because there's a lot of material in this comment.

First: Hi, nice to meet you. I'm curious how you managed to stumble across this entry without any common links via LJ-friends; it's a little bit surprising!

Regarding mapping - I think mapping-as-a-category is interesting, for the reasons you're pointing at with Wry, Ergo Dead (which I haven't solved, but I have some interesting ideas on; I might revisit this conversation once I've puzzled that one out). While most of what I jotted down is lexical, I think mappings can appear in other domains, and I'm interested in finding general techniques for approaching mapping in all its forms - for example, a recent puzzle involved mapping decimal expansions into large fractions, which then mapped to MS room numbers (which are commonly written as 55/2310, where 55 is the building and 2310 is the room). I've also seen mappings into things like colors, and part of my motivation in creating a mapping category is an intuition that this process of transforming one type of data to another is somehow generalizable across many different-appearing puzzles. I do think that it might be useful to pull out lexical mapping as a specific subset, though, given that it has additional properties and appears very frequently.

I probably do want to broaden physical puzzles to include both construction and manipulation.

I think I'm unclear in what I mean by recognition - what you're describing seems to legitimately be trivia to me, but I'm referring to cases where the act of identification, on the basis of a non-researchable property, is a critical step of the puzzle. The Eyeball Benders puzzles I mentioned before have this property, and I've seen it as an element of PuzzleHunt puzzles before: this year, one puzzle involved recognizing the exteriors of certain buildings on campus from sketches of them. In the past, I've seen a puzzle that relied on recognizing that a set of elements on the page form the shape of a flashlight. Perhaps an argument could be made that this is really trivia, but I think there's a lot of difference in how you approach a recognition puzzle (show it to lots of people, looking for the a-ha) versus a trivia puzzle (show it to lots of people and ask your favorite search engine).

I think I've been unclear with information surplus, too. I am referring to puzzles with a lot of chaff - such as the NATO example I gave, or a puzzle with many numbers, a few of which are common fractions, the rest are gibberish. These puzzles aren't all that common, but I've solved enough of them that I think they merit a category. On the other hand, I'm curious about the puzzles you think of as "null puzzles" - could you provide a few examples? It seems like you're referring to a class of puzzle that's somewhat distinct (though perhaps related?)

Ordering and indexing are definitely oversights. They're more structured than the information surplus puzzle, and they have definite techniques that lend themselves to solution. Into the next draft they go, each as its own category.

... And I'm running out of space in this comment, so I'll split it up.

... continued here:

As far as using "riddle" for the name of the class of metaphorical analogies - I think that riddles are definitely this class of puzzle, but I'm concerned about the connotation of using the word "riddle." Montfort aside, I think if I were to ask the question "is this a riddle" during a puzzle competition, most people would look at the puzzle for the form of the classic riddle (a cryptic description using metaphoric language and generally incorporating literary devices), rather than looking for the nature of a riddle - the metaphoric analogy. Most of the puzzles of this form I've seen lately have taken the form of extended analogies for a process - representing a poker game as a set of skirmishes between two sides, or representing a chess game as gang warfare. I could be convinced to use the term "riddle" for this, but so far I haven't because I fear invoking the existing idea.

Recursion is another silly oversight on my part; I was thinking of it when writing the draft and somehow it never made it onto the page.

I don't know the Duck Konundrum, but I have encountered puzzles before where the solution is obtained by following a set of instructions very precisely. That should be added as a category - did you have something different in mind?

Thanks for the PDF; I've heard this sheet referred to in the past, but I've never had a copy of it before. In some ways, this is an attempt to generate such a sheet for my own use.

Also, thanks for all this thoughtful commentary! I have no idea who you are or how you've stumbled upon this work, but your comments will be a lot of help in preparing the next version.

You got linked by Puzzlinks (which also has an LJ feed), and I thought I'd add my two cents.

I agree that indentification/recognition puzzles are essentially generally "nonresearchable," at least via simple means. Let me throw a few more of what I would consider identification puzzles at you. I'm sorry that they're all MITMH puzzles, but since M$ refuses to make its hunts public, I can't talk about those. At a certain point, recognizing a location from a sketch drifts to identifying a song by a sketch. Similarly, it shouldn't be too difficult to identify locations by sound instead of sight. So again, why shouldn't it be the same thing to identify a song by sound. Then, if we're thinking about Eyeball Benders, why separate everyday objects from celebrities or art? None of these things can be reliably checked through a search engine.

Then, when it comes to non-researchable, there are other identification puzzles that seem more mundane, but are just as difficult to identify, like music videos. Then there are identifications that have gone through a metaphorical layer, like song lyrics as read by a computer (PDF). Again, unsearchable.

When I think of "null puzzles," I most often think of metapuzzles, where you're dealing with answers and trying to pull out the important parts of them. In particular, based on your example, I recall a metapuzzle where each answer included a alphabet code word, which is the same method as the "information surplus" but in a much smaller scope. In another metapuzzle, each answer contained an RNA trigram (which, of course, led to a mapping/translation). These kinds of letter-pulling clearly aren't indexing, because no index is provided. What's happening is pulling the important part out of the "nulls."

The Duck Konundrum is the prototypical example of a follow-the-complicated instructions puzzle. The original and its many sequels were written for the MITMH by Dan Katz, and the name has become a watchword among the people who create and solve major puzzle hunts. However, "follow the directions" appears on a smaller scale in other puzzles, especially in connection with a true information surplus puzzle.

Ah! I suppose I'm always shocked when something I write wends its way out of my little corner of the social sphere. Neat.

Your recognition examples are interesting - there's definitely a blurry line between recognition and trivia, though I still think the distinction is useful to attempt to maintain - recognizing a celebrity by a photo is recognition, I think, whereas knowing what he's famous for is trivia. I think I might want to place the fuzzy line on the basis of the cognitive facility it uses - we speak of "recognizing" a photo, a melody or a scent, while we speak of "remembering" a lyric or a fact. There's still a lot to figure out on that one...

Am I right in gathering that your "null puzzles" generally include a notion of knowing how to extract meaning from noise? (That is to say, you're instructed or clued in some way?) That's a hallmark of metapuzzles that I've seen before, and something I think is distinct from my information surplus puzzles - in general, the puzzle of an info-glut is simply "how do I cull this huge dataset into something meaningful," while a metapuzzle that involves extraction is "take data that previously appeared meaningless and, by applying this rule, generate meaning from it." Are your "nulls" the chunks of apparently-meaningless data that can have nuggets of meaning extracted?

While I've never heard of the Duck Konundrum, now that I've read it, I'm sure I've seen other puzzles in its class. The key factor in the genre seems to be the manipulation of a large number of variables based on state, which makes it impossible to solve by any means other than following the instructions. There do seem to be two general subclasses, too - puzzles where you're expected to solve by actually enacting the instructions, and puzzles where you're expected to model the result of following the instructions, which are not feasible to actually carry out.

That's a pretty good taxonomy, but it certainly suggests that your exposure to puzzles is mostly around puzzle hunts and internet-delivered puzzles -- one thing those puzzles have in common is that the "solution" is usually one word or phrase, and that tends to bias the puzzle types.

Here are some puzzle classes that you might not have considered:

Puzzles based on games. Open any large newspaper and you'll probably see a chess puzzle and a bridge puzzle. While you could argue that a chess puzzle is "constraint-satisfaction", I think you'll agree that the type of thinking process is rather different. A bridge puzzle is often not even that, because there usually is a random element that needs to be considered. In some sense, there is a class of puzzles that deals with game theory (both classical and combinatorial) that is missing from your taxonomy.

Construction puzzles. Michael Winkler once proposed this challenge: "Can you create three mechanical objects such any one object can be removed, but once one object is removed, the other two cannot be separated from each other?" One feature that construction puzzles tend to have in common is that the search-space is infinite, and so is the number of solutions, but the challenge comes from the fact that the number of solutions is very sparse in the search space. But once you have a solution, usually there's some way to verify that it works, even though other solvers may come up with something entirely different. Interestingly enough, these puzzles aren't really absent in the MIT Mystery Hunt -- they're called "creative challenges" -- although depending on how it is phrased, one may or may not consider it a puzzle.

While on the subject of mechanical puzzles, the amount of variety there is also staggering. "Jigsaws and Tangrams" doesn't quite do it justice. A good starting point is the Wikipedia page at http://en.wikipedia.org/wiki/Mechanical_puzzle

Thanks for the comments!

I'm certainly biased by my primary puzzle experience, which is, as you've said, puzzle hunts and Internet-driven puzzles - and I will be clearer in the next version of this taxonomy that I'm not intending to be perfectly applicable across all puzzles everywhere. In particular, I'm aware that the variety in mechanical puzzles is outside of my league; I have neither the background nor vocabulary for them.

I'm inclined to see something like retrograde chess as constraint-satisfaction, but you're right that Bridge analysis doesn't fit into that form very well. I'm hesitant to categorize them by their association with games, though - a game is, for these purposes, just a rule-set, and I've seen such puzzles applied to things like Risk and Monopoly in addition to the more classic Chess and Go. I wonder whether chess analysis is constraint-satisfaction as I understand it, while Bridge analysis is in this game-theoretic category. (And, while I'm wondering, I wonder what other game-theory puzzles are out there!)

Construction puzzles should be on here in some form, probably as their own category. I'm not sure to what extent they share commonalities with other puzzles, but I'm interested in discussing that!

Again, thanks for your comments - I'll be thinking more about them!