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.
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:
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 |
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