Who owns the crododile ?

· 6 min read

Who owns the crocodile

I discovered a few weeks ago an interesting library. The library python-constraint is created to solve Constraint Satisfaction Problems. With this library I can solve some zebra puzzles

Let’s try to solve the following easy puzzle: Who owns the Crododile?

Five girls are sitting in a row. Each girl has a favorite color, a chocolate bar, a pet, a hobby, and a place to go on holiday. Determine the name of the girl who owns the crocodile.

The question is simple. Search the girl with the crododile. The puzzle gives us a lot of hints.

  • Jo likes the Wispa Bites.
  • The person with the Hamster likes Swimming.
  • Hannah eats Dairy Milk.
  • Jessica is on the left of Georgina.
  • Lucy is the first on the left.
  • The first person on the right likes Swimming.
  • The person who eats Milky Bars owns a Horse.
  • The person in the middle eats Dairy Milk.
  • Jessica likes Green.
  • The person on the left of the middle wants to go to Tobago.
  • The person who wants to go to the Maldives likes Lilac.
  • The person who likes Wispa Bites sits next to the person who wants to go to Florida.
  • The person who likes Pink wants to go to Florida.
  • The person who sits first on the left likes Lilac.
  • The girl that likes Blue owns a Puppy.
  • The person who likes Skiing sits next to the person who has a Hamster.
  • The girl on the right of the girl who likes Tennis likes Horse riding.
  • The girl next to the girl who likes Milky Bars likes Boost.
  • The girl who likes Purple wants to go to Canada.
  • The girl who likes Crunchies owns a Rabbit.
  • The girl who likes Skiing sits next to the girl who plays Ten-pin bowlings.
  • Jessica wants to go to Australia.

Let’s solve the problem with python and the python-contraint library.

First import the library

from constraint import *

Create the different valid choices. The hints we get use these different options.

color = ["blue", "green", "lilac", "pink", "purple"]
name = ["Georgina", "Hannah", "Jessica", "Jo", "Lucy"]
chocolate = ["Boost", "Crunchies", "Diary Milk", 
             "Milky Bars", "Wispa Bites"]
pet = ["crocodile", "hamster", "horse", "puppy", "rabbit"]
hobby = ["horse riding", "skiing", "swimming", 
	 "ten-pin bowling", "tennis"]
holiday = ["Australia", "Canada", "Florida", 
           "Maldives" , "Tobago"]
place = [1,2,3,4,5]

Create a Problem object and add the variables to it. We get a lot of different permutations if we do not add any constraints to the problem.

p = Problem()
p.addVariables(color, place)
p.addVariables(name, place)
p.addVariables(chocolate, place)
p.addVariables(pet, place)
p.addVariables(hobby, place)
p.addVariables(holiday, place)

Be sure that each combination is only one time present on each place. This means that the color blue is at seat 1 and at seat 2 at the same time. There is only one unique combination valid.

p.addConstraint(AllDifferentConstraint(), color)
p.addConstraint(AllDifferentConstraint(), name)
p.addConstraint(AllDifferentConstraint(), chocolate)
p.addConstraint(AllDifferentConstraint(), pet)
p.addConstraint(AllDifferentConstraint(), hobby)
p.addConstraint(AllDifferentConstraint(), holiday)

In constraint programming, users state constraints on the solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found.

Let’s add our contraints now for our problem. We can create the constraints for our hints we got from the puzzle.

