Click here to Skip to main content
Click here to Skip to main content

Tagged as

CSP Programming of Microsoft Solver Foundation

, 16 Mar 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
Solve N-Queen problem with CSP programming of Microsoft Solver

Introduction

In this tip, we will solve N-Queen problem with Microsoft Solver Foundation with CSP programming.

CSP Programming

A lot of problems in Artificial Intelligence are classified as Constraint Satisfaction Problem or CSP. These problems are combinatorial complexity, resource allocation, planning, etc.

A Constraint Satisfaction Problem (CSP) consists of:

  • set of variables, X1, X2, …, Xn,
  • for each variable Xi a respective domain Di.
  • set of constraints, C1, C2, …, Cm, restricting the values that the variables can simultaneously take

A solution to a CSP is an assignment of every variable some value in its domain such that every constraint is satisfied. Therefore, each assignment (a state change or step in a search) of a value to a variable must be consistent: it must not violate any of the constraints.

As in any AI search problem, there can be only one, multiple or no solutions.

N-Queen Problem

The N-queens problem is to place n queens on an n × n chessboard without having them threaten each other. The queens can do the same moves of chess game: in a move that may move any number of squares vertically, horizontally and diagonally. The problem therefore is to place queens on the boxes "safe", that is not threatened by other queens; therefore intend to secure a box that cannot be achieved by a piece in a single move.

There are many ways to formulate this problem as a CSP, here an example is used in the next program.

Variables

  • { Q1, Q2, … , Qn }

Domain

  • { (1, 2, … ,n), (1, 2, … ,n), (1, 2, … ,n), (1, 2, … ,n), …….. }

Constraints

  • Alldifferent( Q1, Q2, … , Qn )
  • Alldifferent( q1-1, q2-2, … qn-n )
  • Alldifferent (q1+1, q2+2, …. qn+n)

Microsoft Solver Foundation

Microsoft Solver Foundation is an extensible .NET framework that helps you model and solve complex problems by:

  • Modeling and solving scenarios by using constraints, goals, and data.
  • Programming in the Optimization Modeling Language (OML), in C# imperatively, in F# functionally, or in any .NET Framework language.
  • Integrating third-party solvers, such as Gurobi, Mosek™, FICO™ Xpress, LINDO, CPLEX®, and lp_solve.
  • Using familiar interfaces in Microsoft Office Excel and SharePoint to create and solve models.
Microsoft Solver Foundation is a .NET solution for mathematical optimization and modeling. Solver Foundation makes it easier to build and solve real-world optimization models by providing a .NET API and runtime for model creation, reporting, and analysis; a declarative language (OML) for model specification; and powerful built-in solvers.

Solution of N-queen Problem with Microsoft Solver Foundation

In this program, we will resolve the n-queen problem with CSP programming. To perform it, we will use Microsoft Solver Foundation.

Definition of dimension of chessboard:

int N =10;

Definition of domain:

Domain domainInt = Domain.IntegerRange(0, N - 1); 

Definition of variable(decisions) with a domain. The number of variables suggest the number of column where to place the queen.

 for (int row = 0; row < N; row++)
 {
      var d = new Decision(domainInt, "decision_" + row);
      decisions.Add(d);
     _model.AddDecision(d);
 } 

Add constraints:

_model.AddConstraint("allDifferent", Model.AllDifferent(decisions.ToArray()));
 
List<term> teminiSum = new List<term>();
List<term> teminiMen = new List<term>();
 
for (int row = 0; row < N; row++)
{
  teminiSum.Add(decisions[row] + row);
  teminiMen.Add(decisions[row] - row);
}
_model.AddConstraint("diagonale1", Model.AllDifferent(teminiSum.ToArray()));
_model.AddConstraint("diagonale2", Model.AllDifferent(teminiMen.ToArray())); 

Add initial position of some queens: in the first row, the queen is in the 3rd column, in the second row, it is in the 6th position and in the 3rd column, it is in the second row.

_model.AddConstraint("constraint1", Model.Equal(decisions[0], 3));
_model.AddConstraint("constraint2", Model.Equal(decisions[1], 6));
_model.AddConstraint("constraint3", Model.Equal(decisions[2], 2)); 

Complete Program

class Program
    {
        static void Main(string[] args)
        {
            int N =10;
 
            SolverContext _context = SolverContext.GetContext();
            Model _model = _context.CreateModel();
            Domain domainInt = Domain.IntegerRange(0, N - 1);
 
            List<Decision> decisions = new List<decision>();
            for (int row = 0; row < N; row++)
            {
                var d = new Decision(domainInt, "decision_" + row);
                decisions.Add(d);
                _model.AddDecision(d);
            }
 
            _model.AddConstraint("allDifferent", Model.AllDifferent(decisions.ToArray()));
 
            List<term> teminiSum = new List<term>();
            List<term> teminiMen = new List<term>();
 
            for (int row = 0; row < N; row++)
            {
                teminiSum.Add(decisions[row] + row);
                teminiMen.Add(decisions[row] - row);
            }
 
            _model.AddConstraint("diagonale1", Model.AllDifferent(teminiSum.ToArray()));
            _model.AddConstraint("diagonale2", Model.AllDifferent(teminiMen.ToArray()));
 
            //Fix initial position
            _model.AddConstraint("constraint1", Model.Equal(decisions[0], 3));
            _model.AddConstraint("constraint2", Model.Equal(decisions[1], 6));
            _model.AddConstraint("constraint3", Model.Equal(decisions[2], 2));
 
            Solution solution = _context.Solve(new ConstraintProgrammingDirective());
 
            while (solution.Quality != SolverQuality.Infeasible)
            {
                Report report = solution.GetReport();
                Console.Write("{0}", report);
                solution.GetNext();
            }
 
            Console.ReadKey();
 
        }
    } 

