Algorithmically generate a Zebra/Einstein puzzle

Question

Firstly I'm not necessarily looking for a complete algorithm I can just copy and paste, then call it a day. Any "general approach" solutions would be fine for me!

This entire post was spurred by a slow day at work, and stumbling upon this site and not being able to figure out how they implemented their generator.

The Problem

For those of you who don't know, the "Zebra Puzzle" or "Einstein's Puzzle" is a famous logic puzzle that you've probably ran into before.

The full wiki article is here, but I'll post the relevent bits.

There are five houses. The Englishman lives in the red house. The Spaniard owns the dog. Coffee is drunk in the green house. The Ukrainian drinks tea. The green house is immediately to the right of the ivory house. The Old Gold smoker owns snails. Kools are smoked in the yellow house. Milk is drunk in the middle house. The Norwegian lives in the first house. The man who smokes Chesterfields lives in the house next to the man with the fox. Kools are smoked in the house next to the house where the horse is kept.  The Lucky Strike smoker drinks orange juice. The Japanese smokes Parliaments. The Norwegian lives next to the blue house.  Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages  and smoke different brands of American cigarets [sic]. One other thing: in statement  6, right means your right.  

This is all well and good. I've found several concise and neat ways online to solve this problem, especially using constraint programming. However, what interests me is making more of these types of puzzles.

Making More

Obviously, a matrix representation is a logical way to think about this. With each column containing a person, house, what they drink, what type of car they drive, etc.

My initial thought was to start with a randomly generated grid that is complete (ie, solved) then (somehow) create hints from the solved version that uniquely identify it. Every time something can be determined, it's removed from the grid.

Ripping off the site I listed at the beginning, the following "hints" that can be used to solve the grid can be of the following type:

• The person/animal/plant lives/grows in a given house.

• The person/animal/plant does not live/grow in a given house.

• The person/animal/plant lives in the same house as the other person/animal/plant.

• The person/animal/plant is a direct neighbor of the other person/animal/plant.

• The person/animal/plant is the left or right neighbor of other person/animal/plant.

• There is one house between the person/animal/plant and the other person/animal/plant.

• There is one house between the person/animal/plan and the other person/animal/plant on the left or right.

• There are two houses between the person/animal/plant and the other person/animal/plant.

• There are two houses between the person/animal/plan and the other person/animal/plant on the left or right.

• The person/animal/plant lives left or right from the other person/animal/plant.

You can see how these could be generalized, extended, etc;

The difficulty is, using my approach (starting with a complete grid and generating these hints), I'm not sure how to make sure the set of hints I create would absolutely result in the target grid.

For example, if you say "The Englishman does not own a pine tree" you cannot decisively pair two things together at any given time in the puzzle. Yet if there were only two trees remaining to solve for, this could in fact be a decisive piece of evidence.

Am I thinking about this the entirely wrong way? Would a better approach be to create a grid with some randomized, pre-defined known elements (ie, the red house is in the middle) and then build up the grid using these hints as rules for building?

Any advice, articles to read, programming techniques to learn about, etc. would be greatly appreciated!

Answer 1

Here's a simple algorithm making use of your solver:

1. Generate a random puzzle instance.

2. Build a set C of all possible clues that pertain to this puzzle instance. (There are a finite and in fact quite small number of possible clues: for example if there are 5 houses, there are 5 possible clues of the form "Person A lives in house B", 8 possible clues of the form "Person A lives next to house B", and so on.)

3. Pick a random permutation c₁, c₂, ..., c_n of the clues in C.

4. Set i = 1.

5. If i > n, we are done. The set C of clues is minimal.

6. Let D = C − { c_i }. Run your solver on the set D of clues and count the number of possible solutions.

7. If there is exactly one solution, set C = D.

8. Set i = i + 1 and go back to step 5.

(You can speed this up by removing clues in batches rather than one at a time, but it makes the algorithm more complicated to describe.)

Answer 2

I'm not entirely confident in this solution but this is how I would approach it:

Starting from a random solution (i.e. green house holds polish that smokes LM, red house holds irish that smokes cloves etc). you may look at that solution as a graph of relations between statements. where every element (polish, red house etc) is connected to all other elements either by a "yes" edge or a "no edge" (in our case the polish is connected to the green house with a "yes" edge and to the cloves with a "no edge" (amongst many other edges, this initial graph is a full, directional graph)).

Now, if you randomly take away edges, until you are left with a minimal connected graph, you should have a graph representing a solvable puzzle. translate every yes edge to "the foo is/does bar" and every no edge to "the foo isn't/doesn't bar".

intuitively this sounds about right to me. but again, this is in no way a formal or recognized way to do this, and may be entirely wrong.