# Constraint Satisfaction

This is a basic implementation of constraint satisfaction problem solver algorithms and some example problems in Elixir.

It has an accompanying [YouTube video]( and [Twitch stream](

## Installation

The package can be installed by adding `decidex` to your list of dependencies in `mix.exs`:

def deps do
    {:csp, "~> 0.1"}

Docs are available [on](

The library is dually licensed under Apache 2 or MIT (choose whichever you prefer).

## Usage

Constraints are modelled as normal Elixir structs, with the following structure:

  # list of variable ids; could be any Elixir terms that are hashable
  variables: [:x, :y, ...],
  # domains map each variable to a list of all possible values it can be assigned to
  domains: %{
    x: [1, 2, 3, 4],
    y: [true, false],
  # constraints are specified as a list of tuples `{arguments_list, predicate}`.
  # `arguments_list` is a list of variables participating in the constraint.
  # `predicate` is an unary function taking a list of those variables values (in the same order)
  # and returning `true` or `false` signifying if the constraint was satisfied
  constraints: %{
    # the most common kind is inequality constraint, e.g. to specify that x != y:
    {[:x, :y], fn [x, y] -> x != y end},

You can also use helpers from `Csp.Constraints` and `Csp.Domains` modules to simplify creating CSP definitions.

Once you have a CSP definition, you can solve it:


You can specify different methods, for example, min-conflicts, and pass parameters to them, e.g.:

Csp.solve(csp, method: :min_conflicts, tabu_depth: 10)

Additionally, you can check this repo out, build the provided escript, and play with the CLI interface for the example problems:

mix deps.get
MIX_ENV=prod mix

## Currently implemented solvers

- backtracking search (supports AC-3 inference, and `variable_selector` strategies: naïve, minimum remaining values, and custom)
- min-conflicts with tabu search
- AC-3 with backtracking to extract results
- brute-force search (used for performance comparisons with backtracking; don't use it in the real code!)

## Currently provided test problems

- N Queens (with 3 different representations)
- Map coloring
- Sudoku (taken [from here](
- Squares problem

## Future plans

- Literal constraints (e.g., `{[:x, :y], :distinct}`)
- Parallel solvers
- More examples
- Possibly:
  - PC-2
  - Bounds propagation