CSP Programming of Microsoft Solver Foundation

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₁, X₂, …, X_n,
• for each variable X_i a respective domain D_i.
• set of constraints, C₁, C₂, …, 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

• { 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 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()));
 
            //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.