How to: Bind Decisions and Find Valid Values in a CSP

Solver Foundation 3.0

You can use constraint programming to find every possible color combination for a map that shows four countries, each a different color. None of the neighboring countries can be the same color. This is a modified version of the example in How to: Apply a Constraint Programming Directive, where the colors of two countries are specified by a user and the solver reports the values for the remaining two countries.

The following steps demonstrate 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

  1. Create a console application named MapColoring.

  2. Add a reference to Microsoft Solver Foundation on the .NET tab of the Add Reference dialog box.

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

    using Microsoft.SolverFoundation.Services;
    using Microsoft.SolverFoundation.Common;
  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 domain variable that represents the four colors available for the map. Create four decision variables that represent four countries.

    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);
  6. Add five constraints that prevent neighboring countries from being the same color.

      be != de, be != fr, be != nl, de != fr, de != nl);
  7. Add decision bindings for each country, and set the color for Belgium to red and the color for Germany to blue.

    DecisionBinding bindBe = be.CreateBinding();
    DecisionBinding bindDe = de.CreateBinding();
    DecisionBinding bindFr = fr.CreateBinding();
    DecisionBinding bindNl = nl.CreateBinding();
    DecisionBinding[] bindings = new DecisionBinding[] { bindBe, bindDe, bindFr, bindNl };
  8. Use the FindAllowedValues method to find the valid values for the remaining two countries. Write the valid values to the console window.

    string[] valuesFr = bindFr.StringFeasibleValues.ToArray();
    Console.WriteLine("France: \t{0}", string.Join(", ", valuesFr));
    string[] valuesNl = bindNl.StringFeasibleValues.ToArray();
    Console.WriteLine("Netherlands: \t{0}", string.Join(", ", valuesNl));
  9. Press F5 to build and run the code.

    The command window shows the following results.

    France: green, yellow

    Netherlands: green, yellow