fixedpoint.jp

Solving Einstein's five-houses riddle by LibreOffice Calc (2017-05-06)

Einstein's five-houses riddle is a famous logic puzzle. Last year we have proved the existence of its unique solution by Coq. Recently Dasović et al. demonstrates that a spreadsheet application can solve it as a linear programming problem. Although they use Microsoft Excel's Solver add-in, it is even easier to perform the task by LibreOffice Calc, thanks to its built-in Solver menu.

Here is a spreadsheet in OpenDocument Format reproducing the mathematical model described in the paper: five-houses.ods

How to play it (tested with LibreOffice 5.3.2):

1. Go to menu "Tools" > "Solver ..."
2. Pick an arbitrary empty cell for "Target cell"; leave "Optimize to" Maximum or whatever
3. Choose all of yellow cells in field "By changing cells" by entering $B$2:$F$6;$B$9:$F$13;$B$16:$F$20;$B$23:$F$27;$B$30:$F$34;$J$12;$J$14;$J$19
4. In field "Limiting Conditions", make every yellow cell "Binary", and specify an equation for each cell with a comment (see cheatsheet)
5. It is advisable to choose "LibreOffice CoinMP Linear Solver" as Solver Engine from "Options..." in the dialog. Also checking "Assume variables as integer" and "Assume variables as non-negative" would be a plus but optional.
6. Push "Solve" button

Then it will finish in only a second or so.

We have observed a couple of interesting points during this attempt; the one is that constraint (4), namely

The green house is on the left of the white house.

should be interpreted in a strict sense. That is, it must require that the green house is just next to the white house. Otherwise, the riddle could have several solutions. In fact the last two sheets of the above spreadsheet show alternative solutions under a weaker version of constraint (4). Moreover, constraint (19) is unnecessary at least for Calc's solver.