# Jo likes the Wispa Bites.
p.addConstraint(lambda a, b: a == b, ["Jo","Wispa Bites"])
# The person with the Hamster likes Swimming.
p.addConstraint(lambda a, b: a == b, ["hamster","swimming"])
# Hannah eats Dairy Milk.
p.addConstraint(lambda a, b: a == b, ["Hannah","Diary Milk"])
# Jessica is on the left of Georgina.
p.addConstraint(lambda a, b: a-b == 1, ["Jessica","Georgina"])
# Lucy is the first on the left.
p.addConstraint(InSetConstraint([1]), ["Lucy"])
# The first person on the right likes Swimming.
p.addConstraint(InSetConstraint([5]), ["swimming"])
# The person who eats Milky Bars owns a Horse.
p.addConstraint(lambda a, b: a == b, ["Milky Bars","horse"])
# The person in the middle eats Dairy Milk.
p.addConstraint(InSetConstraint([3]), ["Diary Milk"])
# Jessica likes Green.
p.addConstraint(lambda a, b: a == b, ["Jessica","green"])
# The person on the left of the middle wants to go to Tobago.
p.addConstraint(InSetConstraint([2]), ["Tobago"])
# The person who wants to go to the Maldives likes Lilac.
p.addConstraint(lambda a, b: a == b, ["Maldives","lilac"])
# The person who likes Wispa Bites sits next to 
# the person who wants to go to Florida.
p.addConstraint(lambda m,j: abs(m-j) == 1, ["Wispa Bites","Florida"])
# The person who likes Pink wants to go to Florida.
p.addConstraint(lambda a, b: a == b, ["pink","Florida"])
# The person who sits first on the left likes Lilac.
p.addConstraint(InSetConstraint([1]), ["lilac"])
# The girl that likes Blue owns a Puppy.
p.addConstraint(lambda a, b: a == b, ["blue","puppy"])
# The person who likes Skiing sits next to the person 
# who has a Hamster.
p.addConstraint(lambda a, b: abs(a-b) == 1, ["skiing","hamster"])
# The girl on the right of the girl who likes Tennis likes 
# Horse riding.
p.addConstraint(lambda a, b: a-b == 1, ["tennis","horse riding"])
# The girl next to the girl who likes Milky Bars likes Boost.
p.addConstraint(lambda a, b: abs(a-b) == 1, ["Milky Bars","Boost"])
# The girl who likes Purple wants to go to Canada.
p.addConstraint(lambda a, b: a == b, ["purple","Canada"])
# The girl who likes Crunchies owns a Rabbit.
p.addConstraint(lambda a, b: a == b, ["Crunchies","rabbit"])
# The girl who likes Skiing sits next to the girl who plays 
# Ten-pin bowlings.
p.addConstraint(lambda a, b: abs(a-b)==1, 
                ["skiing","ten-pin bowling"])
# Jessica wants to go to Australia.
p.addConstraint(lambda a, b: a == b, ["Jessica","Australia"])

Now that all constraints are added, the program can begin to search the solutions.

allSolutions = p.getSolutions()
print(len(allSolutions))

for s in allSolutions:
  a = {k: v for k, v in sorted(s.items(), key=lambda item: item[1])}
  print(a)

The output of the program shows us that there is only one solution:

{
   'Crunchies': 1, 
   'lilac': 1, 
   'Maldives': 1, 
   'rabbit': 1, 
   'horse riding': 1, 
   'Lucy': 1, 
   'Wispa Bites': 2, 
   'Jo': 2, 
   'blue': 2, 
   'puppy': 2, 
   'tennis': 2, 
   'Tobago': 2, 
   'Florida': 3, 
   'Diary Milk': 3, 
   'Hannah': 3, 
   'pink': 3, 
   'ten-pin bowling': 3, 
   'crocodile': 3, 
   'Milky Bars': 4, 
   'skiing': 4, 
   'Georgina': 4, 
   'horse': 4, 
   'Canada': 4, 
   'purple': 4, 
   'Jessica': 5, 
   'hamster': 5, 
   'Australia': 5, 
   'Boost': 5, 
   'green': 5, 
   'swimming': 5
}

On the third position the crocodile is present. Hannah is also on place 3, so the solution of our problem is Hannah.

With this library we can solve logical problems. At this moment I do not see yet a usecase to use this library in my test automation projects. Maybe in future. You never know.

References