The Fish Puzzle
Don Peterson
Feb 2002

Abstract

The fish puzzle is solved by brute force. I use a python script to exhaustively examine all the possibilities. I don't claim the script is a proof of all the solutions, but I satisfied myself that its output is reasonable. The script took about 2 hours to run on my laptop computer (Jan 2006:  27 minutes on my year old computer). The methods used should be adaptable to allow you to solve similar logic puzzles that aren't too combinatorially complex.

The puzzle

There are 5 houses in five different colors. In each house lives a person with a different nationality. These 5 owners drink a certain drink, smoke a certain brand of tobacco and keep a certain pet. No owners have the same pet, smoke the same tobacco, or drink the same drink.

The question is: Who owns the fish?

Hints:

  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 owner drinks coffee.
  6. The person who smokes Pall Mall raises birds.
  7. The owner of the yellow house smokes Dunhill.
  8. The man living in the house right in the center 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 one who smokes Dunhill.
  12. The owner who smokes Bluemaster 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.
This puzzle is attributed to Einstein, but nobody references any published work or letter from Einstein. Since I'm skeptical that it was actually written by Einstein, I'm just going to call it the fish puzzle.

I started working on it in the same way that most people probably do, but then it occurred to me that it might be worthwhile to look at a brute force solution. A brute force solution looks at every possible answer to the problem, a task suited for a computer.

Combinatorial characteristics

There are 5 categories of 5 characteristics: color of house, nationality, drink, pet, and tobacco. There are 5^5 = 3125 possible combinations of these characteristics, but the hints reduce the set of possible combinations. For example, any possible combination that has the Brit but is not in the red house gets thrown away. Applying these "simple" hints in this way results in 51 combinations are the only ones logicaly allowed.

The task is to examine all possible solutions that can be made from these 51 possibilities. The number of combinations is 51 choose 5, or the binomial coefficient (51, 5), which is 2349060. We have to examine each of the permutations of each of these possibilities, or 5! = 120 permutations. Thus, we have to examine a total of 120 * 2349060 = 281887200 or 282 million combinations.

Assumptions and definitions

It it important to state assumptions when you work on puzzles. In this case, I made the following assumptions:
  1. The fish is one of the pets owned by the people in the houses.
  2. The houses are arranged linearly.
  3. Numbering of the houses goes from 1 being the leftmost house to house 5 being the rightmost house.
  4. A "neighbor" means a house that is immediately to the left or right. This is distinct from common usage, where we will sometimes refer to a neighbor who is two houses away from us.
You can think of other situations that would not fit these assumptions. For example, the houses could be situated in a circle, which would result in house 1 and 5 being neighbors. Or the houses could be situated in a different arrangement in a plane or in space. Another assumption that could be made is that the houses are numbered from right to left. This is not unusual; in fact, if you stand in the middle of a street where the houses are numbered with odd houses on one side and even on the other, you'll have the same behavior when you face each side of the road. These assumptions will change the answer to the original puzzle.

You could even say that nobody owned the fish, since it wasn't stated that the fifth pet was a fish. But the problem isn't very interesting if you make this assumption.

We'll define a solution as follows: a solution is an arrangement of the 25 characteristics that is consistent with the 15 hints. This means that two arrangements that have the German owning the fish but differ in one or more other details are regarded as distinct solutions. However, as answers to the question "Who owns the fish?" (the original problem), they are the same.

Problem solution

Here are the steps in the algorithm:
  1. Generate the subset of possible combinations (51 of them, as mentioned above).
  2. Generate each combination of 5 of these lines (51 choose 5).
  3. For each combination of 5, examine all permutations of the 5 possibilities for any solutions.
The fish.py python program contains the code that solves this problem. It should have enough comments in it to allow you to follow the process to a list of solutions. The comb_perm.py script contains functions that generate combinations and permutations. You will have to move the comb_perm.py script to a directory in your PYTHONPATH.

The script finds 7 solutions, resulting in the Norwegian, German, or Dane as being possible fish owners. Most folks will find the German as the owner when they work on the problem by filling out a matrix. As mentioned above, I have no proof that this code is correct. However, I had found 6 of these solutions manually before writing this code, so that helped convince me that the code was producing the correct output.

Thus, the original problem is not constrained enough to yield a unique solution.  Here are the solutions found:

German
    green        Norwegian    coffee       birds        PallMall
    blue         German       water        fish         Prince      <--
    red          Brit         milk         horses       Blends
    yellow       Dane         tea          cats         Dunhill
    white        Swede        beer         dogs         Bluemaster

    green        Norwegian    coffee       birds        PallMall
    blue         German       water        fish         Prince      <--
    white        Swede        milk         dogs         Blends
    yellow       Dane         tea          cats         Dunhill
    red          Brit         beer         horses       Bluemaster

    yellow       Norwegian    water        cats         Dunhill
    blue         Dane         tea          horses       Blends
    red          Brit         milk         birds        PallMall
    green        German       coffee       fish         Prince      <--
    white        Swede        beer         dogs         Bluemaster

Norwegian
    green        Norwegian    coffee       fish         Blends      <--
    blue         German       water        cats         Prince
    yellow       Swede        milk         dogs         Dunhill
    red          Brit         beer         horses       Bluemaster
    white        Dane         tea          birds        PallMall

Dane
    green        Norwegian    coffee       birds        PallMall
    blue         German       water        cats         Prince
    red          Brit         milk         horses       Blends
    yellow       Dane         tea          fish         Dunhill     <--
    white        Swede        beer         dogs         Bluemaster

    green        Norwegian    coffee       birds        PallMall
    blue         German       water        cats         Prince
    white        Swede        milk         dogs         Blends
    red          Brit         beer         horses       Bluemaster
    yellow       Dane         tea          fish         Dunhill     <--

    green        Norwegian    coffee       birds        PallMall
    blue         German       water        cats         Prince
    white        Swede        milk         dogs         Blends
    yellow       Dane         tea          fish         Dunhill     <--
    red          Brit         beer         horses       Bluemaster