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 p

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.