Zebra Puzzle Terminator: A general automatic reasoning system solving method

Background

Among the many logic puzzles in the world, the Zebra Puzzle is the one of the most famous. It was first published on December 17, 1962 by Life Magazine, an old weekly magazine owned by Time Warner, and it claimed that only 0.1% of people in the world can solve it. The original puzzle is as follows:

Zebra Puzzle: Who drinks the water? Who owns the zebra?

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Life Magazine did not publish the puzzle’s solution. When it was released, the Zebra puzzle gained attention from logic puzzle fans all over the world who would then challenge their friends and it spread like wildfire. On March 25, 1963, the names of hundreds of people who successfully solved the puzzle were published in that month’s edition of Life Magazine.

The Zebra puzzle is now often referred to as Einstein’s puzzle and some say it was invented by Einstein as a boy. In actuality, there is no real evidence that Einstein did invent the puzzle. The cigarette brand Kools mentioned in the original puzzle did not exist during Einstein’s boyhood. The version of Einstein’s puzzle that is widely circulated today is a variant of the above Zebra puzzle. Some claim that Einstein once asserted that 98% the world’s population would not be able to solve it. The puzzle is as follows:

Einstein’s Puzzle: Who keeps the fish?

1. The British man lives in a red house.
2. The Swedish man keeps dogs as pets.
3. The Danish man drinks tea.
4. The Green house is next to, and on the left of the White house.
5. The owner of the green house 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 horses lives next to the man who smokes Dunhill.
12. The man who smokes Blue Master drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The Blends smoker lives next to the one who drinks water.

For a problem in the form of the above two puzzles, this is essentially a classic logic problem. It has important experimental significance in mathematics, logic, and computer science because it can reveal to some extent what intelligence is, how logical reasoning works and how to empower machines to create artificial intelligence.

Problem Analysis

Using computers to solve logic puzzles has been always a common topic and one brute force method is to enumerate every possible situation before deciding. For both the Zebra puzzle and Einstein’s puzzle above, there are 5 dimensions (Nationality, Color, Pets, Drinks, Cigarettes) that need to be connected to the appropriate house. For any dimension, the possible choices are 5 × 4 × 3 × 2 × 1 = 5!, there are (5!) ⁵, or 24, 883, 200, 000 (about 25 billion) possibilities in total for five dimensions (See Table 1). A well-written program can solve this in seconds on a capable computer. The traversal determination is completed within minutes. This enumeration selection and decision method is essentially a brute force method of an exhaustive search space in which there is no intelligence at all.

Table 1: Searching space

We can also think of such puzzles as Constraint Satisfaction Problems (CSPs). A CSP is a special type of problem that involves a set of variables and a set of constraints between them, finding one (or multiple) assignments such that all constraints are satisfied. For a constraint satisfaction problem with limited definitions, it can be solved with a traditional backtracking search in which the variable selection strategy is optimized by the minimum remaining value, the most constrained variable and failure priority strategies. This method is obviously more rational and closer to the way people think.

In addition to the brute force method and the CSP solution method above, is there any other solution method for this logic puzzle? Is it possible to build a general automatic reasoning system for it? This needs to be viewed from the perspective of human thinking.

The brain structure and intelligence level of different people often reveal huge differences when solving problems. A relatively clear difference is the ability of logical reasoning. Logical reasoning is essentially a form of thinking that logically deduces some new knowledge (conclusion) based on some known knowledge (premise). The process of people’s cognition of the objective world is essentially the process of observing, identifying, naming, measuring various objects in the real world and connecting these basic cognitive components to build a cognitive building.

The reasoning process from individual to general, or general to individual, can be summarized as deduction and induction. We generally start from various concrete individuals and continue to abstract and summarize to form “abstract” concepts, then summarize them into general principles and laws. On the other hand, based on the existing knowledge system and the known rules and laws, we will carry out the knowledge application process for the newly emerged concrete individuals in turn. Just like a credit scoring mechanism, this is nothing more than an artificial evaluation model or system based on collected financial data, personal data, etc. of various users, that then evaluates new credit card applicants to determine whether or not to grant, what the credit limit is, what the risk is, etc.

