Modelling a Christmas Riddle as a Constraint Satisfaction Problem

I found the riddle in a small book called “The Escape Room Advent Calendar”¹. It is basically a stripped version of “Einsteins Rätsel” (which I solved here). While solving it, I came to the conclusion that there are actually multiple possible solutions.

To validate my finding, I modelled the riddle as a constraint satisfaction problem and solved it using SAVILE ROW.

The Riddle

The riddle contains some clues and the target is to find the house of the aunts. Each of the five houses has a color and a window shape and the clues present some constraints between colors, window shapes and the ordering of the houses.

Modelling the Problem

First, we need to encode the problem in such a way that the CPS solver can understand it. To do so, we create a 2x5 matrix: two features (window shape + color) for five houses.

Next, we need to create a mapping of the features attributes to integers:

⠀	1	2	3	4	5
COL	yellow	blue	violet	green	red
WIN	round	square	triangle	oval	star

Then we need to make sure, that each feature only appears once across all houses. Note here, that the target matrix M always has the number of the house in the first position and the feature in the second.

allDiff([M[1,COL],M[2,COL],M[3,COL],M[4,COL],M[5,COL]]),

Afterwards, we can start to add the clues as constraints. Most of the constraints are repetitive, so I just put some examples here.

2. Second house is blue

M[2,COL] = 2,

3. Next to the green house, there is one with oval windows

exists x : int(1..5) . M[x,COL] = 4 /\ (M[x+1,WIN] = 4 / M[x-1,WIN] = 4),

The whole file with all constraints can be found here. The hints regarding the aunts house aren’t necessary for the solving, but only to constraint the result.

Solving the Problem

The last step is to actually run the solver. As we want to verify whether there are multiple possible solutions, we add the “-all-solutions”-flag.

savilerow ../christmas_riddle.eprime -minion -run-solver -all-solutions

In the resulting solution-files, we can then verify that two solutions are possible:

First Solution

M = [[5, 1], [2, 2], [4, 3], [1, 4], [3, 5]]

Translating the integer values back to the attributes, we get

House	COL	WIN
1	red	round
2	blue	square
3	violet	triangle
4	yellow	oval
5	green	star

Second Solution

M = [[5, 1], [2, 2], [3, 3], [1, 4], [4, 5]]

Translated, that yields

House	COL	WIN
1	red	round
2	blue	square
3	green	triangle
4	yellow	oval
5	violet	star

Conclusion

Both solutions are valid. When checking the constraints for the aunts house (must be in between two other houses and next to a green one), there are multiple possibilities. In the first solution, the aunts would live in the fourth/yellow house. With the second solution, the aunts could live in the second/blue or the yellow/fourth house.

The book lists the second/blue solution as the correct one; That statement is not wrong, but the answer is not unambiguous - which I would have expected.