How to: Apply a Constraint Programming Directive

Article
12/06/2011

You can use constraint programming to find every possible coloring of a map with four colors. The map has four countries and none of the neighboring countries can be the same color.

The following steps show how to use Solver Foundation to create and solve the map coloring problem by using the Solver Foundation Services layer.

To apply a constraint programming directive to map coloring

Create a Console Application named MapColoring.
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.Services;
using Microsoft.SolverFoundation.Common;

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 domain variable that represents the four colors available for the map and four decision variables that represent four countries.

Dim colors As Domain = Domain.Enum("red", "green", "blue", "yellow")
Dim be As Decision = New Decision(colors, "belgium")
Dim de As Decision = New Decision(colors, "germany")
Dim fr As Decision = New Decision(colors, "france")
Dim nl As Decision = New Decision(colors, "netherlands")
model.AddDecisions(be, de, fr, nl)

Domain colors = Domain.Enum("red", "green", "blue", "yellow");
Decision be = new Decision(colors, "belgium");
Decision de = new Decision(colors, "germany");
Decision fr = new Decision(colors, "france");
Decision nl = new Decision(colors, "netherlands");
model.AddDecisions(be, de, fr, nl);

Add five constraints that prevent neighboring countries from having the same color.

model.AddConstraints("borders",
                     be <> de, be <> fr, be <> nl, de <> fr, de <> nl)

model.AddConstraints("borders", 
  be != de, be != fr, be != nl, de != fr, de != nl);

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())
While (solution.Quality <> SolverQuality.Infeasible)
    Console.WriteLine("Belgium: {0}" & vbTab &
                      "Germany: {1}" & vbTab &
                      "France: {2}" & vbTab &
                      "Netherlands: {3}",
                      be, de, fr, nl)
    solution.GetNext()
End While

Solution solution = context.Solve(new ConstraintProgrammingDirective());
while (solution.Quality != SolverQuality.Infeasible) {
  Console.WriteLine("Belgium: {0}\tGermany: {1}\tFrance: {2}\tNetherlands: {3}",
    be, de, fr, nl);
  solution.GetNext();
}

Press F5 to build and run the code.

The command window shows the following results.

Belgium: green Germany: red France: blue Netherlands: blue

Belgium: green Germany: red France: yellow Netherlands: blue

Belgium: green Germany: red France: blue Netherlands: yellow

Belgium: green Germany: red France: yellow Netherlands: yellow

Belgium: blue Germany: red France: green Netherlands: green

Belgium: blue Germany: red France: green Netherlands: yellow

Belgium: blue Germany: red France: yellow Netherlands: green

Belgium: blue Germany: red France: yellow Netherlands: yellow

Belgium: yellow Germany: red France: green Netherlands: green

Belgium: yellow Germany: red France: blue Netherlands: green

Belgium: yellow Germany: red France: green Netherlands: blue

Belgium: yellow Germany: red France: blue Netherlands: blue

Belgium: red Germany: green France: blue Netherlands: blue

Belgium: red Germany: green France: blue Netherlands: yellow

Belgium: red Germany: green France: yellow Netherlands: blue

Belgium: red Germany: green France: yellow Netherlands: yellow

Belgium: blue Germany: green France: red Netherlands: red

Belgium: blue Germany: green France: yellow Netherlands: red

Belgium: blue Germany: green France: red Netherlands: yellow

Belgium: blue Germany: green France: yellow Netherlands: yellow

Belgium: yellow Germany: green France: red Netherlands: red

Belgium: yellow Germany: green France: red Netherlands: blue

Belgium: yellow Germany: green France: blue Netherlands: red

Belgium: yellow Germany: green France: blue Netherlands: blue

Belgium: red Germany: blue France: green Netherlands: green

Belgium: red Germany: blue France: yellow Netherlands: green

Belgium: red Germany: blue France: green Netherlands: yellow

Belgium: red Germany: blue France: yellow Netherlands: yellow

Belgium: green Germany: blue France: red Netherlands: red

Belgium: green Germany: blue France: red Netherlands: yellow

Belgium: green Germany: blue France: yellow Netherlands: red

Belgium: green Germany: blue France: yellow Netherlands: yellow

Belgium: yellow Germany: blue France: red Netherlands: red

Belgium: yellow Germany: blue France: green Netherlands: red

Belgium: yellow Germany: blue France: red Netherlands: green

Belgium: yellow Germany: blue France: green Netherlands: green

Belgium: red Germany: yellow France: green Netherlands: green

Belgium: red Germany: yellow France: green Netherlands: blue

Belgium: red Germany: yellow France: blue Netherlands: green

Belgium: red Germany: yellow France: blue Netherlands: blue

Belgium: green Germany: yellow France: red Netherlands: red

Belgium: green Germany: yellow France: blue Netherlands: red

Belgium: green Germany: yellow France: red Netherlands: blue

Belgium: green Germany: yellow France: blue Netherlands: blue

Belgium: blue Germany: yellow France: red Netherlands: red

Belgium: blue Germany: yellow France: red Netherlands: green

Belgium: blue Germany: yellow France: green Netherlands: red

Belgium: blue Germany: yellow France: green Netherlands: green

How to: Apply a Constraint Programming Directive

To apply a constraint programming directive to map coloring

See Also

Concepts

Additional resources