## 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, X
_{1}, X_{2}, …, X_{n}, - for each variable X
_{i} a respective domain D_{i}. - set of constraints, C
_{1}, C_{2}, …, C_{m}, 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

#### 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 3^{rd} column, in the second row, it is in the 6^{th} position and in the 3^{rd} 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()));
_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.