You can skip this ...

Real problem-solving does not follow a predefined path where you set out at square one, proceed orderly square after square until you finally pass Start and collect 2000$. At best it is like making the first attempt on a mountain - only guessing a possible approach: advancing, retreating and improvising. At worst it is like cutting your way through the most vicious jungle - the further you go the less likely it seems you will ever reach your destination ...

The Einstein-puzzle was real problem-solving as far as Pro/3 was concerned. The problem did not fit very well into Pro/3's problem solving framework, however the problem was indeed solvable with Pro/3's knowledge base clustering concept. This presentation of a model used to solve Einstein's Puzzle is not an introduction to Pro/3. However, some aspects are illustrated well. Note especially the natural language interface, which permits hints to be entered very closely to the original English-language problem statement. Simply ask Pro/3 which national keeps the fish pet (after inputting the facts and rules described here and after running), and Pro/3 convincingly will respond that national ... keeps the fish pet. 

Introduction

Five lots numbered from 1 to 5 (from left to right) are introduced in the solution presented here, such that the leftmost house stands on lot 1, while the rightmost house stands on lot 5. If the wider problem of locating each member of the five categories on the five lots is solved, then the fish-national problem solution follows (i.e. the national on the same lot as the fish is the national who keeps the fish). The model presented here solves the wider problem. 

The members of one category can be listed in 5! (=120) different ways. The different ways of locating members of the five categories on the five lots is then 120⁵  (=24,883,200,000) - almost 25 billions! If we systematically went on and generated combinations until we found one which did violate any of the hints, then even at a rate of 100 combinations evaluated per second, we would have to spend up to 7.9 years ...

Typing conventions

Knowledge represented in Pro/3's syntax is shown bold letters. The original hints are shown in bold italics. 

Representing the basics

Pro/3 understands knowledge expressed in natural language sentences, given that the appropriate terminological and structural knowledge have been specified. This will not be explained further here. Refer to sentence modeling for details.

We start by asserting the existence of the members of the five categories e.g. the red house exists, the British national exists, the fish pet exists etc. (ref. complete model).

Note that there is nothing magic about the exists verb here - we could have used is defined, is known, is used in the Einstein Puzzle etc. The use of the exists-sentences will become apparent in the presentation of some of the rules under.

Overall problem-solving strategy

The overall problem solving strategy is to find out as much as possible about the wider problem described over, i.e. the relationship between the member of the five categories and five lots. The following terminology is adopted:

• house stands on lot
• national lives on lot
• beverage is consumed on lot
• cigarette is smoked on lot
• pet is kept on lot

Introducing rules - the first hint

Pro/3 supports different types of rules, however we will only need one type in this model, that is, the simple implication rule type. Very briefly, a simple implication rule specifies how sentences can be derived from other sentences. Refer to What is rules? for details.

Let's look at the first clue - the Brit lives in the red house. In the context of the overall problem solving strategy, it tells us that if we know the lot where the Brit lives, then we also know the lot where the red house stands. Formulated in Pro/3's syntax this is written as if the British national lives on lot L, then the red house stands on lot L (L is a variable). 

What if we happened to know or to infer the lot where the red house stands, but not the lot where the Brit lives? Clearly, the rule would not bring us any further. The reversed rule would be useful in this case, i.e. if the red house stands on lot L, then the British national lives on lot L.

Generally we need both, and that is not un-problematic in Pro/3. The two rules together represent a cyclical dependency where location of houses depend on location of nationals, and location of nationals depend on location of houses. Pro/3 cannot handle this directly - a work-around must be resorted to. The work-around is the use of clustered knowledge bases (KBs). The rules must be distributed between KBs in the cluster such that each KB remains acyclic. In reality only two KBs are required.

As mentioned, real problem-solving always involve improvisations, trial and error. You suddenly realize that your approach only reached that far, and you have to re-assess and modify your strategy. In this case, you will eventually discover that knowing that a national does not live on a particular lot, is almost useful as knowing if a national does live on a lot. These inferences are of course interrelated. If you know that A,B,C and D do not live on a particular lot, then clearly the only remaining national E must be living there. 

Consequently to the insight over, we adopt five additional sentence types:

• house does not stand on lot
• national does not live on lot
• beverage is not consumed on lot
• cigarette is not smoked on lot
• pet is not kept on lot

and add two rules corresponding to the two rules previously described:

• if the British national does not live on lot L, then the red house does not stand on lot L!
• if the red house does not stand on lot L, then the British national does not live on lot L!

Hints following the pattern of the first hint

Other simple hints

Two hints do not need to be represented as rules. They can be directly represented as facts (sentences):  the person in the center house drinks milk and  the Norwegian lives in the leftmost house. However, to be very explicit, a fact and a rule has been used for the second of these hints i.e. to define the interpretation of the "leftmost house" if national X lives in the leftmost house, then national X lives on lot 1. Refer to the complete model for details.

