The Zebra PuzzleCarlo TomasiComputer ScienceDuke University1 IntroductionIn the class textbook, the Zebra puzzle is offered as an exercise for Section 1.1 on logic (Exercise 61, page 20). Hereis the puzzle:Five men with different nationalities and with different jobs live in consecutive houses on a street. Thehouses are painted different colors. The men have different pets and have different favorite drinks. De-termine who owns a zebra and whose favorite drink is mineral water (which is one of the favorite drinks)given these clues1:1. The Englishman lives in the red house.2. The Spaniard owns a dog.3. The Japanese man is a painter.4. The Italian drinks tea.5. The Norwegian lives in the first house on the left.6. The green house is on the right of the white one.7. The photographer breeds snails.8. The diplomat lives in the yellow house.9. Milk is drunk in the middle house.10. The owner of the green house drinks coffee.11. The Norwegian’s house is next to the blue one.12. The violinist drinks orange juice.13. The fox is in a house next to that of the physician.14. The horse is in a house next to that of the diplomat.The textbook also gives the following hint:Make a table where the rows represent the men and columns represent the colors of their houses, theirjobs, their pets, and their favorite drinks and use logical reasoning to determine the correct entries in thetable.This is a fun puzzle to think about. However, it has to do with “logic” only marginally. The real difficulty is inknowing where to start, and in how to think about the problem.When addressing real-life problems as computer scientists, we will be in this situation often: someone posesa problem (usually less well defined than this one), and we are asked to solve it. This is different from solving ahomework assignment in a class. For the homework, we are either told what technique to apply, or we can make an1I have numbered the clues for later reference.1educated guess by picking a solution method from the part of the textbook that the problem refers to. In real life,all we have is the problem itself, and whatever knowledge and experience we have accumulated over time. So howdo we come up with a solution? We will use the zebra puzzle to explore some heuristics for thinking about complexproblems.2 How Hard Is the Problem?Why is it useful to know how hard the problem is? Mostly because we want to know how many resources to throw atit: Do I just scribble a couple of lines on the back of an envelope? Do I need to write a computer program? If I do,will the program run in a reasonable amount of time?For puzzles, understanding its complexity is usually a simple exercise of combinatorics, a set of counting tech-niques that we will explore in this course. The web page http://mathforum.org/library/drmath/view/55627.html sug-gests a solution to the zebra puzzle, and starts with the following observation:Of course one could just enumerate the 55= 3125 different possible answers, and scratch off all of thosewhich didn’t fit the clues, but this is the hard way.First, this may not be as hard if done with a computer program: 3000 or so alternatives can be explored in mi-croseconds. If the program is not too complex to write, we may be done more quickly this way. An advantage of asystematic approach like this is that we can also answer ancillary questions: is the solution unique? If not, how manyother solutions are there?Another advantage of a software solution is that if the code is simple we are more confident that our solution iscorrect. Going through the many steps in the “logical” solution given in the web page mentioned above is error prone,and writing a short program may be safer.Thirdly, the solution on the web page goes through a chain of arguments of which here is a snippet (that version ofthe problem uses flowers instead of jobs, and Ukrainians instead of Italians):By No.7, the geranium grower owns snails. Thus the geranium grower does not own the dog, fox, horse,or zebra, and the snail owner does not grow roses, marigolds, lilies, or gardenias. Thus the geraniumowner is not the Spaniard.We can all follow arguments of this type, given the clues. The difficulty is not in verifying whether a logical implicationis valid or not. The real trouble is in coming up with a sequence of arguments that leads us to a conclusion quickly. Soin a sense the given solution is not a solution unless we are also told how the solver came up with the proper sequenceof arguments.In this regard, if we can write a program that solves this puzzle, perhaps we learn how to write programs to solveother puzzles, and maybe even programs that in some sense can be said to “think.”However, the problem is harder than exploring 3000 or so alternatives. The different possible answers are not3125, but many more. To see this, let us do what is a useful first step in all cases: let us visualize the problem.Drawings always help. We could draw five little Victorian houses with windows and chimneys, paint them in fivedifferent colors, and draw a gondolier for an Italian, and so forth. Needless to say, we want something quicker. Thetextbook hint to use tables is good: tables organize information in a concise way, and let us view the whole situationat a glance. This is a broad view of things that is very useful to us, just as it is mostly useless to computers, which in asense can only look at one data item at a time.The specifics of the hint, on the other hand, are misleading. Why should we put the men on the rows, and putjobs, colors, pets, and drinks on the columns? What makes men (or their nationalities) any different, in the abstractproblem, from jobs or colors? This is always a key question when you make a table: what to put on rows and columns,and should the table have two dimensions (rows, columns), or more?Think about this for a minute. I mean it: put this document down, and actually do think for a while about whetherthe nationality of a house occupant is to be treated any differently from the job he holds, or the pet he has, for thepurpose of solving the zebra puzzle.There is really no reason for this distinction. All we have are five houses, and five “attributes” for each house:its color, the nationality, job, and favorite drink of its occupant, and the pet that lives in it. Assigning a job and an2occupant to a house also automatically assigns that job to that occupant. More importantly, if we were to use the tablesuggested in the hint,
View Full Document
Unlocking...