WHO OWNS THE ZEBRA?
This is a puzzle which has been circulating the net. There are a couple differnt versions out there which try to be a little more politically correct but are essentially the same problem.
I figured the fastest way to solve the puzzle was by an exhaustive search. There are only 24 Billion combinations and a 100Mhz pentium can check about 1 Million per second. On a Linux box with a Cyrix P150+ processor, it will take roughly 4 hours to run. The program took about an hour to write and produced this solution within seconds. The program produced the only solution early because I wrote it to guess house colors in the order I had already deduced which reduced the total runtime necessary to less than two minutes, except to double check my initial deduction. This web page was written while the program was still running.
Below is a table which shows some of the deductions made along with the clues from which they were derived. Basically, you start with a blank table and keep going through the list of clues interpretting them in the current knowledge base expressed by the table. When you ge a statement such as the norwegian lives in house 0 you record that fact, along with the fact that the peopel in houses 1,2,3, and 4 are not norwegian and theat the person in house 0 is not english, spanish, japanese, or ukrainian. Remember to do the same for any of your own deductions. It still takes a lot of work. I also used one guess where I divided the problem into three cases. The first case produced a solution. From my computer solution, I know that it was the only solution; otherwise, one would have to check to see if the other two cases yield a solution or a contradiction. Not all of the clues can be represented well in the table below; this is why multiple cases or a different representation of the problem space became necessary later.
Each cell in the table is blank or has a "yes" or "no", annotated with the reason (often the rule number and a fact) or, if a no is entered as a result of a "yes" in another cell, a direction ("up", "down", "left", or "right") to the cell with a yes.
Table entries in blue reflect conclusions drawn after tentatively placing the japanese in house 4, as referred to in the following note:
Note: Although there are 3 unknown nationalities and 3 columns to place them in, there are only three combinations rather than six because of further constraints on two of the nationalities. The japanese are the only ones with three possible locations so we can refer to the three possibilities by their possition and the other two's positions will be determined. Now we can explore three different tentative solutions by making three photocopies of our table as it is at this stage. We will probably either end up with multiple solutions or contradictions will prevent completion of some of the alternatives. The Japanese were placed in column 4 out of speculation. Since we put the japanese in 4 we must put the spaniard in 3 by elimination and therefore the ukranian must be in 1 by further elimination.
| Value | House 0 | House 1 | House 2 | House 3 | House 4 |
|---|---|---|---|---|---|
| yellow | Yes (elimination) | No (down) | no(left) | no(left) | no(left) |
| blue | No (right) | Yes (11,10) | No (left) | No (left) | No (left) |
| red | no(right) | no(up) | Yes(2,english) | no(left) | no(down) |
| ivory | No (right) | No (up) | No (6,11,10) | Yes (6,elim) | No (down) |
| green | No(6) | No(up) | No(4,milk) | no(right) | Yes(6,elim) |
| kools | Yes (8,yellow) | no (8,color) | no (left) | no (left) | no (left) |
| chesterfields | No (up) | Yes (elim) | No (down) | No (down) | No (down) |
| luckies | no (up) | no (right) | no (up) | Yes (13,OJ) | no (13, coffee) |
| old_golds | no (up) | no (7,horse) | Yes (elim) | No (up) | No (down) |
| parliaments | no | No (right) | No (right) | No (right) | Yes (Japanese) |
| english | no (down) | no (2,blue) | Yes (elim) | no (2, ivory) | no (2,green) |
| spanish | no (down) | no (3,horse) | no (up) | Yes (note) | No (down) |
| norwegian | Yes (10) | no (left) | no (left) | no (left) | no (left) |
| japanese | no (up) | No (right) | no (english) | No (right) | Yes (note) |
| ukrainian | no (up) | Yes(note) | no (5, milk) | No (right) | no (5, coffee) |
| water | Yes (elim) | no(left) | no(down) | no (left) | no (down) |
| milk | no (right) | no (right) | Yes (9) | no (left) | no (left) |
| oj | no (13,kools) | No (down) | no (up) | Yes (elim) | no (down) |
| tea | no (5,10) | Yes (5, Ukranian) | no (up) | no (left) | no (down) |
| coffee | no (4) | no (4) | no (up) | no (right) | Yes(4) |
| horse | no (right) | Yes(12) | No (left) | No (left) | No (left) |
| dog | no (3, not spanish) | no (up) | no (3, not spanish) | Yes(3,spanish) | No(left) |
| fox | Yes (#11,elimination) | no (up) | No (down) | No (up) | No (left) |
| snails | no (7, kools) | no (up) | Yes (7,old gold) | No (up) | No (left) |
| zebra | No (up) | no (up) | No (up) | No (up) | Yes (final elimination) |
Here is a copy of the chart partially completed (for trying different alternatives).
| Value | House 0 | House 1 | House 2 | House 3 | House 4 |
|---|---|---|---|---|---|
| yellow | Yes (elimination) | No (down) | no(left) | no(left) | no(left) |
| blue | No (right) | Yes (11,10) | No (left) | No (left) | No (left) |
| red | no(right) | no(up) | Yes(2,english) | no(left) | no(down) |
| ivory | No (right) | No (up) | No (6,11,10) | Yes (6,elim) | No (down) |
| green | No(6) | No(up) | No(4,milk) | no(right) | Yes(6,elim) |
| kools | Yes (8,yellow) | no (8,color) | no (left) | no (left) | no (left) |
| chesterfields | No (up) | ||||
| luckies | no (up) | no (up) | no (13, coffee) | ||
| old_golds | no (up) | no (7,horse) | |||
| parliaments | no | ||||
| english | no (down) | no (2,blue) | Yes (elim) | no (2, ivory) | no (2,green) |
| spanish | no (down) | no (3,horse) | no (up) | ||
| norwegian | Yes (10) | no (left) | no (left) | no (left) | no (left) |
| japanese | no (up) | no (english) | |||
| ukrainian | no (up) | no (5, milk) | no (5, coffee) | ||
| water | Yes (elim) | no(left) | no(down) | no (left) | no (down) |
| milk | no (right) | no (right) | Yes (9) | no (left) | no (left) |
| oj | no (13,kools) | no (up) | no (down) | ||
| tea | no (5,10) | no (up) | no (down) | ||
| coffee | no (4) | no (4) | no (up) | no (right) | Yes(4) |
| horse | no (right) | Yes(12) | No (left) | No (left) | No (left) |
| dog | no (3, not spanish) | no (up) | no (3, not spanish) | ||
| fox | no (up) | ||||
| snails | no (7, kools) | no (up) | |||
| zebra | no (up) |
Here is a blank copy of the chart
| Value | House 0 | House 1 | House 2 | House 3 | House 4 |
|---|---|---|---|---|---|
| yellow | |||||
| blue | |||||
| red | |||||
| ivory | |||||
| green | |||||
| kools | |||||
| chesterfields | |||||
| luckies | |||||
| old_golds | |||||
| parliaments | |||||
| english | |||||
| spanish | |||||
| norwegian | |||||
| japanese | |||||
| ukrainian | |||||
| water | |||||
| milk | |||||
| oj | |||||
| tea | |||||
| coffee | |||||
| horse | |||||
| dog | |||||
| fox | |||||
| snails | |||||
| zebra |
Dr. Math offers another method of solution to a different version of the same problem.
This file is maintained by Mark Whitis (whitis@freelabs.com).
|
Software Development - Electronic Design - Embedded Systems - Device Drivers - System/Network Administration and Security - Motor Control, RobotCNC - Linux/Un*x - 25+ years experience The author of these pages is looking for a new gig. [RESUME] |
| Engineers and electronic hobbyists: The new Open Symbol Project is creating open schematic symbols and PCB footprints for a variety of different CAD packages. |
| Mark Whitis's Website | Home Page | Linux | Book: Linux Programming Unleashed | My Resume | Genealogical Data | Contact Info | Security | About |
All email messages received must pass the turing test or they will be considered SPAM. If it could have been written by a machine, it was.
Under no circumstances are you to email me with questions regarding windoze, any other microsoft operating system or application, or any software which runs under any form of windoze.
*