Zebra Puzzle

Zebra in the grasslands of the Serengeti in Tanzania, East Africa. (Shutterstock)

Diabolical daughter brought this puzzle to our regular exercise-the-old-man's-brain session the other day. Otherwise known as Einstein's Riddle, we have five houses and a list statements concerning each of these houses, things like their nationality of the person who lives there, the kind of pet they keep, what brand of cigarette they smoke, etc.

We worked on it for a bit and eventually came to realize that we were not going to be able to solve this with pure logic. We would need to arbitrarily assign some people to houses and see what shakes out. We only had to go down two or three blind alleys before we came up with a solution.

I'm looking at this and I'm thinking I could easily write a computer program to solve it, so I did. But it doesn't work. I've gone over the logic with a fine tooth comb and I can find nothing wrong. Obviously I am missing something, so I thought I would try and explain the logic in English and maybe something will jump out at me.

The statements typically state that same guy who smokes brand X of cigarettes also favors drink Y. If all the statements were like that, it would be simple to sort it out, but some of the statements tells us that the guy who keeps animal Z lives next door to the house painted with color C.

So for each rule, I scan the table that contains our proposed solution, looking for the first item. If I find it, I check the slot for the second item in this house and the adjacent houses, depending on what the statement says.

That all seems great. For each rule I place two items and if I get through all the rules, I should have all items placed in the table, but when I get to the end, there are still several empty slots. How can that be?

That was yesterday. Last night I found the problem - array index out of bounds. Kind of amazing that it didn't cause a crash. I guess it wasn't that far out of bounds.

When I was writing this program I thought I would be cute and define the array that holds the answer to have six columns, one more than the number of houses. From reading the problem, we see that the houses are apparently numbered one through five. I could use an array with five columns, but then every time I wanted to use a house number to index into this array I would need to remember to reduce it by one. So we have six columns and we use the house number to index into this array. Since I have an extra column (column zero) I used it for labels.

Pretty silly since I only used the house number in a couple of spots. But now since I am starting my index from one instead of from zero I think I should increase the limit by one, which was a big fat error being as I using the dimension of the array as the limit. Adding one to the defined limit means you are going to step over the line when you get to the end. The problem was obvious when I was finally able to see it.

I used Wikipedia's example as my basis.

The program is not as clean as it could be, I copied and pasted a few lines of code in several spots. It didn't seem worthwhile to rearrange the world just to eliminate these few duplicate lines. 

Some people have tried writing programs that will read the English text of the problem, interpret it, and then find a solution. That might be an interesting project, but a project it would be. I already have too many projects. I just did this for fun.

I've uploaded the source to github.