Using matrix operations to solve the Einstein's riddle. Part I.

There are several logical grid puzzles you can find on the internet, but undoubtedly, one of the most popular known is the Einstein's riddle. Although it's attributed to Einstein, there's no evidence to back up that claim. It's rumoured that only 2% of the world can solve it, but it's really not so hard, all one needs is logic and deduction. In this article we are going to present a method based entirely on matrix operations to solve this riddle and any other similar.

The riddle

There are five houses in five different colours in a row. In each house lives a person with a different nationality. The five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage. The question is: Who owns the fish?

Hints:

1. The British man lives in the red house.
2. The Swedish man has a dog for a pet.
3. The Danish man drinks tea.
4. The Norwegian lives in the first house.
5. The German smokes Prince.
6. The green house is to the left of the white house.
7. The owner of the green house drinks coffee.
8. The person that smokes Pall Mall has a bird.
9. The owner of the yellow house smokes Dunhill.
10. The person that lives in the middle house drinks milk.
11. The person that smokes Blend, lives next to the one that has a cat.
12. The person that has a horse lives next to the one that smokes Dunhill.
13. The one that smokes Bluemaster drinks beer.
14. The person that smokes Blend, has a neighbour that drinks water.
15. The Norwegian lives next to a blue house.

Matrix formulation

This problem can be formulated in terms of matrices, where the goal is to complete a matrix using the hints provided.

For this particular problem the start matrix is the following:

Where the position of the houses can be fixed.

Every hint can be expressed by means of a matrix, where the amount of columns is equal to the amount of columns of the start matrix. Use blanks for the unknown cells. For example, hints 1 and 2 can be expressed as:

1

2

Hint 6 involves two rows:

6

And hint 11 is more complex, because it involves two options. As the hint states the person that smokes Blend, lives next to the one that has a cat, it's not clear if the person who smokes Blend lives before or after the one who keeps cats, so we need to consider both options.

11

Matrix operations

As we are dealing with string matrices, there is no sense talking about numerical operations, but some kind of operations that allow working with any kind of value. The solution we propose needs to define three operations, where the operands are matrices with equal amount of columns, and the result is, in two cases a Boolean value (true or false), and in the third case it's a matrix with equal amount of columns as the operands.

1. Has a common value: This is a simple operator that checks if two matrices have a common value (not blank) in the same column position no matter the row.

2. Can be merged: This is a Boolean operator that returns true if two matrices can be merged using the common value found by means of the previous operator as the point of merger. This operator should return false if there are two overlapped non-blank cells with different values, or the merging process requires adding a new row when there is no sense the matrix can grow.

3. Merge: This operator just merges two matrices using a common cell as the point of merger, adding new rows if it's necessary.

In the next part, we'll be talking about the algorithm to solve the riddle using these three matrix operations, and a JavaScript implementation to solve this riddle and any other grid riddle similar to this one.