csp v0.1.0 Csp.AC3
Pure AC-3 algorithm implementation.
Also provides reduce/3 helper that can be used as an inference part of search algorithms.
Link to this section Summary
Functions
Reduces the csp with AC-3.
Tries to solve csp with AC-3 algorithm, applying node and arc consistency.
Link to this section Types
domain_reduction()
Specs
domain_reduction() :: {Csp.t(), Csp.assignment(), unassigned()}
reduce_result()
Specs
reduce_result() :: {:ok, Csp.t(), Csp.assignment(), unassigned()} | :no_solution
unassigned()
Specs
unassigned() :: [Csp.variable()]
Link to this section Functions
reduce(csp, assignment, unassigned)
Specs
reduce(Csp.t(), Csp.assignment(), unassigned()) :: reduce_result()
Reduces the csp with AC-3.
Accepts csp with assignment (map from variables to their assigned values),
and a list of unassigned variables.
Compared to solve/2, apart from tracking the assignment, it also uses
simplified version of domain reduction for constraint: it doesn't attempt
to track affected constraints when reducing some constraint's domain.
Returns :no_solution if an inconsistency is detected, or a tuple of
{:ok, csp, assignment, unassigned}, where domains of csp are reduced,
assignment is amended with inferred variable assignments, and
unassigned list is updated to reflect those assignment changes.
solve(csp)
Specs
solve(Csp.t()) :: {Csp.solver_status(), Csp.t()}
Tries to solve csp with AC-3 algorithm, applying node and arc consistency.
Only considers unary and binary constraints; will skip n-ary constraints where n > 2.
Returns a tuple {status, csp}.
The returned csp will possibly have reduced domains.
If all variables have domain length of 1, we found a solution (:solved status is returned).
If any variable has a domain length of 0, we proved that csp is not solvable,
and :no_solution status is returned.
If neither of those conditions is true, :reduced status is returend, irrespective of
any actual domain reduction occuring.