Inspired by Edi Weitz' solution to Einstein's Riddle in Common Lisp (via O'Reilly Radar), I used Andy Chun's NSolver constraint programming library to solve the program using .NET.
Here's a sense of what C# / NSolver looks like:
//The green house's owner drinks coffee
>Post(greenHouse.Eq(coffee));
//The person who smokes Pall Mall rears birds
Post(pallMall.Eq(birds));
//The owner of the yellow house smokes Dunhill
Post(yellowHouse.Eq(dunhill));
On my 1.5Ghz, 768MB RAM Tablet PC, NSolver can solve the problem 100 times in .79 seconds. C# source code (165 lines).
>