Neil's News

Einstein's Riddle

15 January 2005

While looking for pictures of exploding pigeons, I stumbled across Einstein's Riddle. After a few minutes of work (most of which was spent flailing around in Python's terrible documentation), a Python program emerged which spat out one answer. I'd intended to optimise it, but since it only takes half a second to run, there didn't seem much point. Fun little problem.

Google shows that there are quite a few people who have solved this problem using one language or another. My favourite has to be FormulaOne. How one writes the FormulaOne compiler, I've no idea, but that's a pretty powerful language -- at least for this type of problem. I'm unconvinced that one could use it to write blogging software of equal elegance.

One odd thing that nobody else seems to have spotted is that the 15th rule is not required (The man who smokes Blends has a neighbour who drinks water). The inclusion of a redundant rule makes me suspect that this riddle did not in fact come from Einstein. It would be interesting to generalise the solving program and then write a program to generate riddles of this type, seeking the most elegantly simple one.

Update in 2021: I've reimplemented the solver using TypeScript. Mostly the same program, though using Heap's algorithm[?] and generators[?].

< Previous | Next >

Legal yada yada: My views do not necessarily represent those of my employer or my goldfish.