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.

    
    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 domain variable that represents the four colors available for the map. Create 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)
    
    
    
  6. Add five constraints that prevent neighboring countries from being the same color.

    
    model.AddConstraints("borders",
                         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.

    
    Dim bindBe As DecisionBinding = be.CreateBinding()
    Dim bindDe As DecisionBinding = de.CreateBinding()
    Dim bindFr As DecisionBinding = fr.CreateBinding()
    Dim bindNl As DecisionBinding = nl.CreateBinding()
    Dim bindings As DecisionBinding() = New DecisionBinding() {bindBe, bindDe, bindFr, bindNl}
    
    bindBe.Fix("red")
    bindDe.Fix("blue")
    
    
    
  8. Use the FindAllowedValues method to find the valid values for the remaining two countries. Write the valid values to the console window.

    
    context.FindAllowedValues(bindings)
    Dim valuesFr As String() = bindFr.StringFeasibleValues.ToArray()
    Console.WriteLine("France: " & vbTab & "{0}", String.Join(", ", valuesFr))
    
    Dim valuesNl As String() = bindNl.StringFeasibleValues.ToArray()
    Console.WriteLine("Netherlands: " & vbTab & "{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

Show: