Strategies, pattern identification and effective methods enable quick solution
In this popular logic analysis reasoning puzzle, five nationals live in five differently colored houses, keep five different pets, drink five different fluids and smoke five different brands of cigarette. From 15 given statements, you have to answer—who owns the fish?
After solving it more than one and half years back, by chance I discovered that the problem is the popularly known Einstein's puzzle or Einstein's riddle. You may go through this earlier straightforward solution in the following link,
A few months ago as I went through this earlier solution, I couldn't but ignore a few blemishes. In this session I have removed these shortcomings and explained the new solution as transparently as possible.
I have referred to terminologies of strategies, techniques and methods used for solving the puzzle, but also explained why the techniques are effective and how the methods are to be used. Goal is—anyone of you should be able to understand how the problem is solved and learn to use the strategies, techniques and methods and if possible—improve these. Expected outcome—your interest and involvement.
Let's proceed by first stating the problem and going through the solution step by step.
Who keeps the fish?
Can you find out in 20 minutes? Well, that is the standard time limit for this puzzle. If you have time in your hands, go on till you solve it.
This is one of the most well-balanced puzzles I know of and I am sure you will enjoy when trying to solve it.
The efforts to analyze and reach the solution is more important than the solution itself.
1 The Brit lives in the red house.
2 The Swede keeps dogs as pets.
3 The Dane drinks tea.
4 The green house is on the left of the white house.
5 The green house's owner drinks coffee.
6 The person who smokes Pall Mall rears birds.
7 The owner of the yellow house smokes Dunhill.
8 The man living in the center house drinks milk.
9 The Norwegian lives in the first house.
10 The man who smokes Blends lives next to the one who keeps cats.
11 The man who keeps the horse lives next to the man who smokes Dunhill.
12 The owner who smokes Bluemasters drinks beer.
13 The German smokes Prince.
14 The Norwegian lives next to the blue house.
15 The man who smokes Blends has a neighbor who drinks water.
Solution: Problem analysis and nature of the problem
There are six variables or dimensions (as I call it) in this problem—House each with a specific position, Color of house, Occupant each with a specific nationality, Pet, Drink choice, and Smoking choice. Each of these variables has five unique values.
Assuming that this is a well-formed logic puzzle with a unique solution, we understand by a brief scan through the problem description, that when fully assigned, there will finally be five unique combinations of values of six variables.
In other words, values of the six variables (five for each variable) have to be assigned one-to-one. Simply speaking, no single variable value can be assigned to two values of another variable.
For example, an occupant of a specific nationality living in a house of a fixed position of unique color, has a unique pet, drinks a unique drink and smokes a unique brand of cigarette.
Thus the problem involves one to one assignment between six sets of variable values.The one-to-one assignment property makes solution simpler.
A possible combination might be (but not necessarily be so),
The Swede living in blue house on the rightmost position smokes Dunhill, drinks beer and keeps dogs as pets.
Though the problem was to find whose pet is the fish, a specific single goal, it may turn out that while the assignments are carried out systematically through logic analysis, the whole of the logic table may get fully assigned, thus automatically giving the solution.
At first glance the logic puzzle may seem daunting unless the problem solver is naturally gifted or used to logic analysis of various forms.
Solution: Logic representation
We need to analyze the fifteen given logic statements to find out who owns the pet fish. These statements are also called logic statements, and this kind of problem, reasoning and logic analysis puzzle.
While we analyze the 15 logic statements one by one, we need to write down the results at every step so that we can analyze the next logic statement along with the results of analysis achieved thus far. Gradually the results will get more enriched and move towards the solution.
To write down the results of logic analysis up to any stage, we will use the most compact logic representation in the form of fully collapsed column logic table with five columns and five rows.
The houses identified by their positions form natural column labels with position embedded in each. The other five variable names form the row labels. For example, the column labels will be from left to right—House 1, House 2, House 3, House 4 and House 5 with House 1 being the leftmost and the first house and House 3 being the center house.
The row labels become then, Color of house, Occupant nationality, Pet, Drinks and Smokes.
Note: At first it may seem occupant should be the column header. But assigning house as the primary variable is more natural, as from the logic statements we find each house has a fixed relative position with each other. This relative position property of a house simplifies the solution process if we put the house as the column header. This is why house is the natural choice for the column header. I call the column header variable house as the primary variable to which values of all the other 5 variable values are to be assigned.
Choice of primary variable and forming the logic table correctly is important.
The empty logic table is shown below. The job in hand is to fill up the 25 cells, or better still, find who owns the fish by analyzing the 15 logic statements.
At first it seems we need to find all the five unique combinations of six variables filling up all 25 cells of the logic table. But on review of the problem, we perceive that we need just to find who owns the fish, even if some cells remain empty. This is then our main objective.
Additionally, in this improved solution, we will try to find the answer in as few steps and as quickly and simply as possible. This is our methodological objective.
To achieve these objectives, throughout the solution process we will use powerful strategies, patterns and methods that are effective in solving these puzzles and are accumulated purely through solving many logic puzzles and Sudoku problems. These strategies and techniques are based upon common sense reasoning and I will explain the mechanism of each.
Solution: Logic analysis stage 1: Direct assignment first strategy and link search technique
While solving this type of problem it is essential to form a strategy of processing the logic statements. Going serially from the first to the second and so on generally will end up into hopeless confusion.
First strategy: Direct assignment first
The most important strategy at the start is to process those statements that make certain and definite assignments to any of the cells. We call this strategy as the direct assignment first strategy.
Note: This makes sense at the start, as out of total uncertainty of all empty cells, a statement that states clearly with certainty that a variable value belongs to a single cell of the empty table must have the highest priority of processing.
In this problem, such a statement must have mention of a house by its position.
As a specific national lives in a house at specific position and except color of the house, all the other three variables, Pet, Drinks and Smokes are actually attributes of the national, preference will be given to a statement in which a specific national is involved.
With these decisions, the "Statement 9. The Norwegian lives in the first house." is chosen as the first statement to be processed. This statement puts national Norwegian firmly in House 1 and accordingly the corresponding cell in the table is filled up.
Second strategy: Link search technique
Any statement that refers to the already assigned national and additionally helps to make another certain assignment is chosen next. This assignment by link or reference technique is extremely valuable and is used as soon as we get certain of a new value in the table. This is called link search technique.
Accordingly, "Statement 14. The Norwegian lives next to the blue house." is processed second putting color blue to the House 2. This is so because there is no house on the left of Norwegian's first house. It is use of elementary logic analysis which forms one of the main foundations of logic puzzle solving.
Third strategy: Repeat direct assignment first and link search
When we get "blue" as the color of second house, we search for any statement that refers to "blue" and gives us another certain assignment. This method we follow as part of link search technique. In this case though we don't have such a statement. Link search chain, as I call it, ends here.
But what about direct assignment statements? Is there any more left? This is what I call repeating direct assignment first and link search strategy. It is a combination of the two with repeating element and produces maximum certain assignments quickly in this first stage.
Searching for the second direct assignment, we locate "Statement 8. The man living in the center house drinks milk.", that enables us to assign milk in the Drinks cell below the House 3 column.
This exhausts the first stage and the logic table result is shown below.
Solution: Logic analysis stage 2: Bonded member structures on same variable with highest potential
With no further reference to already assigned values "Norwegian", "milk" or "blue" and no more direct assignment statements available, we have to adopt a new strategy based on a new pattern that we call temporary bonded member structure. Such structures can be formed on same variable values or values of different variables. Preference is for the first type of temporary bonded member structure on same variable values.
Fourth strategy and pattern
When a logic statement refers to two (or more than two) values of same variable, and mentions positional relation of the values (column-wise), we get what we call, a temporary bonded member structure on same variable. Mark that the related values in a temporary bonded member structure of this type must be of same variable, and in this case must belong to the same row.
If there is more than one such statement forming temporary bonded member structures, the statement that spans largest number of bonded cells of a row is selected to be of highest potential.
In our problem we identify "Statement 4. The green house is on the left of the white house.", as the only one forming a temporary bonded member structure of color of house, green on the left of white. This is the positional relation.
By elementary logic analysis we can easily conclude that colors green on the left of white can only be assigned to House 3-House 4 or House 4-House 5, as the first two houses are already blocked.
We call this situation of only two possibilities as two degree uncertainty that is considered as partially certain and preferable. We can write down these two partially certain possibilities easily in the logic table. Because of only two possibilities, this has a high probability of a later statement removing one possibility by conflict and convert the remaining one as certain. Certainty is the main goal we strive for.
Thus by Statement 4, we get a temporary bonded member structure on same variable with two degree uncertainty. The following state of logic table will show how we record this temporary bonded member structure.
With limited possibilities of green and white, now we search for a statement following our dependable link search technique, that refers to either green or white as well as creates new certain assignments.
Such a statement we find in "Statement 5. The green house's owner drinks coffee.", which conflicts with Drinks value of House 3 for green color and thus eliminates this possibility, leaving green color and Drinks coffee for the House 4 with certainty. Color white automatically is assigned to House 5. At one go we have three certain assignments.
This kind of logic analysis thus plays an important role in quickly completing the assignments.
Here we have used first link search technique on the values of temporary bonded member structure green-white and then principle of conflict to achieve multiple certain assignment.
Now perhaps you can realize the potential of creating and using a temporary bonded member structure. A little further on we will use another advanced form of temporary bonded member structure to break a bottleneck.
The result of processing the Statement 5 is shown below.
We could have processed the 4th and 5th statements together, but for showing the mechanism of the combined strategy we have separated out the two steps.
Solution: Logic analysis stage 3: Focus on most filled row and elementary logic analysis
We applied the earlier strategies during the initial stages when the logic table was nearly empty. But as the logic table now is fairly filled up and also the patterns used in the earlier strategies are no longer available, we look for new and easier opportunities.
Fifth strategy: Focus on the most filled row or column and search for conflicts
By this strategy, basically we look for conflicts resulting in certain assignments. It makes sense that,
A row or column that is filled up with maximum number of cell values, or having minimum number of empty cells will have the highest potential for a statement creating a certain assignment.
The target row at this stage is the row of house color, and as expected, the "Statement 1. The Brit lives in the red house." provides us the certain assignment by conflict.
The elementary logic analysis is straightforward. Colors of House 1 and House 3 are still not known and as the Norwegian lives in House 1, the red colored house in which the Brit lives must be the House 3. Certain assignment is achieved by conflict in nationality and color couple.
Sixth strategy and pattern: certain assignment by exclusion
This is a very favorable condition when out of a set of values for a variable only one value is left to be assigned as well as only one cell is left empty for the variable. The last value automatically gets assigned to this remaining cell.
In our problem by this strategy, yellow color is automatically assigned to House 1.
Now applying link search, "Statement 7. The owner of the yellow house smokes Dunhill." is chosen as it links already assigned color yellow with Smokes variable value.
In the same way, "Statement 11. The man who keeps the horse lives next to the man who smokes Dunhill.", is processed next, assigning horse as pet against House 2.
The Statement 7 and then Statement 11 together provide us with an example of what we call—a chained link search.
The other observation: these last three certain assignments fall under the category of Easy pickings, as these are easily and quickly obtained. The logic table at this stage is shown below.
At this stage let's stop for a moment and take stock.
We have processed more than half of the 15 logic statements filling up less than half of the 25 logic cells, but also exhausted all possibilities of any of the previously used strategies and patterns. No easy pickings and no reference of any of the certainly placed 11 values in the logic table left in the remaining 7 logic statements.
On the plus-side, we have filled the house color row completely and managed to put the first pet horse to its rightful owner, the owner of the second house.
We must then use a completely new strategy and pattern with its associated method to break this bottleneck.
Solution: Logic analysis stage 4: Temporary bonded member structure on two variable values, use of multiple statements, Possibilities, and Cycle
Earlier we hinted—when no easy avenue towards solution is visible, form a temporary bonded member structure. Now also we will do that. We will form temporary bonded member structures not on same variable values (because there aren't any statement left to do that), but on values of different variables.
We repeat the most potent strategy in solving difficult reasoning puzzles,
When no easier path towards solution is available, form and use temporary bonded member structures.
Knowing this, we pick up "Statement 3. The Dane drinks tea." and "Statement 12. The owner who smokes Bluemasters drinks beer.", to check the columns in which we can place these two pairs of values of different variables. Quickly we find that the two temporary bonded member structures on different variables, Dane-tea, and Bluemasters-beer can be placed in House 2 and House 5 columns or vice-versa. These create two possibilities with two-degree uncertainty and we are not able to write this information on the main logic table easily. So we combine these two results and create what we call—two Possible scenarios (multiple logic table possibilities), or simply Possibilities below the main table and separate from it.
Top part of the following figure represents these two possibilities where for brevity we have not shown the main logic table.
As these are two different possibilities we cannot merge any of these two with the main logic table. Instead we would keep the possibilities separate from the main table and continue processing rest of the statements with the goal of proving one of the two possibilities as invalid and merge the valid one with the main table. In solving any complicated reasoning puzzle you may have to adopt this advanced pattern and method based strategy.
When we analyze the two possibilities, our attention is drawn naturally to the Drinks values. We find a wonderful new structure waiting to be formed in this Drinks row. Observe that the two values "tea-beer" can be placed only in two cells of the same Drinks row under House 2 or House 5. This is essentially a temporary bonded member structure of two-degree uncertainty on same variable but with reverse positional relationship. If House 2 occupant drinks "tea", House 5 occupant must be drinking "beer", and vice-versa.
We call this powerful new structure as a Cycle, as the two values of the same variable cycle through the two cells and effectively block these two cells from placement of any other Drinks value. This cycle is represented in the lower part of the above figure.
The cycle blocking two Drinks values and two Drinks row cells, the remaining Drink "water" gets automatically assigned to occupant of House 1 by exclusion.
Applying link reference we identify "Statement 15. The man who smokes Blends has a neighbor who drinks water.", and assign "Blends" to occupant of House 2. This invalidates the Possibility 2 and "Bluemasters" with "beer" are assigned to occupant of House 5 and "Dane" with his drink "tea" are assigned to House 2.
This is a critical analytical step and you should check for yourself till fully satisfied.
The difficult obstacle is now broken through by the combined use of temporary bonded member structure on two variables, creation of two Possibilities and finally a Cycle. This is the most important breakthrough in whole of this beautiful problem.
From this point on, the rest are all easy pickings and even without writing the assignments you can tell the correct answer. Still for ease of explanation we will go ahead with the rest of the solution.
The first assignment now is straightforward—with Smokes row nearly full, "Statement 13. The German smokes Prince." is processed next for certain assignment by conflict with Smokes value Bluemasters.
The state of the logic table is shown below along with the four statements that we processed after the previous stage.
Solution: Logic analysis final stage: Exclusion and link reference—all easy pickings
First by exclusion on Smokes row, we select "Statement 6. The person who smokes Pall Mall rears birds.", then by direct assignment "Statement 2. The Swede keeps dogs as pets.", and lastly by link reference, "Statement 10. The man who smokes Blends lives next to the one who keeps cats.", leaving Fish for the German.
The final state of logic table is shown below.
Interesting, isn't it!
This is the most well-formed and balanced reasoning puzzle I have come across. Patterns and methods do take away the mystery of a puzzle somewhat but takes one forward on the path of identifying, forming and using new patterns and methods in unraveling mysteries of new problems.
Puzzles you may enjoy
Logic analysis puzzles
How to solve Einstein's puzzle whose fish confidently, improved method based solution