This solution to Einstein's puzzle was written on Dec 28th, 2009, and retroactively posted elsewhere so that it doesn't distract the TRF readers too much.
Update, Dec 31st 2009 morning
I have written a pretty cool piece of code in Mathematica that finds the solution in less than 1 second, after reviewing the 15 hints less than 6 times. The program remembers the 125 probabilities for the assignments of the type "1st house keeps birds" and adjusts the probabilities cyclically by taking the hints into account. Unfortunately, this program wouldn't converge to the solution if the redundant hint 15 were omitted.
See a PDF preview and the notebook NB file itself.
Draw a 5-by-5 table. Call the columns (houses) 1,2,3,4,5. One is left, five is right.
Call the rows "nation", "color", "drink", "pet", "cigarette". Please, don't consider the labels above the columns or on the left side of the rows to be additional columns. Only the interior of the table - with 5 rows and 5 columns - should be counted.
You will use the table to solve the puzzle.
It's useful to list (and memorize) all the five possible values of all five characteristics.
Now, try to evaluate the 15 hints. It's useful to first focus on the hints that contain "bigger information" and "the most straightforward information".
Clearly, hint 9 is the most obvious one. The Norwegian lives in the left house. Write "Norwegian" in the corresponding place (1st column, 1st row) of your table. Hint 9 is actually not the only hint that directly tells you the location of any characteristics.
Once you know something about the Norwegian guy, all the hints involving "Norwegian" become more useful and straightforward. Look for them. Hint 14 tells you that the house next to the Norwegian one is blue. Because the Norwegian is at the end, only the 2nd column is its neighbor. The 2nd column, 2nd row (color) can therefore be written as "blue".
There was one more hint we could use at the beginning. Hint 8 says that the middle house drinks milk. Write "milk" in the 3rd row, 3rd column.
So far, you only have 3 entries in your table. It's not great yet. Nations, colors, drinks each have 1 known entry. Now, you can find somewhat more complicated arguments about these things.
For example, hint 4 says that there are 2 colors "green, white" written in this order, without anything in between, in the 2nd row. Because house 2 is blue, green-white can be neither 1-2 nor 2-3. It must be 3-4 or 4-5.
Can you say which one? You bet. One extra hint is enough in this case. You scan for "green" which is relevant now. Hint 5 says that the green house drinks coffee. So it can't be house 3 which drinks milk, as we already know. Green-white must be houses 4-5. Write "green, white" at the end of the 2nd row i.e. in the 4th and 5th columns.
There are already 3 known colors of the houses, 2-blue, 4-green, 5-white. You should have prepared a list that instantly tells you that the remaining colors are red and yellow. Which is house 1 and which is house 3? Again, scan for hints including "red" and "yellow" to learn more.
The relevant hint turns out to be hint 1: the Englishman lives in the red house. We may therefore talk about the "red English house". Among two candidates (1,3) for the red English house, 1 is known to be occupied by the Norwegian chap. So it can't be the English house. Consequently, 3 must be the English red house. In the 3rd column, 1st and 2nd rows, write "English" and "red". The remaining color, "yellow", may be now written to the 1st column, 2nd row.
Because we have understood all colors, all hints involving colors have become directly useful. Hints 1,4 have been used. But hint 5 links the green color to coffee. Write "coffee" in the 4th column, 3rd row. Similarly, hint 7 links yellow to Dunhills. Write "Dunhill" in the 1st column, 5th row. No other unused direct hints involving colors can be found.
Again, Dunhill and coffee became known, so the hints involving them are more usable, too. In particular, hint 12 says that the Dunhill house is next to the house with horses. Dunhills are in house 1, so horses must be in house 2: write "horse" in 2nd column, 4th row.
Now, things become somewhat more complex. We must summarize the hints that are still waiting to be used: 2, 3, 6, 10, 11, 13, 15. Note that eight hints have been used while 7 have not. We have already used more than 1/2 and get stuck for a while.
Among the 7 unused hints, five hints 2, 3, 6, 11, 13 don't talk about any neighbors but rather pairs of characteristics that are simply linked (i.e. appear in the same column, the same house):
Sticker 1: Swede - dogs
Sticker 2: Dane - tea
Sticker 3: PallMall - birds
Sticker 4: BlueMasters - beer
Sticker 5: German - Prince
These "direct hints" are more likely to be instantly useful. Note that none of the 10 words above (Swede, dogs, ... Prince) is written in the table yet. There are only 14 empty places in the table so it's pretty dense. In fact, only 5th column - 5th house - has at least 4 empty places, so it could swallow two pairs from the table above. Three empty slots are not enough for two stickers.
In fact, the 5th column will have to swallow two pairs. Why? Because house 1 isn't compatible with any of the stickers. House 1 is a Norwegian yellow Dunhill house. But each of the 5 pairs above requires either a different nation than Norwegian or a different cigarette brand than Dunhill.
So none of the 5 pair stickers can be written in the 1st column. There are 5 stickers per 4 allowed columns. And House 5 is the only one where we can put two pair stickers from the list of 5 pairs above. The remaining 3 stickers will go to columns/houses 2,3,4.
Also, the column 3 is pretty crowded: English, red, milk. There are only two empty slots waiting to be filled: pet and cigarette brand. Clearly, the pair sticker 3 - PallMall birds - is the only one with these characteristics, so you may write "birds" and "PallMall" to the empty places of the 3rd column.
Now, let's look which two pair stickers belong to the house 5.
You can see that three pairs (1,2,5 in the list of five) contain a nationality while three others (3,4,5) contain a cigarette brand. You may have at most 1 nationality and at most 1 cigarette brand in each house which means that we will have to pick one pair among 1,2 and one pair among 3,4. Only the combinations 1+4 and 2+3 work. Moreover, sticker 3 has already been used in the 3rd column/house. So it must be stickers 1+4 that must be attached to House 5. Write "Swede, beer, dogs, BlueMaster" to the fifth column (white house).
The remaining two stickers that have not been used yet are
Now, Dane-tea must be house 2 because other houses have contradictory nations and/or beverages. Write "Dane" and "tea" to the 2nd column.
There is only one nation that hasn't been added to a house yet. So house 4 must be German. Write "German" in the 4th column. The German-Prince hint also allows you to write "Prince" in the 4th column.
At this moment, the last unaffiliated cigarette brand is Blend, so it must go to the remaining place in the last row, namely in the 2nd, Danish column. Write "Blend" over there. In a similar way, the last unaffiliated beverage is water which must go to the last empty slot in the 3rd row, i.e. to the 1st (Norwegian) column. Write "water" over there.
If you remember, the last hints that were not used are 10 and 15 - and they talk about neighbors. Hint 10 says that Blend is a neighbor of cats. Blend is in house 2 but house 3 are birds, so the cats must live in house 1 on the opposite side. Write "cats" in the first column. The remaining pets are fish which must go to the 4th (German) column.
Write "fish" in the 4th column. That also answers the question: it's the German who keeps fish.
The table is now complete. Hint 15 was redundant. But as a consistency check, you may verify that Blend (house 2) and water (house 1) are indeed neighbors.
By the way, the Mathematica code I linked at the top wouldn't converge to the right solution if hint 15 were omitted. If you were using a similar algorithm and got stuck in this way, you could get unstuck manually.
For example, the nationality of the 2nd house would be determined to be either Danish or German. You could try add an extra rule, lpa[2,"german"], and the result would be a division by zero, which only occurs if there's no solution (because it tries to normalize the five probabilities 0,0,0,0,0). If you add an extra rule lpa[2,"danish"] instead, the program would abruptly find the solution, automatically proving that hint 15 is indeed redundant.