Packages
fixpoint
0.8.21
0.22.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/solver/constraints/propagators/all_different_fwc.ex
defmodule CPSolver.Propagator.AllDifferent.FWC do
use CPSolver.Propagator
@moduledoc """
The forward-checking propagator for AllDifferent constraint.
"""
defp initial_state(args) do
%{unfixed_vars: Enum.to_list(0..(length(args) - 1))}
end
@impl true
def variables(args) do
Enum.map(args, fn x_el -> set_propagate_on(x_el, :fixed) end)
end
@impl true
def filter(args) do
filter(args, initial_state(args))
end
def filter(args, nil) do
filter(args, initial_state(args))
end
@impl true
def filter(all_vars, %{unfixed_vars: unfixed_vars} = _state) do
updated_unfixed_vars = filter_impl(all_vars, unfixed_vars)
{:state, %{unfixed_vars: updated_unfixed_vars}}
end
defp filter_impl(all_vars, unfixed_vars) do
fwc(all_vars, unfixed_vars, MapSet.new(), [], false)
end
## The list of unfixed variables exhausted, and there were no fixed values.
## We stop here
defp fwc(_all_vars, [], _fixed_values, unfixed_ids, false) do
unfixed_ids
end
## The list of unfixed variables exhausted, and some new fixed values showed up.
## We go through unfixed ids we have collected during previous stage again
defp fwc(all_vars, [], fixed_values, ids_to_revisit, true) do
fwc(all_vars, ids_to_revisit, fixed_values, [], false)
end
## There is still some (previously) unfixed values to check
defp fwc(all_vars, [idx | rest], fixed_values, ids_to_revisit, changed?) do
var = Enum.at(all_vars, idx)
remove_all(var, fixed_values)
if fixed?(var) do
## Variable is fixed or was fixed as a result of removing all fixed values
fwc(all_vars, rest, MapSet.put(fixed_values, min(var)), ids_to_revisit, true)
else
## Still not fixed, put it to 'revisit' list
fwc(all_vars, rest, fixed_values, [idx | ids_to_revisit], changed?)
end
end
## Remove values from the domain of variable
defp remove_all(variable, values) do
Enum.map(
values,
fn value ->
remove(variable, value)
end
)
|> Enum.any?(fn res -> res == :fixed end)
end
end