The difference between machines and humans is very significant in several aspects. The memory capacity and computing power of computers can be expanded infinitely, especially cloud computing, which has raised this ability to a new level. No matter how good the human memory is, it is not comparable to those well-organized and indexed knowledge base systems that exist on hard disks or in the cloud. No matter how good the human mental arithmetic ability is, it cannot deduce the recursive processing and stack-type repetitive processing of the computer. No matter how sharp the human eye is, it cannot be compared with the bit-level discrimination ability of the color components of a pixel. However, our human brain is capable of innovation, intuition, perception, high abstraction, and derived wisdom, which is the advantage of our carbon-based life over silicon-based machines that need electricity to operate.

Human Perspective

Let’s analyze how a “human” with strong logical reasoning ability solves the Zebra puzzle. From all the puzzle’s statements, we can perceive various entities, that is, images constructed by the identification and naming of various real-world entities, including Englishman, red house, Spaniard, dogs, etc.; similarly, we deconstruct the relationship between entities from some verbs or prepositions, such as… lives…, owns…, drinks…, to the right of…, etc., this relationship is also an entity in essence.

Secondly, according to the relationship between entities in the real world, people will establish corresponding connections in the brain, and abstract higher-level category concepts, such as nationality, color, pets, drinks, cigarettes, and other concepts according to the type of connection. Among them, you can also see that concepts like “nationality” are almost purely virtual. These virtual entities are developed based on the needs of human beings to organize society. There are almost no physical entities except an ID number to prove this. Also, you can’t say someone is a stateless person if the passport is not issued or lost!

Therefore, according to the order of the puzzle statements, we can summarize 5 dimensions (corresponding variables) according to the entity type, the nationality of the homeowner, the color of the house, pets, drinks, and cigarettes. From this, we can list 5 explicit dimensions and their possible values (in order of appearance in the puzzle). Undoubtedly, these variables are nominal:

• Nationality: British, Spaniard, Ukrainian, Norwegian, Japanese
• House: red, green, ivory, yellow, blue
• Pets: dog, snails, fox, horse
• Drinks: coffee, tea, milk, orange juice
• Cigarettes: Old Gold, Kools, Chesterfields, Lucky Strike, Parliaments

Wait, there’s another dimension hidden in the puzzle: the location of the house. This is an entity relationship identified based on the words “to the right of,” “in the middle,” “next to,” “in the first” and other concepts in the statement set, so we should establish a concept in our mind to express the order relationship between entities. The most straightforward way is to number them sequentially: 1, 2, 3, 4, 5. Thus, position variables are ordinal variables that not only contain differences but also describe differences in their order or rank.

At this point in the puzzle, the solution to the problem “Who drinks water and who owns zebras?” becomes searching for the mapping relationship of entities in the above six dimensions. The essence of knowledge is connections, so the intelligence based on this model is the process of establishing principles and criteria and applying them to solve, predict and change the future.

Everyone uses different strategies when dealing with problems and even the same person will use different strategies in the derivation process. The 6-dimensional variable is enough to confuse most people’s minds – “how to choose the next statement to get a solution as quickly as possible” is the key to solving the problem! Like the minimum remaining strategy for constraint satisfaction problems, we can usually use the deterministic highest strategy to reason forward and use elimination strategies to reduce the solution space.

When people reason, they often begin with a certain statement (knowledge), then apply knowledge to uncertain statements and constantly accept and exclude uncertain statements. Uncertain means that there are multiple possible distributions for the same statement. If there are multiple possible branches, hypothetical reasoning will be used to select one of the limited possible paths to try until the result meets the maximum statements accepted. If there are too many branches of uncertainty, the process degenerates into a search process.

For a logic puzzle, we also need to consider whether its final solution is unique and how many variants of methods (paths) there are to solve it. That is to say, the former can be obtained by the fastest method, while the latter is more complicated and needs to be traversed on the equivalent branch to obtain all possible paths.

Implementation perspective

Based on the above thinking logic, we can use SAS to design a model-oriented automatic reasoning system. It takes the tagged text as the input and outputs the answer text for a query. The so-called general automatic reasoning means that it must be abstract enough and completely centered on an abstract model, which means that it should be able to solve arbitrary logic puzzles without changing any code. The solver itself should not have any domain-related formulas or constraints. The difference between it and the constraint satisfaction problems solver is that the constraints are contained in the model generation stage, rather than determined in the solving stage. The overall design (Figure 1) is as follows, and currently you can click here to download the precompiled SAS code for preview, but it can only run in English, Unicode or Simplified Chinese SAS 94M7+(WIN) or SAS Viya(LAX) environments.

Figure 1: Overall design

