The Einstein's Puzzle is a well-known logic puzzle. It is often called Einstein's Puzzle because it is said to have been invented by Albert Einstein as a boy. However, there is no known evidence for Einstein's or Carroll's authorship. This puzzle can be modified with various conditions to produce a variety of similar puzzles. For starters, we will solve a simplified version of the puzzle.

There are 5 houses on street which are painted 5 different colors: blue, green, red, white and yellow.
In each house lives a person of a different nationality: Brit, Dane, German, Norwegian and Swede.
These people drink a certain beverage: beer, coffee, milk, tea and water.
Smoke a certain brand of cigarettes: Rothmans, Dunhill, PallMall, Winfield and Marlboro.
They keep a certain pet: cat, bird, dog, fish and horse.

None of the owners have the same pet, smoke the same brand of cigarette, or drink the same beverage.

You are given a set of "relations". Each relation connects two identifiers in the owner relationships. For example: "Norwegian-Dunhill" indicates that the Norwegian smokes only Dunhill. "5-dog" indicates...