csp v0.1.0 Csp
Constraint satisfaction problem definition & solver interface.
Use solve/2 for solving the csp. You can generate example CSPs with Csp.Problems module functions.
For constructing your own CSPs, you can use helpers from Csp.Domains and Csp.Constraint.
You can specify custom constraints by implementing Csp.Constraint protocol.
Additionally, you can test some example problems with the provided escript CLI.
Link to this section Summary
Functions
Returns a list of variables from assignmnet that violate constraints in csp.
Checks if (possibly partial) assignment satisfies all constraints in csp,
for which it has enough assigned variables.
Returns a list of all constraints in csp
that have variable as one of their arguments.
Returns a count of conflicts with assignment in csp,
i.e. constraints that the assignment breaks.
Returns a value for variable that will produce the minimal number of conflicts
in csp with assignment.
Orders values from variable's domain by number of violated
constraints the variable participates in in the assignment
for csp.fun()
Solves a CSP.
Checks if assignment solves csp.
Link to this section Types
assignment()
Specs
constraint()
Specs
domain()
Specs
domain() :: [value()]
solve_result()
Specs
solve_result() :: {:solved, assignment() | [assignment()]} | :no_solution
solver_status()
Specs
solver_status() :: :solved | :reduced | :no_solution
Specs
t() :: %Csp{
constraints: [Csp.Constraint.t()],
domains: %{required(variable()) => domain()},
variables: [atom()]
}
value()
Specs
value() :: any()
variable()
Specs
variable() :: atom()
Link to this section Functions
conflicted(csp, assignmnet)
Specs
conflicted(t(), assignment()) :: [variable()]
Returns a list of variables from assignmnet that violate constraints in csp.
consistent?(csp, assignment)
Specs
consistent?(t(), assignment()) :: boolean()
Checks if (possibly partial) assignment satisfies all constraints in csp,
for which it has enough assigned variables.
constraints_on(csp, variable)
Specs
constraints_on(t(), variable()) :: [Csp.Constraint.t()]
Returns a list of all constraints in csp
that have variable as one of their arguments.
count_conflicts(csp, assignment)
Specs
count_conflicts(t(), assignment()) :: non_neg_integer()
Returns a count of conflicts with assignment in csp,
i.e. constraints that the assignment breaks.
min_conflicts_value!(csp, variable, assignment)
Specs
min_conflicts_value!(t(), variable(), assignment()) :: value()
Returns a value for variable that will produce the minimal number of conflicts
in csp with assignment.
order_by_conflicts(csp, variable, assignment)
Specs
order_by_conflicts(t(), variable(), assignment()) :: [value()]
Orders values from variable's domain by number of violated
constraints the variable participates in in the assignment
for csp.fun()
solve(csp, opts \\ [])
Specs
solve(t(), Keyword.t()) :: solve_result()
Solves a CSP.
Options
The following opts are supported:
method, can be one of the following::backtracking- backtracking search, selected by default:min_conflicts- min-conflicts algorithm with tabu search:ac3- AC-3 algorithm followed by backtracking:brute_force- brute-force search.
You can pass options to backtracking (see Csp.Backtracking.solve/2 docs),
min-conflicts (Csp.MinConflicts.solve/2), or brute-force (see Csp.Searcher.brute_force/2)
in this function's opts.
solved?(csp, assignment)
Specs
solved?(csp :: t(), assignment()) :: boolean()
Checks if assignment solves csp.