Due to the constraints being parsed and implied in the generated model from statements, an automatic reasoning system can be a pure model structure-based solver which does not contain any predefined domain-specific knowledge. The solution generated by the reasoning system is just a subset of the model that can be further processed or presented. The boundaries between humans and machines are limited to model generation and question answering. Thanks to this, a statement set can be any set of finite constraints, whether it is a zebra puzzle, a simpler Einstein’s puzzle or a more complicated blood donation puzzle that can be solved by the same reasoning system. They differ only in the statement set and the questions. The practice has proved that according to the above principles of human thinking, all zebra-type puzzles can be resolved by the same system as they are essentially the same.

Since machines cannot automatically identify different dimensions or variables from entities and relationships like humans, we need to provide a minimal set of tags in the statement set, which can be in the form of a parsimonious [N:Englishman] keyword tag or form such as <Entity Type=”N”>Englishman</Entity> XML markup. The following table (Table 2) lists the statement set of the Zebra puzzle which consists of 14 statements. This labeled statement set is the only input of the reasoning system.

Table 2: Tagged Statements as input

%SolvePuzzle(input=Zebra_en, question=%str([N:Who] drinks [D:Water],[N:Who] owns [P:Zebra]));

The above statement set is parsed and a model is generated. The type of the annotation, i.e. the variable type is a key factor. In the Zebra puzzle, all variables are nominal except the Location, which is an ordinal variable.

To solve a single solution, the termination condition is that all statements are accepted (satisfied). As the reasoning system proceeds, it must maintain two queues: accepted knowledge and rejected knowledge. We know that when we accept new knowledge, we may accept more compatible knowledge. We may also reject some contradictory knowledge; when we reject a piece of knowledge, if it is propagatable in logic, we will also reject more associated knowledge. This is an active elimination strategy. The method of solving all solutions shares this reasoning logic with solving a single solution, but the outer structure is different.

Given the specificity of Location variables in Zebra puzzle, determining the mapping of other categorical variables on the Location variable is a key point. Various zebra puzzle variants have an ordinal variable, when we accept a statement, determining the value of the Location  variable is the most critical step, so the reasoning system should expose it. The following table (Table 3) shows the reasoning steps of the system for the zebra puzzle, where L is the location of the house:

Table 3: Reasoning Steps as output

The result of the reasoning steps can be presented in a more intuitive matrix as follows (Table 4):

Table 4: Reasoning Result

The system can also print the detailed solution process in the form of matrix according to the reasoning steps (Table 5) :

Table 5: Reasoning Result step by step

For the solution results, we can ask any reasonable question in the form of text and let the system return an intuitive answer. Note that the question must be in the tagged form above with question-condition pairs, that is, the sequence of forms in which the question comes first, and the condition comes after. For example:

 %QueryAnswer(question=%str([N:Who] drink [D:Water]，[N:Who] owns [P:Zebra]));

Table 6: Reasoning Answer for question

In fact, we can ask the system to answer all kinds of valid questions, whether they are known or unknown conditions in the statement, such as:

%QueryAnswer(question=%str([P:What] was kept by [N:Spaniard]，[N:Who] smokes [C:Chesterfields].));

Table 7: Reasoning Answer for question

As a puzzle terminator, we try to let the automatic reasoning system solve the so-called very hard zebra puzzle: Blood Donation puzzle. The complete text description of the puzzle is as follows:

Blood Donation Puzzle

There is a hospital with a blood donation section with five units next to each other. One day after five women donated blood simultaneously, the secretary forgot to make a record of the event and the managers hired you to conduct research and hopefully find out each donor’s blood type correctly. After your investigation, you observed that each donor has a different shirt color, name, blood type, age, weight and job. Then you talked with the laboratory workers and they told you they have all the information about the donors but it’s completely mixed up. They also give you a report about what they remember from the instance of donation.

• Shirt Color: black, blue, green, purple, red
• Names: Andrea, Brooke, Kathleen, Meghan, Nichole.
• Blood Types: A+, AB+, B+, B-, O-.
• Ages: 25, 30, 35, 40, 45 years.
• Weights: 120, 130, 140, 150, 160 lbs.
• Jobs: Actress, Chef, Engineer, Florist, Policewoman

Chief security officers also provided a report for you according to what he remembers.