"house is on the left side of house"

The hint that the green house is on the left side of the white house is entered as a fact, however, a series of rules have been defined as well to possibly pin this knowledge down to relations between houses and lots. The fact itself is entered word by word as the given hint. Then there is one rule which states that a house which is on the the left side of another house cannot possibly stand on lot 5, if house X is on the left side of house Y, then house X does not stand on lot 5, and a corresponding rule which states that a house which has another house on its left side cannot stand on lot 1, if house X is on the left side of house Y, then house Y does not stand on lot 1.

Note here that the more obvious rule, if house X is on the left side house Y and house X stands on lot L, then house Y stands on lot (L+1), is not valid in Pro/3. The reason is that the rule is self-referential - it contains the same sentence type (house stands on lot) in both condition and conclusion. This is the same issue as cyclical dependency discussed over. Refer to the discussion on sentence derivation for details. 

With this limitation in mind we have to look for rules which conclude the lots where a given house cannot stand. The facts stating the existence of the five lots are used in these rules. Given that a house is on the left or the right side of a house known to stand on a particular lot, then it is trivial to state where the house does not stand - if house X is on the left side of house Y, house X stands on lot Lx, lot Ly exists and Ly<>(Lx+1), then house Y does not stand on lot Ly and if house X is on the left side of house Y, house Y stands on lot Ly, lot Lx exists and Lx<>(Ly-1), then house X does not stand on lot Lx.

Neighbor hints

Neighbor-relations are somewhat imprecise in the way that a known lot of something cannot be used to directly infer the lot of the neighbor (i.e. the location can be on either side) - unless of course we know that we are on the leftmost or rightmost lot. Without, this knowledge we have to look for rules concluding where the neighbor is not located. 

Consider the hint that the person who smokes Blend lives next to the person who keeps a cat. The first two rules are obvious: if the cat pet is kept on lot 1, then Blend cigarettes are smoked on lot 2; and if the cat pet is kept on lot 5, then Blend cigarettes are smoked on lot 4. Then the reversed rules: if the cat pet is not kept on lot 1, then Blend cigarettes are not smoked on lot 2; and if the cat pet is not kept on lot 5, then Blend cigarettes are not smoked on lot 4.

The last three rules state where the Blend cigarettes are not smoked (utilizing the know se of five lots) - if the cat pet is kept on lot L, then Blend cigarettes are not smoked on lot L; if the cat pet is kept on lot Lx, lot L exists and L<(Lx-1), then Blend cigarettes are not smoked on lot L; and if the cat pet is kept on lot Lx, lot L exists and L>(Lx+1), then Blend cigarettes are not smoked on lot L.

All the seven rules over utilizes knowledge of cat locations to infer where Blend cigarettes are smoked. However, cat locations could be elusive while Blend-smoking locations could be known, so we need the seven reversed rules as well - if Blend cigarettes are smoked on lot 1, then the cat pet is kept on lot 2; if Blend cigarettes are smoked on lot 5, then the cat pet is kept on lot 4 etc. Refer to the complete model for details.

There are three more hints involving neighbor relations: the person who keeps a horse lives next to the person who smokes Dunhill; the Norwegian lives next to the blue house; and the man who smokes Blend has a neighbor who drinks water. These rules follow exactly the same pattern as the cat-Blend rules:

Almost there ...

The last batch of rules define basic assumptions of the problem. The rules apply to locations of all the five categories e.g. house locations. If it is known that a given house does not stand on four particular lots, then obviously it has to stand on the only remaining lot - if house X exists, Ns=the number of sentences where the house X does not stand on lot Ld, Ns=4, lot L exists and false (the house X does not stand on lot L), then house X stands on lot L (Ld is a dummy variable). A similar logic applies to a given lot where it is known that four different house do not stand, i.e. the only remaining house must stand there - if lot L exists, Ns=the number of sentences where house Xd does not stand on lot L, Ns=4, house X exists and false (the house X does not stand on lot L), then house X stands on lot L.

Then of course - a house can stand on only one lot: if house X stands on lot Lx, lot L exists and L<>Lx, then house X does not stand on lot L; and finally, a lot can only accommodate one house: if house X exists and the house with color<>X stands on lot L, then house X does not stand on lot L. 

The are six corresponding rules each for nationals, beverages, cigarettes and pets. Refer to the complete model for details.

Who keeps which pet?

To enable the model to answer the who keeps the fish pet question directly, it will be necessary to use the rule if national X lives on lot L and pet Y is kept on lot L, then national X keeps pet Y. We can also include directly the hint that the Swede keeps the dog - the Swedish national keeps the dog pet.

Step-by-step creation of the Pro/3 Model