If any of you actually need such constraint satisfaction in javascript, checkout my fd.js library [1]. You'll find einstein, sudoku and other puzzles in the tests.js file.
I also recommend a Mozart/Oz style interactive search tree explorer made by a student [2] .. built on fd.js.
In this riddle, the search space is a list of five permutations, the first being a permutation of the five nationalities (Brit, Swede, etc.), the next being a permutation of the five house colors and so on. A brute-force search would need to search (5!)^5 possibilities because there are 5! (equal to 120) permutations of 5 elements.
Some types of constraints force brute-force searches, for example if the MD5 sum of the list needs to match a particular value then there is little that we can do without trying every possible list of permutations. Some constraints allow faster, but still intractable, searches that grow exponentially with the size of the problem (knapsack problems fall into this category). In this riddle, we have 15 simple constraints; some can even be applied to individual permutations (e.g. "The Norwegian lives in the first house."). A straightforward solution thus presents itself to us. Here is the entire solution in Python:
from itertools import permutations as perms
for brit, swede, dane, norwegian, german in perms(range(5)):
if norwegian != 0: continue
for red, green, white, yellow, blue in perms(range(5)):
if brit != red: continue
if green != white - 1: continue
if norwegian not in [blue-1, blue+1]: continue
for tea, coffee, milk, beer, water in perms(range(5)):
if milk != 2: continue
if dane != tea: continue
if green != coffee: continue
for pallmall, dunhill, marlboro, winfield, rothmans in perms(range(5)):
if dunhill != yellow: continue
if winfield != beer: continue
if rothmans != german: continue
if marlboro not in [water-1, water+1]: continue
for dogs, birds, cats, horses, fish in perms(range(5)):
if swede != dogs: continue
if pallmall != birds: continue
if marlboro not in [cats-1, cats+1]: continue
if dunhill not in [horses-1, horses+1]: continue
nation = {brit: "Brit", swede: "Swede", dane: "Dane",
norwegian: "Norwegian", german: "German"}
print "The {} owns the fish".format(nation[fish])
On my old laptop this solution runs in 0.023 seconds of real time using Python 2.7. I haven't tried it using Pypy. Notice that in order to cut off branches of the search space as soon as possible, I introduce the tests for the constraints as soon as possible while generating the permutations. This is standard Python and only needs one function (permutations) from the standard library.
Normally, inner loops are executed more times than outer loops, but in this program the inner loops are skipped (because of the continue statements) when constraints fail in the the outer loops. The five loops are executed a total of 69, 1265, 520, 890 and 109 times respectively (I put counter in each loop, all counters were initialized before any of the loops begin).
Python is great for simple problems like this. I wrote this program while waiting for my daughter to come downstairs to be driven to school this morning.
Presented with a page like this, obviously I sat down to solve the puzzle. :) For others who do the same, CRUCIAL CLARIFICATION: The constraint that "The green house is on the left of the white house" must be read as saying that the green house is immediately to the left of the white house, not merely that it is somewhere to the left (otherwise you don't have quite enough information to continue).
It's a really well-constructed puzzle, though: the identity of the fish owner is the very last part of the grid that you get to fill in.
In case anyone else misunderstood the title, this article doesn't demonstrate the unique ability of Lisp to solve this problem. The method they use is constraint solving using backtracking. This could be implemented in any language.
It is a good illustration of code-as-data in Lisp. It's just that in this case, code-as-data doesn't seem to be a particular advantage in solving the problem (it's not a disadvantage either, just a stylistic difference).
So this article could have been 'A C solution to "Einsteins Riddle"' if C had been chosen as the language. Not a criticism, just a clarification, since HN is full of people looking for the true potential of new/different languages.
These kind of problems are more elegantly solved in logic (aka relational) programming languages like Prolog and similar logic programming implementations like miniKanren & Clojure's core.logic. Here's the same problem solved using Clojure's core.logic library https://github.com/swannodette/logic-tutorial/blob/master/sr...
One issue that I found when solving problems like this is that, to achieve speed, it can become necessary to use many nested lets. That could hurt readability. Nobody wants to see a line of code nested 20 tabs deep!
and then express amb-like computations in effectively the same way:
sample :: [(Int, Int)]
sample = do
x <- [1,2,3,4,5]
y <- [1,2,3,4,5]
require (x == 2 * y)
return (x, y)
after which the value of sample is [(2,1),(4,2)]. (Also, my require is effectively the same as the guard function found in Control.Monad, specialized for lists.)
