A ‘Bucket Elimination’ Constraint Solver in F#

Constraint Programming is a vast subject area in AI and Operations Research. Some well-known Constraint Satisfaction Problems (CSP) are Sudoku, N-Queens, Map Coloring, Scheduling (of many kinds, e.g. classrooms-to-courses).

In general, CSP are NP-hard but many techniques/algorithms have emerged to tackle such problems. The two basic approaches used are Search and Inference. There are many variations of each and the two are often mixed together. Arc Consistency 3 (AC-3) is one of best known inference algorithms which uses constraint propagation.

The definitive textbook on CSP is “Constraint Processing” by Dr. Rina Dechter. One interesting algorithm presented in the book is “Bucket Elimination”. Bucket Elimination is closely related to Variable Elimination which is used in a variety of areas and can be considered a general framework for reasoning or inference.

For a CSP, Bucket Elimination gives back a ‘compressed’ representation of the underlying ‘knowledge’ that can be useful for further exploration – beyond just finding all solutions. For example, given a partial variable assignment one easily determine the possible assignments of other variables that would lead to a solution.

Here is an experimental implementation of the Bucket Elimination algorithm in F#:

The implementation provides a DSL to declaratively model finite domain CSPs. The constraint programming ‘language’ (i.e. the DSL) does not currently provide ‘global constraints’ such as “allDifferent” but the language can be easily extended, if needed.

The solution includes samples for N-Queens; Map Coloring and “SEND+MORE=MONEY” problems.

The following code is from the 4-Queens sample:

let domain = intSet [for i in 1..4 -> i]

//variables
let x1 = VarDef(“x1”, domain)
let x2 = VarDef(“x2”, domain)
let x3 = VarDef(“x3”, domain)
let x4 = VarDef(“x4”, domain)

let constraints =
[
//all different
&x1 != &x2
&x2 != &x3
&x3 != &x4
&x1 != &x3
&x2 != &x4
//safe
Abs(&x1 – &x2) != 1I
Abs(&x2 – &x3) != 1I
Abs(&x3 – &x4) != 1I
Abs(&x1 – &x3) != 2I
Abs(&x1 – &x4) != 3I
Abs(&x2 – &x4) != 2I
]

let cs = ConstraintSystem([x1;x2;x3;x4], constraints)
let solSet = solve cs

Advertisements

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