`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".