# Solving Einstein’s Riddle with Ruby

Doing the rounds again at the moment is the so-called “Einstein’s Riddle”, a puzzle he allegedly described as being too difficult for 98% of the population to solve.

Also known as the Zebra puzzle, it involves deducing the nationality of inhabitants of a street of houses, the colour of those houses, and which drink, cigar and pet the occupant prefers.

There are five houses in five different colours in a row. In each house lives a person with a different nationality. The five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet.

No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

Other facts:

1. The Brit lives in the red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The green house is on the immediate left of the white house.
5. The green house’s owner drinks coffee.
6. The owner who smokes Pall Mall rears birds.
7. The owner of the yellow house smokes Dunhill.
8. The owner living in the center house drinks milk.
9. The Norwegian lives in the first house.
10. The owner who smokes Blends lives next to the one who keeps cats.
11. The owner who keeps the horse lives next to the one who smokes Dunhill.
12. The owner who smokes Bluemasters drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The owner who smokes Blends lives next to the one who drinks water.

The question is: who owns the fish?

The specific attributes are interchangeable, but the puzzle always retains two key features: The number of possible combinations is enormous, and there is only one single valid combination that satisfies all the given facts.

## Naïve Solution

5! ×5! ×5! ×5! × 5! = 24,883,200,000

In a naïve solution, all we need to do is generate all possible combinations of colour, nationality, cigar, pet, and drink and then try them out with each house in the street. Every time we generate a new street, we test out the configuration against the facts we know — if any facts are contradicted then we move along to the next combination.

Ruby’s Array library has a handy method to help us out, Array#permutation.

This allows us to nest 5 loops in order to create every single valid street.

Now we need to think about how we check the facts laid out in the puzzle.

If we assume the ordering of each set to imply the house numbers then it makes our code quite simple as the house that each option appears in (colour, pet, cigar etc) matches its place in the array (assuming we index from one not zero) i.e.

Now we need to consider how to check whether the facts are validated. The simplest kind of fact in the puzzle is a statement of positional implication, i.e.

The owner living in the center house drinks milk.

or

The Norwegian lives in the first house.

We can easily test for this with an array index test:

The next type of fact matches two options into one house i.e.

The German smokes Prince.

In terms of predicate logic, we can define this rule as AB, or “A implies B”. This means, if the cigar smoked in a certain house is “Prince” then the nationality of the occupant is German (and reflexively, BA, since there can be no duplicates).

Rather than hardcoding that, let’s define a method #implies? that returns true or false for whether a house in the street contains both an occupant whose nationality is German, and an occupant who smokes Prince cigars.

Now we can define all the implies? facts as follows:

The next type of fact is an extension of the #implies? fact:

The green house is on the immediate left of the white house.

This is a simple twist on the #implies? fact test. Since we represent position as the ordering of the arrays, we can specify this as follows:

There’s a third type of fact that builds further on this i.e.

The owner who keeps the horse lives next to the one who smokes Dunhill.

This means the Dunhill smoker lives either to the left of the horse owner, or to the right. We can express this like so:

Ok! Now we have all the tools we need to check the known facts. Let’s put it all together.

Eventually (anywhere between minutes and hours) this will spit out the correct combination. If you still want to deduce the answer yourself, now would be a good time to bookmark this post for later ;-)

=> [ [:yellow, :blue, :red, :green, :white], [:norwegian, :danish, :british, :german, :swedish], [:cats, :horses, :birds, :fish, :dogs], [:water, :tea, :milk, :coffee, :beer], [:dunhill, :blends, :pall_mall, :prince, :bluemasters]]

This translates to:

• House 1 is yellow. The owner is Norwegian, smokes Dunhill, drinks water, and keeps cats.
• House 2 is blue. The owner is Danish, smokes Blends, drinks tea, and keeps horses.
• House 3 is red. The owner is British, smokes Pall Mall, drinks milk, and keeps birds.
• House 4 is green. The owner is German, smokes Prince, drinks coffee, and keeps fish.
• House 5 is white. The owner is Swedish, smokes Bluemasters, drinks beer, and keeps dogs.

# A faster implementation!

Since only one permutation is correct, this means you have a 119/120 chance of starting with the wrong ordering and doing a whole heap of pointless tests in the process.

In terms of worst-case scenario, we’ll need to loop through all 24 billion combinations before reaching the correct one at the very end. Realistically, you’ll meet the combination on average in the middle somewhere, so you’ll average 12 billion tests before you get your answer.

Surely we can do better…

What if we could discount bad permutations at every level of iteration? We’d cut down the problem space significantly.

So we’ve cut down the problem space massively from 14,400 to 2,880 — that’s 80% smaller!

Let’s try this with the other facts, placing their tests at the right loop level.

Note our use of #shuffle when setting up the options. Without this, we’d get the same number of loops every single time we run the solver so it’s reassuring to see that it works in a sensible amount of time no matter what the initial ordering of the permutations is.

So now we have a solver that finds the correct solution in around 55,000 tests. That’s just 0.0002% of the number of tests needed by the naïve solver!

This runs consistently on my laptop in around a fifth of a second. Throw in some code to display it nicely and we’re about done with our smart solution.

# Anyone for golf?

## Merging left_of? with implies?

Now we can throw away the #left_of? method and use i(a,b,c,d,1) instead.

# 546 characters

Pretty nifty! And that’s Einstein’s puzzle about done for me.

Full source on Github: https://github.com/seanhandley/einstein

EDIT: Thanks very much for all the comments folks! A lot of people have pointed out you don’t need code to solve this… and that’s true. I did it on pen and paper first and then thought “This’d be fun to solve with code!”. It’s definitely an enjoyable puzzle to do offline so don’t let all the code dissuade you from trying.

Written by