1. The A+ donor is next to the B+ donor.
2. Brooke is at one of the ends.
3. The woman wearing a Black shirt is somewhere to the left of the 150 lb woman.
4. The Actress is next to the Chef.
5. Kathleen is 40 years old.
6. The Florist is somewhere to the right of the woman wearing the purple shirt.
7. The oldest year-old donor weighs 130 lb.
8. Brooke is next to Nichole.
9. The 35-year-old woman is exactly to the left of the 30-year-old woman.
10. The 120 lb donor is somewhere between the the O- donor and the 150 lb donor, in that order.
11. Kathleen is at one of the ends.
12. The woman wearing the purple shirt is somewhere to the right of the woman wearing the green shirt.
13. The B+ donor weighs 140 lb.
14. The youngest woman is next to the 30-year-old woman.
15. The woman considered AB+ universal recipient is exactly to the left of the A+ donor.
16. Meghan is somewhere to the right of the woman wearing the purple shirt.
17. The woman wearing the green shirt is somewhere between the Actress and the woman wearing the red shirt, in that order.
18. At one of the ends is the 130 lb woman.
19. The O- universal donor is 35 years old.
20. The Florist is somewhere between the Actress and the Engineer, in that order.
21. The woman wearing the blue shirt is somewhere to the left of the woman wearing the red shirt.
22. The AB+ donor is next to the youngest woman.

According to all this information, the managers expect you to find out all details about the blood donors. In fact, the solution to the blood donation puzzle can be formulated into four more concise questions: Whose blood type is B-? And what color shirt is worn by the person weighing 160 lb? How many years old is Andrea, which unit is the Policewoman?

To make the system to solve the blood donation puzzle, we only need to create the following set of labeled statements as the input to the automatic reasoning system (Table 8):

Table 8: Tagged statement as input

The system solution results are as follows (Table 9), please note the Youngest and Oldest in the column A, which are mapping to the age 25 and 45. If you want 25 and 45 to appear in the matrix, you should let these numbers substitute for youngest/oldest in the input statements.

Table 9: Reasoning Result

Further tests indicate that the automatic reasoning system can solve various similar logic puzzles and the difference in input information is in the statement set. Further analysis and comparison showed that the Zebra puzzle, Einstein’s puzzle, and the Blood Donation puzzle all have unique solutions, but there can be multiple solution order variants. E.g., the Zebra puzzle has 144 variants while the Blood Donation puzzle has 972 variants.

Table 10: Multiple Reasoning Variants

Einstein’s puzzle is less difficult than the Zebra puzzle. The Blood Donation puzzle has more dimensions and requires more questions to be answered, and the average time required to solve all variants becomes longer due to the expansion of the search space. Another interesting finding is that although there are many questions to be answered in the Blood Donation puzzle, the reasoning steps to find the first solution will not lead to any dead ends, indicating that the puzzle was purposely designed in the most natural way that humans can solve. The table below lists the brief analysis data.

Table 11: Comparison of three puzzles

The evolution from data to intelligence must go through several stages: data -> information -> knowledge -> intelligence. The underlying data plays the most fundamental role. It comes from actual observations and is the most primitive entity, which has no meaning itself except to represent a kind of existence. For the reasoning system, the four types of variables in statistics, nominal variables, ordinal variables, interval variables and ratio variables, reflect the capacity of information. The various puzzles mentioned above usually only contain limited nominal and ordinal variables and do not contain interval and ratio variables, so they can be easily solved by the automatic reasoning system mentioned in this article. Currently, the model generation part can only deal with limited categorical variables, it has not been generalized to continuous variables but discrete variables so far. In contrast, the rules are implied in the constraint formulation of general constraint satisfaction problems, so there is no such restriction of variable type. It still requires further research and optimization to solve, e.g., the mixed model approach.

Due to space limitations, only the key concepts, implementation bird view and some system capabilities are presented in this post, please allow me to discuss technical details for this automatic reasoning system in the near future!

Summary

Starting from the Zebra puzzle, this post identifies the common paradigm of logic puzzles and designs a general logic reasoning system to solve them automatically. It is not only different from the brute force method without intelligence, but also different from the general solution to the constraint satisfaction problems. This practice has shown that by starting from a set of purely declarative statements, any zebra puzzle with limited constraints can be tagged and solved quickly in the same way without changing any code.

Learn more

• Solve the Missionaries and Cannibals Problem with SAS
• Solve “A Puzzle for Pirates” with SAS
• SAS financial functions review and mortgage payment analysis

Zebra Puzzle Terminator: A general automatic reasoning system solving method was published on SAS Users.