fdjs
v0.1.0
Published
Finite Domain Constrain Solver
Downloads
3
Readme
fd.js
is a Javascript finite domain constraint programming (CP) library with
a design based on the CP features of Mozart/Oz. In particular, fd.js
aims to
separate the concerns of constraint problem specification, branching strategy
and search strategy through the use of "computation spaces".
Status
Work very much in progress, but the library is already useful enough to solve simple puzzles.
Here are some cool student projects built using FD.js -
- Search tree visualization
- CompOzeJS
- RoCoCo - Sports tournament scheduling
- Nonogram solver
Related links
Acknowledgement
Thanks to Dr. Martin Henz for his excellent introduction to finite domain constriant programming with Mozart/Oz which inspired this library.
License
All source code part of the fd.js
project is licensed under the permissive New BSD license.
FD
This is the top level "module" that you get when you load fd.js.
FD.space
"Computation space" class holding variables and propagators. You create a new "computation space" by doing -
var S = new FD.space();
S.clone()
Creates a "clone" of the space S. Further computations carried out in the clone do not affect S.
S.propagate()
Runs all propagators until no more can run - i.e. until the space becomes "stable" or "failed". Propagators fail by throwing a "fail" exception. So if this call returns, you've got a stable space.
S.is_solved()
Checks all the fd vars in the space and returns true if all of them have singleton domains and false otherwise.
S.inject(script)
Calls script(S) so that the script can add propagators to the space and any needed branchers. Returns S.
S.decl(name_or_names, dom?)
Declares the given named fd vars. If dom is specified, initializes the domains of all of them to the given domain. A domain is specified as an array of intervals like this -
[[10,20],[100,133],[1729,3551]]
The sub-intervals should not overlap and must be in increasing order. Both the bounds of each sub-interval are considered to be included in the domain. Returns S.
S.temp(dom?) and S.temps(N, dom?)
Creates new temporary or intermediate fd variables whose names you don't want to bother with. Returns the name of the temporary variable.
S.konst(n)
Currently shorthand for S.temp([[n, n]])
. Might be optimized in the future.
Propagators
Propagators are provided as method invocations on a space and all such calls return the space itself as the result so that further method invocations can be concatenated.
S.eq(v1name, v2name)
Asserts that fd variable named v1name
is equal to that named v2name
.
S.lt(v1name, v2name)
Asserts that fd variable v1
is strictly less than v2
.
S.gt(v1name, v2name)
Asserts that fd variable v1
is strictly greater
than v2
.
S.lte(v1name, v2name)
Asserts that fd variable v1
is less than or equal to v2
.
S.gte(v1name, v2name)
Asserts that fd variable v1
is greater than or equal to v2
.
S.neq(v1name, v2name)
Asserts that fd variables v1
and v2
must be different.
S.distinct(names)
Asserts that all the variables in the given array are pair-wise distinct.
S.plus(v1name, v2name, sumname)
Asserts v1 + v2 = sum
and propagates domain changes to all three fd vars.
S.times(v1name, v2name, prodname)
Asserts v1 * v2 = prod
and propagates domain changes to all three fd vars.
S.scale(factor, vname, prodname)
Asserts factor * v = prod + v2 = sum
and propagates domain changes to both fd
vars. factor has to be a constant and not an fd var.
S.times_plus(k1, v1name, k2, v2name, resultname)
Asserts k1 * v1 + k2 * v2 = result
. k1
and k2
have to be constants and
not fd vars.
S.sum(vnames, sumname)
Asserts that the sum of all the variables in the given vnames array equals the sumname variable.
S.product(vnames, prodname)
Asserts that the product of all the variables in the given vnames array equals the prodname variable.
S.wsum(kweights, vnames, sumname)
kweights
is an array of constant natural numbers and vnames
is an array of
fd var names of the same length as kweights. This then adds propagators that
ensure that the weighted sum of these variables equals the given sum variable.
S.reified(opname, argv, boolname)
Provides support for reified propagators. Currently only the various comparison
propagators are supported - i.e. opname can be one of 'eq', 'lt', 'gt', 'lte'
or 'gte' only. Any other value will throw an exception. argv
must be an array
of variable names to which the comparison is applied. boolname
must be the
name of a declared fdvar that will be constrained to take on either 0 or 1. If
boolname
is omitted, then a temporary variable is allocated and returned as
the result, thus permitting reified
to be used with "functional notation".
See the test_mozart_photo_bab
example for use of reified comparison
propagators. For example, to reify the comparison X < Y as the boolean variable
Z, do this -
S.reified('lt', ['X', 'Y'], 'Z');
Functional notation
Propagator methods such as plus, times, sum and wsum take the "result variable" as the last argument. Quite often, you'll need to create an intermediate (i.e. "temporary") variable to hold a result. To make that easier, omitting the last result argument will cause the propagator method to automatically create a temporary for the result and return the name of the created temporary instead of the space on which the method was invoked. This lets us use a convenient "functional" syntax. For an example, see the test_send_more_money_fn script in tests.js and compare it with the test_send_more_money script.
FD.distribute
A namespace that holds various distribution strategies.
FD.distribute.naive(S, varname)
Walks through the values in the do main of the specified variable. varname can also be an array of variable names in which case the "naive" call will automatically run for each of the given variables in sequence. This auto-mapping behaviour is for programming convenience.
FD.distribute.fail_first(S, varnames)
Given an array of variable names, figures out the one with the smallest domain and branches on it first, then moving on to the immediately larger domain, and so on.
FD.distribute.split(S, varname)
Adds branchers that split the domain of the specified fdvar (or variables, if an array or an object with fdvars was supplied) into pieces for each branch. A variable's domain is first split at the holes and once it has no holes, it is split down the middle.
FD.search
A namespace that holds various search strategies.
FD.search.depth_first(state)
Implements the "depth first" search strategy. state
is expected to be an
object whose space
property is the starting space for the search. The state
object is also the return value, but with additional properties filled in. On
return, if state.status
is the string "solved"
, then state.space
is a
solution. If there may be more solutions, then state.more
will be true
. If
no solution space is found even after considering branchers, then
state.status
will be set to "end"
upon return and state.more will be
false
. If you want to get all possible solutions, then you need to
iteratively call depth_first
passing the returned state of one call as the
argument of the next call and collect all the cases where state.status
is
"solved"
.
FD.search.branch_and_bound(state, ordering)
Finds the "best" solution according to the given ordering function. The state
parameter is similar to the depth_first
search function. It is expected to be
an object such that state.space
gives the space from which to search for the
best solution.
The state
is also what is returned by branch_and_bound
and state.space
will be the space with the best solution found during the search. When a
solution exists, state.status
will be the string "solved".
The ordering
argument is expected to be a function of the form
function (space, a_solution) { ... }
where the space
argument is the space into which the ordering function should
inject the new constraints for the ordering, and a_solution
is an object
whose keys are root finite domain variable names and whose values are the
solved values of those variables. The return value of the ordering function is
irrelevant.
There are two ways to use the branch_and_bound function -
In one shot mode where a single call will give you the best solution that it can find, if a solution exists at all.
In "single step" mode, indicated by setting state.single_step
to true
. In
this mode, the function will return whenever it finds a solved space and
state.more
will indicate whether there may be any more solutions to look at.
In this mode, every call will result in a solution that is "better" than the
one found before it, due to the ordering
function.
Note that if state.more
is false
, then definitely there are no more
solutions to look at, but if it is true
, there may be more solutions to
look at. If a subsequent search turns up empty, it is indicated by
state.status
being set to the string "end".