How to: Apply a CSP to Logical Implication

Solver Foundation 3.0

You can use constraint programming to solve a logical puzzle about five people, houses, pets, jobs, and drinks. Given the following 15 facts, you must determine who drinks water and who owns the zebra.

  1. There are five houses.

  2. The first person lives in the red house.

  3. The second person owns the dog.

  4. Coffee is drunk in the green house.

  5. The fourth person drinks tea.

  6. The green house is immediately to the right of the white house.

  7. The sculptor owns snails.

  8. The diplomat lives in the yellow house.

  9. Milk is drunk in the middle house.

  10. The fifth person lives in the first house.

  11. The doctor lives in the house next to the man with the fox.

  12. The diplomat lives in the house next to the house where the horse is kept.

  13. The painter drinks orange juice.

  14. The third person is a violinist.

  15. The fifth person lives next to the blue house.

The following example uses Solver Foundation to show how to create and solve the zebra logic puzzle by demonstrating how to use the Solver Foundation Services layer.

To apply a constraint programming directive to the zebra puzzle

  1. Create a Console Application named CSPZebra.

  2. Add a reference to Microsoft Solver Foundation on the .NET tab.

  3. Add the following Imports or using statements to the top of the Program code file.

    
    Imports Microsoft.SolverFoundation.Common
    Imports Microsoft.SolverFoundation.Services
    
    
    
  4. In the Main method, add the following code to get the context environment for a solver and create a new model.

    
    Dim context As SolverContext = SolverContext.GetContext()
    Dim model As Model = context.CreateModel()
    
    
    
  5. Create a five decision variables to represent the five nationalities, and add the decisions to the model.

    
    Dim person1 As New Decision(Domain.IntegerRange(1, 5), "person1")
    Dim person2 As New Decision(Domain.IntegerRange(1, 5), "person2")
    Dim person3 As New Decision(Domain.IntegerRange(1, 5), "person3")
    Dim person4 As New Decision(Domain.IntegerRange(1, 5), "person4")
    Dim person5 As New Decision(Domain.IntegerRange(1, 5), "person5")
    model.AddDecisions(person1, person2, person3, person4, person5)
    
    
    
  6. Create a five decision variables to represent the five house colors, and add the decisions to the model.

    
    Dim red As New Decision(Domain.IntegerRange(1, 5), "Red")
    Dim green As New Decision(Domain.IntegerRange(1, 5), "Green")
    Dim white As New Decision(Domain.IntegerRange(1, 5), "White")
    Dim blue As New Decision(Domain.IntegerRange(1, 5), "Blue")
    Dim yellow As New Decision(Domain.IntegerRange(1, 5), "Yellow")
    model.AddDecisions(red, green, white, blue, yellow)
    
    
    
  7. Create a five decision variables to represent the five different pets, and add the decisions to the model.

    
    Dim dog As New Decision(Domain.IntegerRange(1, 5), "Dog")
    Dim snails As New Decision(Domain.IntegerRange(1, 5), "Snails")
    Dim fox As New Decision(Domain.IntegerRange(1, 5), "Fox")
    Dim horse As New Decision(Domain.IntegerRange(1, 5), "Horse")
    Dim zebra As New Decision(Domain.IntegerRange(1, 5), "Zebra")
    model.AddDecisions(dog, snails, fox, horse, zebra)
    
    
    
  8. Create a five decision variables to represent the five jobs, and add the decisions to the model.

    
    Dim painter As New Decision(Domain.IntegerRange(1, 5), "Painter")
    Dim sculptor As New Decision(Domain.IntegerRange(1, 5), "Sculptor")
    Dim diplomat As New Decision(Domain.IntegerRange(1, 5), "Diplomat")
    Dim violinist As New Decision(Domain.IntegerRange(1, 5), "Violinist")
    Dim doctor As New Decision(Domain.IntegerRange(1, 5), "Doctor")
    model.AddDecisions(painter, sculptor, diplomat, violinist, doctor)
    
    
    
  9. Create a five decision variables to represent the five drinks, and add the decisions to the model.

    
    Dim tea As New Decision(Domain.IntegerRange(1, 5), "Tea")
    Dim coffee As New Decision(Domain.IntegerRange(1, 5), "Coffee")
    Dim milk As New Decision(Domain.IntegerRange(1, 5), "Milk")
    Dim juice As New Decision(Domain.IntegerRange(1, 5), "Juice")
    Dim water As New Decision(Domain.IntegerRange(1, 5), "Water")
    model.AddDecisions(tea, coffee, milk, juice, water)
    
    
    
  10. Add constraints that require each person to have a different nationality, house color, pet, job, and drink. Then, add constraints that show which traits are linked.

    
    model.AddConstraints("constraints",
        model.AllDifferent(person1, person2, person3, person4, person5),
        model.AllDifferent(red, green, white, blue, yellow),
        model.AllDifferent(dog, snails, fox, horse, zebra),
        model.AllDifferent(painter, sculptor, diplomat, violinist, doctor),
        model.AllDifferent(tea, coffee, milk, juice, water),
        person1 = red,
        person2 = dog,
        person3 = painter,
        person4 = tea,
        person5 = 1,
        green = coffee,
        white - green = 1,
        sculptor = snails,
        diplomat = yellow,
        milk = 3,
        violinist = juice,
        model.Abs(person5 - blue) = 1,
        model.Abs(fox - doctor) = 1,
        model.Abs(horse - diplomat) = 1
        )
    
    
    
  11. Add a constraint programming directive, and solve the model. Then, write the solutions to the console window.

    
    Dim solution As Solution = context.Solve(New ConstraintProgrammingDirective())
    Dim report As Report = solution.GetReport()
    Console.Write("{0}", report)
    
    
    
  12. Press F5 to build and run the code. The results show that the violinist owns the zebra and the diplomat drinks water.

    The command window shows the following results.

    ===Solver Foundation Service Report===

    Date: Date

    Version: Version

    Model Name: Default

    Capabilities Applied: CP

    Solve Time (ms): 83

    Total Time (ms): 166

    Solve Completion Status: Feasible

    Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem

    Directives:CSP(TimeLimit = -1, MaximumGoalCount = -1, Arithmetic = Default, Algorithm = Default, VariableSelection = Default, ValueSelection = Default, MoveSelection = Default, RestartEnabled = False, PrecisionDecimals = 2)

    Algorithm: Any

    Variable Selection: Any

    Value Selection: Any

    Move Selection: Any

    Backtrack Count: 1

    ===Solution Details===

    Goals:

    Decisions:

    person1: 3

    person2: 5

    person3: 4

    person4: 2

    person5: 1

    Red: 3

    Green: 4

    White: 5

    Blue: 2

    Yellow: 1

    Dog: 5

    Snails: 3

    Fox: 1

    Horse: 2

    Zebra: 4

    Painter: 4

    Sculptor: 3

    Diplomat: 1

    Violinist: 5

    Doctor: 2

    Tea: 2

    Coffee: 4

    Milk: 3

    Juice: 5

    Water: 1

Show: