# 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](https://www.youtube.com/watch?v=ao1CO8_V5do) and [Twitch stream](https://www.twitch.tv/videos/572863390).
## Installation
The package can be installed by adding `decidex` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:csp, "~> 0.1"}
]
end
```
Docs are available [on Hex.pm](https://hexdocs.pm/csp).
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:
```elixir
%Csp{
# 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:
```elixir
Csp.solve(csp)
```
You can specify different methods, for example, min-conflicts, and pass parameters to them, e.g.:
```elixir
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:
```bash
mix deps.get
MIX_ENV=prod mix escript.build
./csp
```
## 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](https://en.wikipedia.org/wiki/Sudoku))
- Squares problem
## Future plans
- Literal constraints (e.g., `{[:x, :y], :distinct}`)
- Parallel solvers
- More examples
- Possibly:
- PC-2
- Bounds propagation