Home > Uncategorized > Constraint Programming

Constraint Programming

Wikipedia defines constraint programming as:

Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. This makes constraint programming a form of declarative programming.

The clpfd library for Prolog makes it possible to express constraint programs. This way of embedding constraints in a logic program is called constraint logic programming and clpfd is indeed a shorthand for “Constraint Logic Program over Finite Domains”. Finite domains refers to the fact that the variables are limited to a finite set of values.

Other libraries that support constraint programming exists for other languages. Microsoft provides one that is accessible from .net languages that is called Microsoft Solver Foundation. Robert Pickering has published a sample where he uses it to build a Sudoku solver. The host language is F# but of course C# or Visual Basic .NET would have worked out as well. Fasail has also done the same thing.

Writing a full featured, high performance constraint solver requires lots of work but building a basic yet functional one is in fact not an overwhelming task. As an exercise I wrote one consisting of about 140 lines of F# code. It provides constraint primitives for all_different, validate_pair and has_value which makes it possible to solve both Sudoku and N-queen problems.

Ignoring a few utility functions for row, column and block extraction the Sudoku solver boils down to:

type Puzzle = int list

 

let sudoku (puzzle : Puzzle) : Puzzle list =

    let vars = newVars 81 (Set.ofList [1..9])

    let givenConds =

        [ for n, var in List.zip puzzle vars do

            if n > 0 then

                yield HasValue(var,n) :> FDCond ]   

    let gameConds = List.map (fun vars -> AllDifferent(vars) :> FDCond) (rows vars @ columns vars @ boxes vars)

    labelling vars (givenConds @ gameConds)

 

The N-queen problem can be solved using:

let nqueen n =

    let allvars = newVars n (Set.ofList [1..n])

    let rows = AllDifferent(allvars) :> FDCond

    let rec diagonals vars : FDCond list = 

        let rec diagonals’ v vrest i =

            match vrest with

            | vr::vrs ->

                let j = i + 1

                (ValidatePair(v, vr, fun v1 v2 -> v1 <> v2 + j) :> FDCond) ::

                (ValidatePair(v, vr, fun v1 v2 -> v1 <> v2 – j) :> FDCond) :: 

                diagonals’ v vrs j

            | [] -> []

        match vars with

        | v::vs -> diagonals’ v vs 0 @ diagonals vs

        | [] -> []

    labelling allvars (rows :: diagonals allvars)

 

The core of the solver consists of the following functions:

let rec solve (state : FDState) (conds : FDCond list) : FDState list =

    let state’ = propagateConstraints state conds

    if state’.Unique then

        if evalConstraints state’ conds then

            [ state’ ]

        else

            []

    else if state’.Invalid then

        []

    else

        [

            let leastAmbiguousVar = state’.LeastAmbigousVar

            for value in leastAmbiguousVar.domain do

                let state” : FDState = state’.UpdateVar { leastAmbiguousVar with domain = Set.singleton value }

                yield solve state” conds

        ] |> List.concat

 

let labelling (vars : FDVar list) (conds : FDCond list) : int list list =

    [

        let initialState = new FDState(vars)

        for solution in solve initialState conds do

            yield solution.Export

    ]

 

which means, algorithmically, that we need one mechanism for constraint propagation and one for (backtrack) search. The efficiency of the solver is related to how good it propagates constraints and this an area of active research that is beyond the scope of this post. Christian Bessier provides a lot of information on this subject in his paper, simply called constraint propagation.

Advertisements
Categories: Uncategorized
  1. Musa
    October 2, 2011 at 10:41 pm

    Help: your code gives error, can you please help fix the error

    line 6 on … new Vars 81 (^^^^

    Unexpected symbol ‘(‘ in binding. Expected incomplete structured construct at or before this point or other token.

  2. Musa
    October 3, 2011 at 8:41 am

    Sorry mibad, download from link above worked. thanks

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: