Project 2: Embuzzled

The aim of this project is to automatically create an image containing a collection of embedded puzzles for a human puzzler to solve. The puzzles are embedded in a grid whose shape is part of the input to your program. For example, consider this image. The shape is a 10x10 square grid with the corners cut off. (The light blue is the background, and is not part of the shape.) Each cell in the grid is colored with one of several discrete colors.

The human puzzler's task is twofold. First, they have to figure out that a certain group of colored cells within the image consititutes a puzzle. In the image above, the red cells form such a group. Once the puzzler has identified this group, he/she must identify the pattern that this group of cells encodes. In this case, the pattern is the simple arithmetic progression 1,2,3,4. The number in the lower right corner is generated by your program. It tells the puzzler how many puzzles are embedded in the image. In this example, the number is 1, and so the puzzler who has found the arithmetic progression knows that all puzzles have been found.

We'll generally be working with larger images, the only constraint being that they fit on a single piece of letter-sized paper and are readable (without a magnifying glass) at the specified resolution. You will therefore have space to embed a fair number of puzzles into your images.

The arithmetic sequence above is only one of many kinds of embedded puzzle you might be able to come up with. For example, you could embed text (let's restrict ourselves to English, please), symbols, codes, etc. You can use or refer to items that would be common knowledge to a Columbia puzzler, such as a sequence based on NYC subway stop numbers, for example. The options are limited only by your imagination, and what you think a puzzler will be able to figure out after (say) 15 minutes or so of puzzling.

At the end of the project, the TA and I will recruit some puzzlers who will try to solve the puzzles in your images within a fixed time limit. Note that we'll be giving you the shape of the competition image after the final code submission deadline. While you cannot change your code after the deadline, we will allow you to run your code many times with different random number seeds and choose from among the generated puzzles. Note that if you use randomness, it must be done in a reproducible fashion. Thus, if you generate an image using the seed 8765, we should be able to generate the same image using your code and the same seed.

We'll ask the puzzlers to rate the puzzles. As always, these ratings are for fun and pride only, and do not affect your grades. Grades are based on your reports and presentations. I cannot predict for certain which criteria the puzzlers will use to judge the images. You may want to try out some of your initial attempts on your friends to see what they think. Nevertheless, here are some initial guidelines that might be helpful, and things to think about:

• Puzzles that are either too easy or impossibly difficult are frustrating.
• Cleverness and creativity in your puzzles is likely to be appreciated. A common theme among puzzles within an image, similar to what is often done within crossword puzzles, might impress the puzzlers. It might also help them figure out the puzzles.
• Each cell can be an arbitrary RGB color. Should you stick to a few discrete colors, or use the complete range?
• What colors are visually appealing? When can color be distracting and/or confusing? There has been much work on this topic, and a good starting point is the work of Tufte. Note that in some cases, distraction might be a good thing: think of the ``Where's Waldo'' books.
• The image will be contiguous, but it may have holes, like a donut. The boundaries of the image shape may be straight or irregular. How will these features affect your placement algorithms?
• Be careful about stray colors that might accidentally invalidate or confuse a puzzle. In the example image, imagine what would happen if one of the non-red cells adjacent to a red cell had also been colored red.
• If you're embedding a sequence, how many terms do you need to embed for the puzzler to be certain that the pattern is genuine?
• When might background or filler cells inadvertantly resemble puzzles? How can this effect be avoided?
• Do cells have to be adjacent to be part of a single puzzle?
• Is there an optimal puzzle ``density'' within an image? If puzzles are evenly spread out, does that make locating the puzzles too predictable?

In addition to the image, your program should generate a solution key, in the form of plain text. The puzzlers will be shown the solution key before they give their final rating.

I'll give you an image to try to solve just after project 2 groups have been formed. You'll have a few days to work on the puzzles within your groups, or alone if you prefer, and we'll discuss them during the first class. Please do not talk to people outside of your group when working on this practice puzzle, even just before the first class -- this way you'll get a better feel for the puzzler's point of view.

(For a related kind of puzzle, read the Wikipedia article on Al Hirschfeld, the cartoonist who embedded the name ``Nina'' in many of his cartoons.)