Tuesday, January 31, 2017

Generate a Puzzle for Your Math Class in 5 Minutes

There's a famous puzzle, often referred to as the Zebra Puzzle. It goes something like this:

  1. There are five houses.
  2. The Englishman lives in the red house.
  3. The Spaniard owns the dog.
  4. ...
  5. ...
Here follow many more facts detailing who lives next to whom, and which pets they own and so on, until the final question is given: Who owns the zebra?
There is no quick and clean solution for this puzzle that involves a single big "Aha!" moment, but rather a series of steps, making ad-hoc assumptions, and trying to see if they sit well with each other and with the facts given, until a solution is found.

Constraint Satisfaction Problems

This puzzle belongs to a class of problems called Constraint Satisfaction Problems, or CSP. 
While CSPs in general are hard to solve, even for computers, small instances of them are both easy to create, and make for popular puzzles. An example of such puzzle is Sudoku.

Floors Puzzles

Here's a really easy CSP I just came up with:
  1. There are 4 floors in the building.
  2. The rooster does not live on the top floor.
  3. The cat lives two floors under the lion.
  4. the dog lives in a lower floor than the rooster.

Which animal lives on which floor?
Spoiler alert: if you like to solve this puzzle, do so now, since the next section will reveal the solution. The puzzle is, by the way, so easy that I suggest you solve it yourself anyway, just to get an understanding of what it feels like.
An animal that does not live on the top floor

This is a nice puzzle for 10 year old students. A similar puzzle with 3 floors will be suitable for 7 year olds, and naturally, more floors can make it increasingly harder to solve.

Create Your Own Floors Puzzle in 5 Minutes

  • Choose animals and number of floors. 
  • Draw a diagram of which animal goes where, e.g.:
  • Write down rules that describe your building - e.g. "the dog lives 3 floors below the lion".

Over a certain number - some of the rules will be redundant, that is - the puzzle may be solved even if those rules are not given, but don't worry about that. As a rule of thumb - the number of rules should be slightly smaller than the number of floors.

Checking Solutions

Note that it may be the case that there will be correct solutions that are not identical to the one you used to write the puzzle, but that's okay, because the puzzle is about finding a solution, not the solution. While it is possible, in principle, to check whether the rules you chose have more than one solution, it will probably take more than the 5 minutes promised in the title of this post... 

So there you have it - generate a puzzle for your math class in five minutes or less. Enjoy.


On a less-practical note, about a year ago I wrote a post tying "good" puzzles to NP-complete problems, and this current post is really just another example of that.