Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

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.