The
Red King

The Einstein Problem

Einstein said that 98% of the population couldn't solve this problem. Working it out in your head just takes a few minutes with a pad & pen. It isn't a huge problem, but it is a good example of making sure you don't just try to make a computer do a complete random search for a problem.

Problem Statement

There are 5 houses in 5 different colors. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain type of pet. No owners have the same pet, smoke the same brand of cigar or drink the same beverage.

The question is: "Who owns the fish?"

You have the following hints to help you:

  • The Brit lives in the red house.
  • The Swede keeps dogs as pets.
  • The Dane drinks tea.
  • The green house is on the left of the white house.
  • The green house's owner drinks coffee.
  • The person who smokes Pall Mall rears birds.
  • The owner of yellow house smokes Dunhill.
  • The man living in the center house drinks milk.
  • The Norwegian lives in the first house.
  • The man who smokes blends lives next to the one who keeps cats.
  • The man who keeps horses lives next to the one who smokes Dunhill.
  • The owner who smokes Bluemasters drinks beer.
  • The German smokes Prince.
  • The Norwegian lives next to the blue house.
  • The man who smokes Blends has a neighbour who drinks water.

Solutions

All tests were done on an Athlon 2200+, 256Mb RAM and FreeBSD 4.9 generic kernel. The source code was compiled using gcc and the UNIX time command used as stated below:

g++ -O3 einstein.c -o einstein
time einstein
V1
einstein.c

A full search solution that only tests that the riddle has been solved at the end. This was done as a 'worst case scenario' only and naturally the performance is awful!

2314secs

V2
einstein2.c

Combinations for each sets of items are tested to check if they are possible as soon as the set is complete. Makes a big difference as allows searching of large proportions of the search space to be stopped early.

0.038secs

V3
einstein3.c

All combinations are tested as soon as possible in the search tree (e.g. as soon as the left most house is chosen etc.).

0.036secs

V4
einstein4.c

All neighbour data is collected as soon as each set of items is determined. Noticeable performace loss as all find()'s are always done.

0.048secs

Complete Package

Correct Solution

Select+Drag to reveal

House 1  Norwegian  Cat    Water   Dunhill     Yellow
House 2  Danish     Horse  Tea     Blend       Blue
House 3  British    Bird   Milk    PallMall    Red
House 4  German     Fish   Coffee  Prince      Green
House 5  Swedish    Dog    Beer    BlueMaster  White

The German owns the fish