Repository files navigation

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

It has an accompanyingYouTube video andTwitch stream.

The package can be installed by addingcsp to your list of dependencies inmix.exs:

defdepsdo[{:csp,"~> 0.1"}]end

Docs are availableon Hex.pm.

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

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

%Csp{# list of variable ids; could be any Elixir terms that are hashablevariables:[:x,:y,...],# domains map each variable to a list of all possible values it can be assigned todomains:%{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 satisfiedconstraints:%{# the most common kind is inequality constraint, e.g. to specify that x != y:{[:x,:y],fn[x,y]->x!=yend},...}}

You can also use helpers fromCsp.Constraints andCsp.Domains modules to simplify creating CSP definitions.

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

Csp.solve(csp)

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.getMIX_ENV=prod mix escript.build./csp

• backtracking search (supports AC-3 inference, andvariable_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!)

• N Queens (with 3 different representations)
• Map coloring
• Sudoku (takenfrom here)
• Squares problem

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