11,433,997 members (58,605 online)
Tip/Trick

# CSP Programming of Microsoft Solver Foundation

, 16 Mar 2014 CPOL
 Rate this:
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);
} ```

```_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++)
{
}

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("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);
}

List<term> teminiSum = new List<term>();
List<term> teminiMen = new List<term>();

for (int row = 0; row < N; row++)
{
}

//Fix initial position

Solution solution = _context.Solve(new ConstraintProgrammingDirective());

while (solution.Quality != SolverQuality.Infeasible)
{
Report report = solution.GetReport();
Console.Write("{0}", report);
solution.GetNext();
}

}
} ```

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.

## About the Author

Software Developer
Italy
No Biography provided

## Comments and Discussions

 First Prev Next
 how can I define my goal? nicol_andru19-Mar-14 7:08 nicol_andru 19-Mar-14 7:08
 My vote of 5 Volynsky Alex17-Mar-14 12:03 Volynsky Alex 17-Mar-14 12:03
 Last Visit: 31-Dec-99 19:00     Last Update: 5-May-15 3:20 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

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