Packages
fixpoint
0.8.49
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.
"""
@impl true
def arguments(args) do
Arrays.new(args, implementation: Aja.Vector)
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(all_vars, state, changes) do
new_fixed = Map.keys(changes) |> MapSet.new()
{unresolved, fixed} =
(state &&
{state[:unresolved] |> MapSet.difference(new_fixed), fixed_values(all_vars, new_fixed)}) ||
initial_split(all_vars)
case fwc(all_vars, unresolved, fixed) do
false -> :passive
unfixed_updated_set -> {:state, %{unresolved: unfixed_updated_set}}
end
end
defp fixed_values(vars, fixed) do
Enum.reduce(fixed, MapSet.new(), fn idx, values_acc ->
val = Propagator.arg_at(vars, idx) |> min()
(val in values_acc && fail()) || MapSet.put(values_acc, val)
end)
end
defp initial_split(vars) do
Enum.reduce(0..(Arrays.size(vars) - 1), {MapSet.new(), MapSet.new()}, fn idx,
{unfixed_acc,
fixed_vals_acc} ->
var = Propagator.arg_at(vars, idx)
if fixed?(var) do
val = min(var)
(val in fixed_vals_acc && fail()) || {unfixed_acc, MapSet.put(fixed_vals_acc, val)}
else
{MapSet.put(unfixed_acc, idx), fixed_vals_acc}
end
end)
end
defp fwc(vars, unfixed_set, fixed_values) do
{updated_unfixed, _fixed_vals} = remove_values(vars, unfixed_set, fixed_values)
MapSet.size(updated_unfixed) > 1 && updated_unfixed
end
## unfixed_set - set of indices for yet unfixed variables
## fixed_values - the set of fixed values we will use to reduce unfixed set.
defp remove_values(vars, unfixed_set, fixed_values) do
for idx <- unfixed_set, reduce: {MapSet.new(), fixed_values} do
{still_unfixed_acc, fixed_vals_acc} ->
var = Propagator.arg_at(vars, idx)
case remove_all(var, fixed_vals_acc) do
false ->
## Variable is still unfixed, keep it
{MapSet.put(still_unfixed_acc, idx), fixed_vals_acc}
new_fixed_value ->
fixed_vals_acc = MapSet.put(fixed_vals_acc, new_fixed_value)
{unfixed_here, fixed_here} =
remove_values(vars, still_unfixed_acc, MapSet.new([new_fixed_value]))
{unfixed_here, MapSet.union(fixed_here, fixed_vals_acc)}
end
end
end
defp remove_all(var, values) do
Enum.reduce_while(values, false, fn val, acc ->
if remove(var, val) == :fixed do
{:halt, :fixed}
else
{:cont, acc}
end
end)
|> case do
false ->
fixed?(var) && min(var)
:fixed ->
min(var)
end
|> then(fn new_min -> new_min && ((new_min in values && fail()) || new_min) end)
end
defp fail() do
throw(:fail)
end
end