The result of program is as follows:

===Solver Foundation Service Report===
Date: 3/8/2014 11:43:07 AM
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 197
Total Time (ms): 475
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
Directives:
CSP(TimeLimit = -1, MaximumGoalCount = -1, Arithmetic = Default, Algorithm = Def
ault, VariableSelection = Default, ValueSelection = Default, MoveSelection = Def
ault, RestartEnabled = False, PrecisionDecimals = 2)
Algorithm: TreeSearch
Variable Selection: DomainOverWeightedDegree
Value Selection: ForwardOrder
Move Selection: Any
Backtrack Count: 3
===Solution Details===
Goals:
 
Decisions:
decision_0: 3
decision_1: 6
decision_2: 2
decision_3: 5
decision_4: 1
decision_5: 9
decision_6: 0
decision_7: 8
decision_8: 4
decision_9: 7
===Solver Foundation Service Report===
Date: 3/8/2014 11:43:07 AM
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 197
Total Time (ms): 475
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
Directives:
CSP(TimeLimit = -1, MaximumGoalCount = -1, Arithmetic = Default, Algorithm = Def
ault, VariableSelection = Default, ValueSelection = Default, MoveSelection = Def
ault, RestartEnabled = False, PrecisionDecimals = 2)
Algorithm: TreeSearch
Variable Selection: DomainOverWeightedDegree
Value Selection: ForwardOrder
Move Selection: Any
Backtrack Count: 6
===Solution Details===
Goals:
 
Decisions:
decision_0: 3
decision_1: 6
decision_2: 2
decision_3: 9
decision_4: 5
decision_5: 1
decision_6: 8
decision_7: 4
decision_8: 0
decision_9: 7
===Solver Foundation Service Report===
Date: 3/8/2014 11:43:07 AM
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 197
Total Time (ms): 475
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
Directives:
CSP(TimeLimit = -1, MaximumGoalCount = -1, Arithmetic = Default, Algorithm = Def
ault, VariableSelection = Default, ValueSelection = Default, MoveSelection = Def
ault, RestartEnabled = False, PrecisionDecimals = 2)
Algorithm: TreeSearch
Variable Selection: DomainOverWeightedDegree
Value Selection: ForwardOrder
Move Selection: Any
Backtrack Count: 6
===Solution Details===
Goals:
 
Decisions:
decision_0: 3
decision_1: 6
decision_2: 2
decision_3: 9
decision_4: 5
decision_5: 0
decision_6: 8
decision_7: 4
decision_8: 7
decision_9: 1

These are the three solutions of the problem, where I have fixed the first 3 queens.

Conclusion

With Microsoft Solver Foundation, we can implement and solve problems with technique of CSP programming.

Microsoft Solver Foundation seems to be simple to use for CSP problems.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Giovanni Caputo
Software Developer
Italy Italy
No Biography provided
Follow on   LinkedIn

Comments and Discussions

 
Questionhow can I define my goal? Pinmembernicol_andru19-Mar-14 7:08 
Hi Giovanni,
Please help me define my model. I want to assign resources to tasks(events) and maximize the score. Every resource has assigned a score for each task(event).
I have 2 sets: one of resources and one of events:
 
Set resources = new Set(Domain.IntegerRange(0,19), "resources");
Set events = new Set(Domain.IntegerRange(0,9), "events");
Domain domainResources=Domain.IntegerRange(0,19);
 
I tried to define my decision as follows:
List<Decision> decisions = new List<Decision>();
for (int e = 0; e < Events.Length; e++)
        {
          var d = new Decision(domainResources, "decision_" + e);
          decisions.Add(d);
          model.AddDecision(d);
         }dDecision(d);
            }
 
The score is added as a parameter:
Parameter s = new Parameter(Domain.Real, "score", events, resources);
s.SetBinding(Score, "Score",0, "TaskEventId", "ResourceId");
model.AddParameters(s);
 
In my opinion the goal should look like this:
model.AddGoal("maximizeScore", GoalKind.Maximize,
               Model.Sum(Model.ForEach(events, e => s[e,decisions[e]]))
 
But this doesn't work. I get an error:
Error   2   Argument 1: cannot convert from 'Microsoft.SolverFoundation.Services.Term' to 'int' 
Please help me set up the goal in the correct way. Thanks a lot!
GeneralMy vote of 5 PinprofessionalVolynsky Alex17-Mar-14 12:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 16 Mar 2014
Article Copyright 2014 by Giovanni Caputo
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid