Geeks With Blogs

News

Charles Young
       

As promised in my last post (http://geekswithblogs.net/cyoung/archive/2009/02/24/129639.aspx), I had a look at the Express edition of Microsoft Solver Framework (http://code.msdn.microsoft.com/solverfoundation), and used it to implement the Einstein puzzle using the built-in CSP solver and C#.  Creating the solution proved particularly easy for the simple reason that Microsoft provides a worked example of a politically corrected ‘Zebra’ variant in their documentation (no tobacco or beer in sight).  You will find this as Sample 8 in the SFS Programming Primer document that comes with the download. 

To begin with, I simply amended this code, putting all the non-pc bits back in, and bought it into line with Daniel’s example (see https://www.ibm.com/developerworks/mydeveloperworks/blogs/brms/entry/einsteinspuzzle?lang=env).  It worked first time!!   I didn’t like the raw format used to report on decisions, so I wrote an additional method to print the solution.  I also found having to declare every separate 'Decision' (essentially representing a bound variable for output) rather verbose.   Hence, I wrote an additional helper class called DVar which deliberately emulates dvar in ILOG's CP optimizer.   There is no equivalent to dvar in the current version of the Modelling API although it may be possible to use Parameters, Sets and databinding in a somewhat similar way (more research needed!).   I have very deliberately structured the code to be as close to the ILOG example as possible.

On my reasonably specified notebook, the Microsoft solver reported that it took 73 milliseconds to solve the puzzle and 169 ms in total. This appears to be slower than the ILOG solver, but obviously this is not a comparative test.   I have no idea what hardware ILOG used, and no conclusions should be drawn from these results.   More than this, I personally have no interest in doing comparative performance testing of CP solvers.   Also, note that the use of the DVar class did not add any noticable overhead.

Here is the code:

/*
* Copyright © 2009 Charles Young
*
* This program is free software; you can redistribute it and/or
* modify it as you wish.
*
* The software is licensed "as-is". The author gives no express warranties,
* guarantees or conditions. To the extent permitted under your local laws,
* the author excludes the implied warranties of merchantability, fitness
* for a particular purpose and non-infringement.
* */
namespace Einstein
{
using System;
using System.Collections.Generic;
using Microsoft.SolverFoundation.Services;
 
/// <summary>
/// The Einstein puzzle, implemented using the Microsoft Solver Foundation and the default CSP solver.
/// </summary>
public class Puzzle
{
// Decision variables
private static DVar s;
private static DVar a;
private static DVar d;
private static DVar k;
private static DVar c; 
        /// <summary>
/// Run the programme.
/// </summary>
public static void Main()
{
Solve();
}

  /// <summary>
/// Solve the Einstein puzzle using the default CSP solver in MSF.
/// </summary>
public static void Solve()
{
var context = SolverContext.GetContext();
 
// ======================================
// Create and define the model...
// ======================================
 
var model = context.CreateModel();
 
         string[] States = { "Brit", "Swede", "Dane", "Norwegian", "German"};
        string[] Animals = { "dogs", "fish", "birds", "cats", "horses"};
        string[] Drinks = { "tea", "coffee", "milk", "beer", "water"};
        string[] Smoke = { "Pall Mall", "Dunhill", "Blends", "Blue Master", "Prince" };
string[] Colors = { "red", "green", "white", "yellow", "blue"};
 
        // All decisions take integer values from 1-5
        s = new DVar(model, States, Domain.IntegerRange(1, 5));
        a = new DVar(model, Animals, Domain.IntegerRange(1, 5));
        d = new DVar(model, Drinks, Domain.IntegerRange(1, 5));
        k = new DVar(model, Smoke, Domain.IntegerRange(1, 5));
         c = new DVar(model, Colors, Domain.IntegerRange(1, 5));

         // Add global constraints to prevent two decisions in a set having the same value
model.AddConstraints("constraints",
 
          // AllDifferent needed
          Model.AllDifferent(s.Decisions),
          Model.AllDifferent(a.Decisions),
          Model.AllDifferent(d.Decisions),
          Model.AllDifferent(k.Decisions),
          Model.AllDifferent(c.Decisions),
 
          // 1. The Brit lives in a red house.
          s["Brit"] == c["red"],
          // 2. The Swede keeps dogs as pets.
          s["Swede"] == a["dogs"],
          // 3. The Dane drinks tea.
          s["Dane"] == d["tea"],
          // 5. The owner of the Green house drinks coffee.
          c["green"] == d["coffee"],
          // 6. The person who smokes Pall Mall rears birds.
          k["Pall Mall"] == a["birds"],
          // 7. The owner of the Yellow house smokes Dunhill.
          c["yellow"] == k["Dunhill"],
          // 8. The man living in the centre house drinks milk.
         d["milk"] == 3,
         // 9. The Norwegian lives in the first house.
         s["Norwegian"] == 1,
         // 12. The man who smokes Blue Master drinks beer.
         k["Blue Master"] == d["beer"],
         // 13. The German smokes Prince.
         s["German"] == k["Prince"],
         // 4. The Green house is on the left of the White house.
         c["green"] == c["white"] - 1,
         // 10. The man who smokes Blends lives next to the one who keeps cats.
         Model.Abs(k["Blends"] - a["cats"]) == 1,
         // 11. The man who keeps horses lives next to the man who smokes Dunhill.
         Model.Abs(a["horses"] - k["Dunhill"]) == 1,
         // 14. The Norwegian lives next to the blue house.
         Model.Abs(s["Norwegian"] - c["blue"]) == 1,
          // 15. The man who smokes Blends has a neighbour who drinks water.
         Model.Abs(k["Blends"] - d["water"]) == 1
);

// ======================================
// Solve with the built-in CSP solver...
// ======================================
        // Use default directives for CS solver
var solution = context.Solve(new ConstraintProgrammingDirective());
 
// ======================================
// Print the results...
// ======================================
 
// Print the generated report without decisions
var report = solution.GetReport(ReportVerbosity.SolverDetails | ReportVerbosity.Directives);
Console.Write("{0}", report);
 
// Print the decisions
PrettyPrintDescisions();
}
 
    /// <summary>
    /// Print results in a readable fashion
   
/// </summary>
    private static void PrettyPrintDescisions()
    {
       // Sort the decision data
       var statesSorted = GetSortedDecisionData(s);
       var animalsSorted = GetSortedDecisionData(a);
       var drinksSorted = GetSortedDecisionData(d);
       var smokeSorted = GetSortedDecisionData(k);
       var coloursSorted = GetSortedDecisionData(c);

        Console.WriteLine("\n\rSOLUTION:");

       for (var pos = 1; pos <= 5; pos++)
        {
         Console.WriteLine("House " + pos + ": {0}, {1}, {2}, {3}, {4}", statesSorted[pos], animalsSorted[pos], drinksSorted[pos], smokeSorted[pos], coloursSorted[pos]);
        }

       Console.WriteLine();
    }
 
    /// <summary>
    /// Returns a sorted dictionary of decision data
    /// </summary>
    /// <param name="dvar">A decision variable containing a collection of decisions.</param>
    /// <returns>A sorted dictionary of decision data</returns>
    private static SortedDictionary<int, string> GetSortedDecisionData(DVar dvar)
    {
       var sortedData = new SortedDictionary<int, string>();

       foreach (var decision in dvar.Decisions)
       {
           sortedData.Add(decision.ToInt32(), decision.Name);
        }
 
        return sortedData;
    }
 
 
    /// <summary>
    /// Represents a decision variable. Emulates dvar in ILOG CP Optimizer
    /// </summary>
    class DVar
    {
       // Collection of decisions for the given decision variable
       Dictionary<string, Decision> decisions = new Dictionary<string, Decision>();

       /// <summary>
       /// Constructor
       /// </summary>
        /// <param name="model">MSF model that contains the decisions.</param>
        /// <param name="keys">Array of string values of keys.</param>
        /// <param name="domain">The domain of the variable</param>
        public DVar(Model model, string[] keys, Domain domain)
        {
            if (keys != null)
            {
                foreach (var key in keys)
                {
                    var decision = new Decision(domain, key);
                    decisions.Add(key, decision);
                    model.AddDecision(decision);
               }
           }
        }
 
        /// <summary>
       /// Indexer.
        /// </summary>
        /// <param name="key">Key value.</param>
        /// <returns>A decision, referenced by key.</returns>
       public Decision this[string key]
        {
            get
            {
                return
decisions[key];
            }
        }
 
        /// <summary>
        /// Array of all decisions for the decision variable.
        /// </summary>
        public Decision[] Decisions
        {
            get
            {
                var decisionsOut = new Decision[decisions.Values.Count];
                decisions.Values.CopyTo(decisionsOut, 0);
                return decisionsOut;
            }
        }
    }

}
 
Here is the output:

===Solver Foundation Service Report===
Datetime: 02/25/2009 14:29:56
Model Name: Default
Capabilities requested: CP
Solve Time (ms): 73
Total Time (ms): 169
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: TreeSearch
Variable Selection: Any
Value Selection: Any
Move Selection: Any
===Solution Details===
Goals:

SOLUTION:
House 1: Norwegian, cats, water, Dunhill, yellow
House 2: Dane, horses, tea, Blends, blue
House 3: Brit, birds, milk, Pall Mall, red
House 4: German, fish, coffee, Prince, green
House 5: Swede, dogs, beer, Blue Master, white

Posted on Wednesday, February 25, 2009 3:12 PM | Back to top


Comments on this post: Einstein Puzzle in Microsoft Solver Foundation

# re: Einstein Puzzle in Microsoft Solver Foundation
Requesting Gravatar...
Looks interesting. I've never tried microsoft's solver, so it's cool to see an example. I might have to download it in my copious free time.

peter
Left by peter lin on Feb 27, 2009 2:16 PM

# re: Einstein Puzzle in Microsoft Solver Foundation
Requesting Gravatar...
I tried the code listed here, but it did not compile. The reason is that "decision" does not have the method "ToInt32" stated in this line of code:

sortedData.Add(decision.ToInt32(), decision.Name);

Please let me know how you made it compile. Thanks.

Sam
Left by Sam Anani on Sep 16, 2010 12:41 PM

Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net