Export (0) Print
Expand All
2 out of 2 rated this helpful - Rate this topic

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.

    
    using Microsoft.SolverFoundation.Common;
    using 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.

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

    
    Decision person1 = new Decision(Domain.IntegerRange(1, 5), "person1");
    Decision person2 = new Decision(Domain.IntegerRange(1, 5), "person2");
    Decision person3 = new Decision(Domain.IntegerRange(1, 5), "person3");
    Decision person4 = new Decision(Domain.IntegerRange(1, 5), "person4");
    Decision person5 = 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.

    
    Decision red = new Decision(Domain.IntegerRange(1, 5), "Red");
    Decision green = new Decision(Domain.IntegerRange(1, 5), "Green");
    Decision white = new Decision(Domain.IntegerRange(1, 5), "White");
    Decision blue = new Decision(Domain.IntegerRange(1, 5), "Blue");
    Decision yellow = 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.

    
    Decision dog = new Decision(Domain.IntegerRange(1, 5), "Dog");
    Decision snails = new Decision(Domain.IntegerRange(1, 5), "Snails");
    Decision fox = new Decision(Domain.IntegerRange(1, 5), "Fox");
    Decision horse = new Decision(Domain.IntegerRange(1, 5), "Horse");
    Decision zebra = 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.

    
    Decision painter = new Decision(Domain.IntegerRange(1, 5), "Painter");
    Decision sculptor = new Decision(Domain.IntegerRange(1, 5), "Sculptor");
    Decision diplomat = new Decision(Domain.IntegerRange(1, 5), "Diplomat");
    Decision violinist = new Decision(Domain.IntegerRange(1, 5), "Violinist");
    Decision doctor = 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.

    
    Decision tea = new Decision(Domain.IntegerRange(1, 5), "Tea");
    Decision coffee = new Decision(Domain.IntegerRange(1, 5), "Coffee");
    Decision milk = new Decision(Domain.IntegerRange(1, 5), "Milk");
    Decision juice = new Decision(Domain.IntegerRange(1, 5), "Juice");
    Decision water = 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.

    
    Solution solution = context.Solve(new ConstraintProgrammingDirective());
    Report 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

Did you find this helpful?
(1500 characters remaining)
Thank you for your feedback
Show:
© 2014 Microsoft. All rights reserved.