Packages
fixpoint
0.12.9
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/element2d.ex
defmodule CPSolver.Propagator.Element2D do
use CPSolver.Propagator
import CPSolver.Utils
@moduledoc """
The propagator for Element2D constraint.
array2d[row_index][col_index] = value
"""
def new(array2d, row_index, col_index, value) do
new([array2d, row_index, col_index, value])
end
@impl true
def variables([_array2d, row_index, col_index, value]) do
[
set_propagate_on(row_index, :domain_change),
set_propagate_on(col_index, :domain_change),
set_propagate_on(value, :domain_change)
]
end
defp initial_state([[], _row_index, _col_index, _value]) do
throw(:fail)
end
defp initial_state([array2d, row_index, col_index, value]) do
num_rows = length(array2d)
num_cols = length(hd(array2d))
initial_reduction(array2d, row_index, col_index, value, num_rows, num_cols)
build_state(array2d, row_index, col_index, value, num_rows, num_cols)
end
def build_state(array2d, row_index, col_index, value, num_rows, num_cols) do
## Build a state graph.
## Three sets of vertices: ([{:value, value}], [{:row_index, value}], [{:col_index, value}])
## with edges from {:value, z_value} to {:row_index, x_value},
## where z_value is present in x_value row of array2d.
## Likewise, with edges from {:value, z_value} to {:col_index, y_value},
## where z_value is present in y_value column of array2d.
for i <- 0..(num_rows - 1), j <- 0..(num_cols - 1), reduce: Graph.new() do
acc ->
if contains?(row_index, i) && contains?(col_index, j) do
table_value = Enum.at(array2d, i) |> Enum.at(j)
if contains?(value, table_value) do
acc
|> Graph.add_edge({:value, table_value}, {:row_index, i}, label: {:col_index, j})
|> Graph.add_edge({:value, table_value}, {:col_index, j}, label: {:row_index, i})
else
acc
end
else
acc
end
end
end
defp initial_reduction(array2d, row_index, col_index, value, num_rows, num_cols) do
# x and y are indices in array2d,
# so we trim D(x) and D(y) accordingly.
removeBelow(row_index, 0)
removeAbove(row_index, num_rows - 1)
removeBelow(col_index, 0)
removeAbove(col_index, num_cols - 1)
## D(value) is bounded by min and max of the array2d
{arr_min, arr_max} = array2d_min_max(array2d)
removeAbove(value, arr_max)
removeBelow(value, arr_min)
end
defp maybe_reduce_domains(row_index, col_index, value, %Graph{} = graph) do
(maybe_fix(row_index, col_index, value, graph) && :passive) ||
(
{updated_graph, changed?} =
Enum.reduce(Graph.vertices(graph), {graph, false}, fn
{:value, _} = v, acc ->
maybe_remove_vertex(v, value, acc)
{:row_index, _} = v, acc ->
maybe_remove_vertex(v, row_index, acc)
{:col_index, _} = v, acc ->
maybe_remove_vertex(v, col_index, acc)
end)
## Repeat if any reductions were made
if changed? do
maybe_reduce_domains(row_index, col_index, value, updated_graph)
else
updated_graph
end
)
end
defp maybe_remove_vertex(
{_signature, value} = vertex,
variable,
{graph, _changed?} = acc,
removal_condition \\ fn graph, vertex -> Graph.degree(graph, vertex) == 0 end
) do
cond do
!contains?(variable, value) ->
{remove_vertex(graph, vertex), true}
removal_condition.(graph, vertex) ->
remove(variable, value)
{remove_vertex(graph, vertex), true}
true ->
acc
end
end
defp remove_vertex(graph, {:value, _value} = vertex) do
Graph.delete_vertex(graph, vertex)
end
defp remove_vertex(graph, {signature, _value} = vertex)
when signature in [:row_index, :col_index] do
graph
|> Graph.delete_vertex(vertex)
## We delete all edges related to this vertex (that is, labelled {:signature, value})
|> then(fn graph ->
graph
|> Graph.edges()
|> Enum.reduce(
graph,
fn edge, acc ->
(edge.label == vertex && Graph.delete_edge(acc, edge.v1, edge.v2, edge.label)) ||
acc
end
)
end)
end
@impl true
def filter(args, state, changes) do
filter_impl(args, (state && state) || initial_state(args), changes)
end
def filter_impl(args, state, _changes) do
case filter_impl(args, state) do
:passive ->
:passive
updated_state ->
if Graph.vertices(updated_state) |> Enum.empty?() do
:fail
else
{:state, updated_state}
end
end
end
defp filter_impl([_array2d, row_index, col_index, value], state) do
maybe_reduce_domains(row_index, col_index, value, state)
end
defp maybe_fix(row_index, col_index, value, graph) do
## If any 2 are fixed, fix the 3rd
case Graph.vertices(graph) do
[_vertex1, _vertex2, _vertex3] = triple ->
Enum.each(
triple,
fn
{:row_index, x_value} -> fix(row_index, x_value)
{:col_index, y_value} -> fix(col_index, y_value)
{:value, z_value} -> fix(value, z_value)
end
)
true
_more_than_one_triple ->
false
end
end
end