How to: Apply a CSP to Logical Implication

Article
12/06/2011

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.

There are five houses.
The first person lives in the red house.
The second person owns the dog.
Coffee is drunk in the green house.
The fourth person drinks tea.
The green house is immediately to the right of the white house.
The sculptor owns snails.
The diplomat lives in the yellow house.
Milk is drunk in the middle house.
The fifth person lives in the first house.
The doctor lives in the house next to the man with the fox.
The diplomat lives in the house next to the house where the horse is kept.
The painter drinks orange juice.
The third person is a violinist.
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

Create a Console Application named CSPZebra.
Add a reference to Microsoft Solver Foundation on the .NET tab.

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

Imports Microsoft.SolverFoundation.Common
Imports Microsoft.SolverFoundation.Services

using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;

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()

SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();

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)

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);

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)

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);

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)

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);

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)

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);

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)

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);

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
    )

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
  );

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)

Solution solution = context.Solve(new ConstraintProgrammingDirective());
Report report = solution.GetReport();
Console.Write("{0}", report);

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

Share via

How to: Apply a CSP to Logical Implication

To apply a constraint programming directive to the zebra puzzle

See Also

Concepts

Additional resources