Einstein's Logic Puzzle (SPOILER ALERT!)

On Monday I began working through a Discrete Math textbook in preparation for some courses I'll be taking in January. There was a beautiful logic problem in Chapter 1, apparently created by Einstein. This is one version of it:

Five men with different nationalities and with different jobs live in consecutive houses on a street. These houses are painted different colors. The men have different pets and have  different favorite drinks. 

Determine who owns a zebra and whose favorite drink is mineral water (which is one of the favorite drinks) given these clues: 

1. The Englishman lives in the red house. 
2. The Spaniard owns a dog. 
3. The Japanese man is a painter. 
4. The Italian drinks tea. 
5. The Norwegian lives in the first house on the left. 
6. The green house is immediately to the right of the white one.
7. The photographer breeds snails. 
8. The diplomat lives in the yellow house.
9. Milk is drunk in the middle house.
10. The owner of the green house drinks coffee.
11. The Norwegian’s house is next to the blue one. 
12. The violinist drinks orange juice. 
13. The fox is in a house next to that of the physician. 
14. The horse is in a house next to that of the diplomat.

Initially there are 600 (5! for each row) possible combinations. 
Using the clues we can immediately reduce this like so:

Number	1	2	3	4	5
Color
Nationality	Norwegian
Job
Drink			Milk
Pet

This is a table representing the fields with the currently known values using CLUES 5, 9, 11. 
There are now only 312 possible combinations of the remaining fields.

SOLUTION

1. Right away, you can find the color of the Norwegian's house using CLUES 1 and 6 (on top of those you have used already.)

• CLUE 6 tells you that the WHITE and GREEN houses are adjacent. Therefore, neither can be HOUSE 1-they must be two of the houses from HOUSE 3,4 or 5.
• CLUE 1 tells you that the Englishman has a red house. Therefore, by process of elimination, the Norwegian's house must be yellow.

Number	1	2	3	4	5
Color
Nationality	Norwegian
Job
Drink			Milk
Pet

Remaining possible combinations : 294

2. Now, using CLUES 8 and 14,  we discover that the Norwegian is the DIPLOMAT and the house next to him  contains the HORSE.

Number	1	2	3	4	5
Color
Nationality	Norwegian
Job	Diplomat
Drink			Milk
Pet		Horse

Remaining possible combinations : 112

3. Look at clues 4, 10, and 12. The Norwegian can't drink milk (since he lives in HOUSE 1), he can't drink ORANGE JUICE as he isn't the violinist, he can't drink TEA (CLUE 4) and he can't drink coffee(CLUE 10). 

 Therefore he drinks  mineral water.

Number	1	2	3	4	5
Color
Nationality	Norwegian
Job	Diplomat
Drink	Mineral Water		Milk
Pet		Horse

Remaining possible combinations : 84

4. At this point it makes sense to list the remaining possibilities. I find it easiest to organise by NATIONALITY, like so: 

Nationality	Norwegian	Englishman	Japanese	Italian	Spaniard
Number	1	3, 5	2,3,4,5	2,4	3,4,5
Color	Yellow	Red	Blue, White, Green	Blue, White	Green, White
Job	Diplomat	Violinist, Physician, Photographer	Painter	Violinist, Physician, Photographer	Violinist, Physician
Drink	Mineral Water	OJ, Milk	Coffee, Milk	Tea	Coffee, OJ, Milk
Pet	Zebra, Fox	Zebra, Fox, Snails	Horse, Fox, Zebra	Horse, Fox, Zebra,Snails	Dog

We've reduced the number of remaining combinations significantly. 

4. From this point we can take a gamble and place the Englishman. There are two possibilities: because the WHITE and GREEN HOUSES are adjacent, one of them has  to be HOUSE 4. Therefore, the Englishman is either in HOUSE 3 or 5. So one of these scenarios is correct:

3	4	5	#	3	4	5
			#
			#
			#
Milk			#	Milk

5. If the Englishman is in HOUSE 3, then he must drink MILK. If so, then the Japanese man must drink COFFEE and therefore lives in the GREEN house. We continue through eliminating duplicates until we get this:

Nationality	Norwegian	Italian	Englishman	Spaniard	Japanese
Number	1	2	3	4	5
Color	Yellow	Blue	Red	White	Green
Job	Diplomat	Physician	Photographer	Violinist	Painter
Drink	Mineral Water	Tea	Milk	OJ,	Coffee
Pet	Fox	Horse	Snails	Dog	Zebra

Go back and check to see if all clues match this table. If so, then we've solved it. We were lucky in choosing HOUSE 3 for the Englishman first. However, if we had tried HOUSE 5 and found a logical inconsistency, we would have known immediately that the Englishman was in HOUSE 3.

After I had solved the puzzle this way, I discovered these grids online:

 In these grids, you place a circle for fields that match (i.e. Englishman in Red House). Then you place crosses through the remaining columns and rows (So X's would go in the Red column for the remaining people.)

I'm not sure which method is faster.