Einstein’s logic puzzle

Earlier today, I was thinking about a logic puzzle that originally was attributed to Albert Einstein. Here’s a quick description of the original puzzle. The original can be solved very quickly — if you have the right insight.

This puzzle has inspired several computer games — one written in 1990 for MS DOS (called Sherlock) and another written a few years ago for Linux/Windows/MacOS called Einstein.

Both Sherlock and Einstein (the computer game) are played on a 6 by 6 grid of tiles. Each row has a set of items for that row, and each column has a specific series of items from each row.

For example, a specific row could have types of animals — say cats, dogs, horses, birds, and fish. Each specific column would have one of a cat, a dog, a horse, a bird, or a fish. Further, one and only one column would have a cat (or a dog, etc.)

Here’s a more specific example — let’s say that we have a 4×4 grid. In the first row, we have types of animals (dog, monkey, mouse, goat). In the second row, we have different-colored tiles (red, green, blue, orange). In the third row, we have different numbers of circles (one, two, three, four). In the fourth row, we have letters (A, B, C, D). Now, in each row, we can only have the items specific to that row — we can’t have a mouse in the colors row. When the puzzle is solved, each column will have one item from each row — the first column might have a goat, a blue tile, two circles, and the letter A, and so on for the other columns.

In order to determine which tiles go in which columns, you are given a number of clues. The clues in this puzzle tell you about how the tiles are laid out. There are five types of clues:

1. A specific tile goes in a specific location. (Example: the red tile is in the second column.)
2. That two tiles (different rows) are in the same column. (Example: The monkey is in the same column as the letter B.)
3. That two tiles are in immediately adjacent columns; the tiles may or may not be in the same row. (Example: The two circle tile is in the column adjacent to the tile with the dog.)
4. That one tile is to the left (or right) of another. (Example: the letter “C” is in some column to the left of the blue tile — not necessarily adjacent.)
5. Lastly, that three tiles are in three adjacent columns. (Example: the red tile is adjacent to the cat, which is then adjacent to the letter “B”.)

I was thinking about how to implement this puzzle in a computer game. In order to do this, you need to be able to create a set of rules that are both consistent and have only one solution.

The first thing that I need to do is to determine what solutions a set of rules match, if any. Well, the brute force approach would be to enumerate the boards one-by-one and see how many boards match those rules.

A quick back-of-the-envelope calculation tells us that this is impractical — for a 6×6 board, there are possible combinations of tiles per row, and with six rows, there are possible arrangements of tiles. This means that brute force is Right Out.

So here’s a first attempt. First, the program should choose “the solution” to the puzzle that it is going to present: some ordering out of the 140 quadrillion possible solutions.

Now we start randomly creating rules that are consistent with our solution.

For each rule that we create, we start looking at the partial solutions that will match that rule and the other — previously created rules — if we create a rule that says “The cat is above the red tile”, we examine the six partial solutions that match this rule (cat and red tile in the first column, in the second column, etc.)

We’ll keep on adding rules just so long as we either:

1. Apply all of the rules and still have tiles that we didn’t place somewhere — in which case, we create a rule that matches the tile that we didn’t place.
2. Find other solutions — and then we add a rule that matches “the solution” but not the “other solution” that we just found.

Eventually, we’ll get to the point where we have rules that only match our chosen solution.

From experience, we’ll end up with between 10 and 20 rules.  Searching through this list is much shorter. At the very worst, we have 15 separate ways that a specific rule can match an empty board. Further, the more rules that have been applied, the fewer number of ways a given rule can match the board. The absolute worst we could see for the number of combinations that we’d need to traverse is

Clearly, this is not an improvement — so what if we *sort* the rules before we try to apply them to the board? The pessimistic option above would become combinations that we would have to check.

Now the question becomes, how do we sort the rules?

Here’s my first stab at how to order the rules:

1. All “this tile goes specifically here” rules.
2. Any rule mentioning a tile placed by “this tile goes specifically here”.
3. Any rules containing tiles that are in the rules from #2 (and now #3).
4. Count the occurrences of the tiles in the remaining rules. The more times that a tile occurs, the more “important” it is. Sort the remaining rules by the “importance” of the tiles mentioned therein.

Analysis of this is going to prove more difficult; more on this later!