"""Module containing the code for constraint definitions."""

from collections.abc import Callable, Sequence

from itertools import product

from constraint.domain import Unassigned

class Constraint:

"""Abstract base class for constraints."""

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False):

"""Perform the constraint checking.

If the forwardcheck parameter is not false, besides telling if

the constraint is currently broken or not, the constraint

implementation may choose to hide values from the domains of

unassigned variables to prevent them from being used, and thus

prune the search space.

Args:

variables (sequence): :py:class:`Variables` affected by that constraint,

in the same order provided by the user

domains (dict): Dictionary mapping variables to their

domains

assignments (dict): Dictionary mapping assigned variables to

their current assumed value

forwardcheck: Boolean value stating whether forward checking

should be performed or not

Returns:

bool: Boolean value stating if this constraint is currently

broken or not

"""

return True

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict):

"""Preprocess variable domains.

This method is called before starting to look for solutions,

and is used to prune domains with specific constraint logic

when possible. For instance, any constraints with a single

variable may be applied on all possible values and removed,

since they may act on individual values even without further

knowledge about other assignments.

Args:

variables (sequence): Variables affected by that constraint,

in the same order provided by the user

domains (dict): Dictionary mapping variables to their

domains

constraints (list): List of pairs of (constraint, variables)

vconstraints (dict): Dictionary mapping variables to a list

of constraints affecting the given variables.

"""

if len(variables) == 1:

variable = variables[0]

domain = domains[variable]

for value in domain[:]:

if not self(variables, domains, {variable: value}):

domain.remove(value)

constraints.remove((self, variables))

vconstraints[variable].remove((self, variables))

def forwardCheck(self, variables: Sequence, domains: dict, assignments: dict, _unassigned=Unassigned):

"""Helper method for generic forward checking.

Currently, this method acts only when there's a single

unassigned variable.

Args:

variables (sequence): Variables affected by that constraint,

in the same order provided by the user

domains (dict): Dictionary mapping variables to their

domains

assignments (dict): Dictionary mapping assigned variables to

their current assumed value

Returns:

bool: Boolean value stating if this constraint is currently

broken or not

"""

unassignedvariable = _unassigned

for variable in variables:

if variable not in assignments:

if unassignedvariable is _unassigned:

unassignedvariable = variable

else:

break

else:

if unassignedvariable is not _unassigned:

# Remove from the unassigned variable domain's all

# values which break our variable's constraints.

domain = domains[unassignedvariable]

if domain:

for value in domain[:]:

assignments[unassignedvariable] = value

if not self(variables, domains, assignments):

domain.hideValue(value)

del assignments[unassignedvariable]

if not domain:

return False

return True

class FunctionConstraint(Constraint):

"""Constraint which wraps a function defining the constraint logic.

Examples:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> def func(a, b):

... return b > a

>>> problem.addConstraint(func, ["a", "b"])

>>> problem.getSolution()

{'a': 1, 'b': 2}

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> def func(a, b):

... return b > a

>>> problem.addConstraint(FunctionConstraint(func), ["a", "b"])

>>> problem.getSolution()

{'a': 1, 'b': 2}

>>> problem = Problem()

>>> problem.addVariables([1, 2], ["a", "b"])

>>> def func(x, y):

... return x != y

>>> problem.addConstraint(FunctionConstraint(func), [1, 2])

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[(1, 'a'), (2, 'b')], [(1, 'b'), (2, 'a')]]

"""

def __init__(self, func: Callable, assigned: bool = True):

"""Initialization method.

Args:

func (callable object): Function wrapped and queried for

constraint logic

assigned (bool): Whether the function may receive unassigned

variables or not

"""

self._func = func

self._assigned = assigned

def __call__( # noqa: D102

self,

variables: Sequence,

domains: dict,

assignments: dict,

forwardcheck=False,

_unassigned=Unassigned,

):

# # initial code: 0.94621 seconds, Cythonized: 0.92805 seconds

# parms = [assignments.get(x, _unassigned) for x in variables]

# missing = parms.count(_unassigned)

# # list comprehension and sum: 0.13744 seconds, Cythonized: 0.10059 seconds

# parms = [assignments.get(x, _unassigned) for x in variables]

# missing = sum(x not in assignments for x in variables)

# # sum check with fallback: , Cythonized: 0.10108 seconds

# missing = sum(x not in assignments for x in variables)

# parms = [assignments.get(x, _unassigned) for x in variables] if missing > 0 else [assignments[x] for x in var]

# # tuple list comprehension with unzipping: 0.14521 seconds, Cythonized: 0.12054 seconds

# lst = [(assignments[x], 0) if x in assignments else (_unassigned, 1) for x in variables]

# parms, missing_iter = zip(*lst)

# parms = list(parms)

# missing = sum(missing_iter)

# # single loop array: 0.11249 seconds, Cythonized: 0.09514 seconds

# parms = [None] * len(variables)

# missing = 0

# for i, x in enumerate(variables):

# if x in assignments:

# parms[i] = assignments[x]

# else:

# parms[i] = _unassigned

# missing += 1

# single loop list: 0.11462 seconds, Cythonized: 0.08686 seconds

parms = list()

missing = 0

for x in variables:

if x in assignments:

parms.append(assignments[x])

else:

parms.append(_unassigned)

missing += 1

# if there are unassigned variables, do a forward check before executing the restriction function

if missing > 0:

return (self._assigned or self._func(*parms)) and (

not forwardcheck or missing != 1 or self.forwardCheck(variables, domains, assignments)

)

return self._func(*parms)

class CompilableFunctionConstraint(Constraint):

"""Wrapper function for picklable string constraints that must be compiled into a FunctionConstraint later on."""

def __init__(self, func: str, assigned: bool = True): # noqa: D102, D107

self._func = func

self._assigned = assigned

def __call__(self, variables, domains, assignments, forwardcheck=False, _unassigned=Unassigned): # noqa: D102

raise NotImplementedError("CompilableFunctionConstraint can not be called directly")

class AllDifferentConstraint(Constraint):

"""Constraint enforcing that values of all given variables are different.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(AllDifferentConstraint())

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

"""

def __call__( # noqa: D102

self,

variables: Sequence,

domains: dict,

assignments: dict,

forwardcheck=False,

_unassigned=Unassigned,

):

seen = {}

for variable in variables:

value = assignments.get(variable, _unassigned)

if value is not _unassigned:

if value in seen:

return False

seen[value] = True

if forwardcheck:

for variable in variables:

if variable not in assignments:

domain = domains[variable]

for value in seen:

if value in domain:

domain.hideValue(value)

if not domain:

return False

return True

class AllEqualConstraint(Constraint):

"""Constraint enforcing that values of all given variables are equal.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(AllEqualConstraint())

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1)], [('a', 2), ('b', 2)]]

"""

def __call__( # noqa: D102

self,

variables: Sequence,

domains: dict,

assignments: dict,

forwardcheck=False,

_unassigned=Unassigned,

):

singlevalue = _unassigned

for variable in variables:

value = assignments.get(variable, _unassigned)

if singlevalue is _unassigned:

singlevalue = value

elif value is not _unassigned and value != singlevalue:

return False

if forwardcheck and singlevalue is not _unassigned:

for variable in variables:

if variable not in assignments:

domain = domains[variable]

if singlevalue not in domain:

return False

for value in domain[:]:

if value != singlevalue:

domain.hideValue(value)

return True

class ExactSumConstraint(Constraint):

"""Constraint enforcing that values of given variables sum exactly to a given amount.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(ExactSumConstraint(3))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-1, 0, 1])

>>> problem.addConstraint(ExactSumConstraint(0))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -1), ('b', 1)], [('a', 0), ('b', 0)], [('a', 1), ('b', -1)]]

"""

def __init__(self, exactsum: int | float, multipliers: Sequence | None = None):

"""Initialization method.

Args:

exactsum (number): Value to be considered as the exact sum

multipliers (sequence of numbers): If given, variable values

will be multiplied by the given factors before being

summed to be checked

"""

self._exactsum = exactsum

self._multipliers = multipliers

self._var_max = {}

self._var_min = {}

self._var_is_negative = {}

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers if self._multipliers else [1] * len(variables)

exactsum = self._exactsum

self._var_min = { variable: min(domains[variable]) * multiplier for variable, multiplier in zip(variables, multipliers) } # noqa: E501

self._var_max = { variable: max(domains[variable]) * multiplier for variable, multiplier in zip(variables, multipliers) } # noqa: E501

# preprocess the domains to remove values that cannot contribute to the exact sum

for variable, multiplier in zip(variables, multipliers):

domain = domains[variable]

other_vars_min = sum_other_vars(variables, variable, self._var_min)

other_vars_max = sum_other_vars(variables, variable, self._var_max)

for value in domain[:]:

if value * multiplier + other_vars_min > exactsum:

domain.remove(value)

if value * multiplier + other_vars_max < exactsum:

domain.remove(value)

# recalculate the min and max after pruning

self._var_max = { variable: max(domains[variable]) * multiplier if len(domains[variable]) > 0 else 0 for variable, multiplier in zip(variables, multipliers) } # noqa: E501

self._var_min = { variable: min(domains[variable]) * multiplier if len(domains[variable]) > 0 else 0 for variable, multiplier in zip(variables, multipliers) } # noqa: E501

self._var_is_negative = { variable: self._var_min[variable] < 0 for variable in variables }

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

exactsum = self._exactsum

sum = 0

min_sum_missing = 0

max_sum_missing = 0

missing = False

missing_negative = False

if multipliers:

for variable, multiplier in zip(variables, multipliers):

if variable in assignments:

sum += assignments[variable] * multiplier

else:

min_sum_missing += self._var_min[variable]

max_sum_missing += self._var_max[variable]

missing = True

if self._var_is_negative[variable]:

missing_negative = True

if isinstance(sum, float):

sum = round(sum, 10)

if sum + min_sum_missing > exactsum or sum + max_sum_missing < exactsum:

return False

if forwardcheck and missing and not missing_negative:

for variable, multiplier in zip(variables, multipliers):

if variable not in assignments:

domain = domains[variable]

for value in domain[:]:

if sum + value * multiplier > exactsum:

domain.hideValue(value)

if not domain:

return False

else:

for variable in variables:

if variable in assignments:

sum += assignments[variable]

else:

min_sum_missing += self._var_min[variable]

max_sum_missing += self._var_max[variable]

missing = True

if self._var_is_negative[variable]:

missing_negative = True

if isinstance(sum, float):

sum = round(sum, 10)

if sum + min_sum_missing > exactsum or sum + max_sum_missing < exactsum:

return False

if forwardcheck and missing and not missing_negative:

for variable in variables:

if variable not in assignments:

domain = domains[variable]

for value in domain[:]:

if sum + value > exactsum:

domain.hideValue(value)

if not domain:

return False

if missing:

return sum + min_sum_missing <= exactsum and sum + max_sum_missing >= exactsum

else:

return sum == exactsum

class VariableExactSumConstraint(Constraint):

"""Constraint enforcing that the sum of variables equals the value of another variable.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b", "c"], [1, 2, 3])

>>> problem.addConstraint(VariableExactSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1), ('c', 2)], [('a', 1), ('b', 2), ('c', 3)], [('a', 2), ('b', 1), ('c', 3)]]

>>> problem = Problem()

>>> problem.addVariable('a', [-1,0,1])

>>> problem.addVariable('b', [-1,0,1])

>>> problem.addVariable('c', [0, 2])

>>> problem.addConstraint(VariableExactSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -1), ('b', 1), ('c', 0)], [('a', 0), ('b', 0), ('c', 0)], [('a', 1), ('b', -1), ('c', 0)], [('a', 1), ('b', 1), ('c', 2)]]

""" # noqa: E501

def __init__(self, target_var: str, sum_vars: Sequence[str], multipliers: Sequence | None = None):

"""Initialization method.

Args:

target_var (Variable): The target variable to sum to.

sum_vars (sequence of Variables): The variables to sum up.

multipliers (sequence of numbers): If given, variable values

(except the last) will be multiplied by the given factors before being

summed to match the last variable.

"""

self.target_var = target_var

self.sum_vars = sum_vars

self._multipliers = multipliers

if multipliers:

assert len(multipliers) == len(sum_vars) + 1, "Multipliers must match sum variables and +1 for target."

assert all(isinstance(m, (int, float)) for m in multipliers), "Multipliers must be numbers."

assert multipliers[-1] == 1, "Last multiplier must be 1, as it is the target variable."

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers

if multipliers:

for var, multiplier in zip(self.sum_vars, multipliers):

domain = domains[var]

for value in domain[:]:

if value * multiplier > max(domains[self.target_var]):

domain.remove(value)

else:

for var in self.sum_vars:

domain = domains[var]

others_min = sum(min(domains[v]) for v in self.sum_vars if v != var)

others_max = sum(max(domains[v]) for v in self.sum_vars if v != var)

for value in domain[:]:

if value + others_min > max(domains[self.target_var]):

domain.remove(value)

if value + others_max < min(domains[self.target_var]):

domain.remove(value)

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

if self.target_var not in assignments:

return True # can't evaluate without target, defer to later

target_value = assignments[self.target_var]

sum_value = 0

missing = False

if multipliers:

for var, multiplier in zip(self.sum_vars, multipliers):

if var in assignments:

sum_value += assignments[var] * multiplier

else:

missing = True

else:

for var in self.sum_vars:

if var in assignments:

sum_value += assignments[var]

else:

sum_value += min(domains[var]) # use min value if not assigned

missing = True

if isinstance(sum_value, float):

sum_value = round(sum_value, 10)

if missing:

# Partial assignments: only check feasibility

if sum_value > target_value:

return False

if forwardcheck:

for var in self.sum_vars:

if var not in assignments:

domain = domains[var]

if multipliers:

for value in domain[:]:

temp_sum = sum_value + (value * multipliers[self.sum_vars.index(var)])

if temp_sum > target_value:

domain.hideValue(value)

else:

temp_sum = sum_value - min(domain) # sum_value already includes min for unassigned vars

for value in domain[:]:

if temp_sum + value > target_value:

domain.hideValue(value)

if not domain:

return False

return True

else:

return sum_value == target_value

class MinSumConstraint(Constraint):

"""Constraint enforcing that values of given variables sum at least to a given amount.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(MinSumConstraint(3))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)], [('a', 2), ('b', 2)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-3, 1])

>>> problem.addConstraint(MinSumConstraint(-2))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -3), ('b', 1)], [('a', 1), ('b', -3)], [('a', 1), ('b', 1)]]

"""

def __init__(self, minsum: int | float, multipliers: Sequence | None = None):

"""Initialization method.

Args:

minsum (number): Value to be considered as the minimum sum

multipliers (sequence of numbers): If given, variable values

will be multiplied by the given factors before being

summed to be checked

"""

self._minsum = minsum

self._multipliers = multipliers

self._var_max = {}

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers if self._multipliers else [1] * len(variables)

self._var_max = { variable: max(domains[variable]) * multiplier for variable, multiplier in zip(variables, multipliers) } # noqa: E501

# preprocess the domains to remove values that cannot contribute to the minimum sum

for variable, multiplier in zip(variables, multipliers):

domain = domains[variable]

others_max = sum_other_vars(variables, variable, self._var_max)

for value in domain[:]:

if value * multiplier + others_max < self._minsum:

domain.remove(value)

# recalculate the max after pruning

self._var_max = { variable: max(domains[variable]) * multiplier if len(domains[variable]) > 0 else 0 for variable, multiplier in zip(variables, multipliers) } # noqa: E501

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

minsum = self._minsum

sum = 0

missing = False

max_sum_missing = 0

if multipliers:

for variable, multiplier in zip(variables, multipliers):

if variable in assignments:

sum += assignments[variable] * multiplier

else:

max_sum_missing += self._var_max[variable]

missing = True

else:

for variable in variables:

if variable in assignments:

sum += assignments[variable]

else:

max_sum_missing += self._var_max[variable]

missing = True

if isinstance(sum, float):

sum = round(sum, 10)

if sum + max_sum_missing < minsum:

return False

return sum >= minsum or missing

class VariableMinSumConstraint(Constraint):

"""Constraint enforcing that the sum of variables sum at least to the value of another variable.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b", "c"], [1, 4])

>>> problem.addConstraint(VariableMinSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1), ('c', 1)], [('a', 1), ('b', 4), ('c', 1)], [('a', 1), ('b', 4), ('c', 4)], [('a', 4), ('b', 1), ('c', 1)], [('a', 4), ('b', 1), ('c', 4)], [('a', 4), ('b', 4), ('c', 1)], [('a', 4), ('b', 4), ('c', 4)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-3, 1])

>>> problem.addVariable('c', [-2, 2])

>>> problem.addConstraint(VariableMinSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -3), ('b', 1), ('c', -2)], [('a', 1), ('b', -3), ('c', -2)], [('a', 1), ('b', 1), ('c', -2)], [('a', 1), ('b', 1), ('c', 2)]]

""" # noqa: E501

def __init__(self, target_var: str, sum_vars: Sequence[str], multipliers: Sequence | None = None):

"""Initialization method.

Args:

target_var (Variable): The target variable to sum to.

sum_vars (sequence of Variables): The variables to sum up.

multipliers (sequence of numbers): If given, variable values

(except the last) will be multiplied by the given factors before being

summed to match the last variable.

"""

self.target_var = target_var

self.sum_vars = sum_vars

self._multipliers = multipliers

if multipliers:

assert len(multipliers) == len(sum_vars) + 1, "Multipliers must match sum variables and +1 for target."

assert all(isinstance(m, (int, float)) for m in multipliers), "Multipliers must be numbers."

assert multipliers[-1] == 1, "Last multiplier must be 1, as it is the target variable."

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers

if not multipliers:

for var in self.sum_vars:

domain = domains[var]

others_max = sum(max(domains[v]) for v in self.sum_vars if v != var)

for value in domain[:]:

if value + others_max < min(domains[self.target_var]):

domain.remove(value)

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

if self.target_var not in assignments:

return True # can't evaluate without target, defer to later

target_value = assignments[self.target_var]

sum_value = 0

if multipliers:

for var, multiplier in zip(self.sum_vars, multipliers):

if var in assignments:

sum_value += assignments[var] * multiplier

else:

sum_value += max(domains[var] * multiplier) # use max value if not assigned

else:

for var in self.sum_vars:

if var in assignments:

sum_value += assignments[var]

else:

sum_value += max(domains[var]) # use max value if not assigned

if isinstance(sum_value, float):

sum_value = round(sum_value, 10)

return sum_value >= target_value

class MaxSumConstraint(Constraint):

"""Constraint enforcing that values of given variables sum up to a given amount.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(MaxSumConstraint(3))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1)], [('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-3, 1])

>>> problem.addConstraint(MaxSumConstraint(-2))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -3), ('b', -3)], [('a', -3), ('b', 1)], [('a', 1), ('b', -3)]]

"""

def __init__(self, maxsum: int | float, multipliers: Sequence | None = None):

"""Initialization method.

Args:

maxsum (number): Value to be considered as the maximum sum

multipliers (sequence of numbers): If given, variable values

will be multiplied by the given factors before being

summed to be checked

"""

self._maxsum = maxsum

self._multipliers = multipliers

self._var_min = {}

self._var_is_negative = {}

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers if self._multipliers else [1] * len(variables)

maxsum = self._maxsum

self._var_min = { variable: min(domains[variable]) * multiplier for variable, multiplier in zip(variables, multipliers) } # noqa: E501

# preprocess the domains to remove values that cannot contribute to the sum

for variable, multiplier in zip(variables, multipliers):

domain = domains[variable]

other_vars_min = sum_other_vars(variables, variable, self._var_min)

for value in domain[:]:

if value * multiplier + other_vars_min > maxsum:

domain.remove(value)

# recalculate the min after pruning

self._var_min = { variable: min(domains[variable]) * multiplier if len(domains[variable]) > 0 else 0 for variable, multiplier in zip(variables, multipliers) } # noqa: E501

self._var_is_negative = { variable: self._var_min[variable] < 0 for variable in variables }

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

maxsum = self._maxsum

sum = 0

min_sum_missing = 0

missing = False

missing_negative = False

if multipliers:

for variable, multiplier in zip(variables, multipliers):

if variable in assignments:

sum += assignments[variable] * multiplier

else:

min_sum_missing += self._var_min[variable]

missing = True

if self._var_is_negative[variable]:

missing_negative = True

if isinstance(sum, float):

sum = round(sum, 10)

if sum + min_sum_missing > maxsum:

return False

if forwardcheck and missing and not missing_negative:

for variable, multiplier in zip(variables, multipliers):

if variable not in assignments:

domain = domains[variable]

for value in domain[:]:

if sum + value * multiplier > maxsum:

domain.hideValue(value)

if not domain:

return False

else:

for variable in variables:

if variable in assignments:

sum += assignments[variable]

else:

min_sum_missing += self._var_min[variable]

missing = True

if self._var_is_negative[variable]:

missing_negative = True

if isinstance(sum, float):

sum = round(sum, 10)

if sum + min_sum_missing > maxsum:

return False

if forwardcheck and missing and not missing_negative:

for variable in variables:

if variable not in assignments:

domain = domains[variable]

for value in domain[:]:

if sum + value > maxsum:

domain.hideValue(value)

if not domain:

return False

return True

class VariableMaxSumConstraint(Constraint):

"""Constraint enforcing that the sum of variables sum at most to the value of another variable.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b", "c"], [1, 3, 4])

>>> problem.addConstraint(VariableMaxSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1), ('c', 3)], [('a', 1), ('b', 1), ('c', 4)], [('a', 1), ('b', 3), ('c', 4)], [('a', 3), ('b', 1), ('c', 4)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-2, 1])

>>> problem.addVariable('c', [-3, -1])

>>> problem.addConstraint(VariableMaxSumConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -2), ('b', -2), ('c', -3)], [('a', -2), ('b', -2), ('c', -1)], [('a', -2), ('b', 1), ('c', -1)], [('a', 1), ('b', -2), ('c', -1)]]

""" # noqa: E501

def __init__(self, target_var: str, sum_vars: Sequence[str], multipliers: Sequence | None = None):

"""Initialization method.

Args:

target_var (Variable): The target variable to sum to.

sum_vars (sequence of Variables): The variables to sum up.

multipliers (sequence of numbers): If given, variable values

(except the last) will be multiplied by the given factors before being

summed to match the last variable.

"""

self.target_var = target_var

self.sum_vars = sum_vars

self._multipliers = multipliers

if multipliers:

assert len(multipliers) == len(sum_vars) + 1, "Multipliers must match sum variables and +1 for target."

assert all(isinstance(m, (int, float)) for m in multipliers), "Multipliers must be numbers."

assert multipliers[-1] == 1, "Last multiplier must be 1, as it is the target variable."

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

multipliers = self._multipliers

if not multipliers:

for var in self.sum_vars:

domain = domains[var]

others_min = sum(min(domains[v]) for v in self.sum_vars if v != var)

for value in domain[:]:

if value + others_min > max(domains[self.target_var]):

domain.remove(value)

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

multipliers = self._multipliers

if self.target_var not in assignments:

return True # can't evaluate without target, defer to later

target_value = assignments[self.target_var]

sum_value = 0

if multipliers:

for var, multiplier in zip(self.sum_vars, multipliers):

if var in assignments:

sum_value += assignments[var] * multiplier

else:

sum_value += min(domains[var] * multiplier) # use min value if not assigned

else:

for var in self.sum_vars:

if var in assignments:

sum_value += assignments[var]

else:

sum_value += min(domains[var]) # use min value if not assigned

if isinstance(sum_value, float):

sum_value = round(sum_value, 10)

return sum_value <= target_value

class ExactProdConstraint(Constraint):

"""Constraint enforcing that values of given variables create a product of exactly a given amount.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [1, 2])

>>> problem.addConstraint(ExactProdConstraint(2))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-2, -1, 1, 2])

>>> problem.addConstraint(ExactProdConstraint(-2))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -2), ('b', 1)], [('a', -1), ('b', 2)], [('a', 1), ('b', -2)], [('a', 2), ('b', -1)]]

"""

def __init__(self, exactprod: int | float):

"""Instantiate an ExactProdConstraint.

Args:

exactprod: Value to be considered as the product

"""

self._exactprod = exactprod

self._variable_contains_lt1: list[bool] = list()

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

# check if there are any values less than 1 in the associated variables

self._variable_contains_lt1: list[bool] = list()

variable_with_lt1 = None

for variable in variables:

contains_lt1 = any(value < 1 for value in domains[variable])

self._variable_contains_lt1.append(contains_lt1)

for variable, contains_lt1 in zip(variables, self._variable_contains_lt1):

if contains_lt1 is True:

if variable_with_lt1 is not None:

# if more than one associated variables contain less than 1, we can't prune

return

variable_with_lt1 = variable

# prune the associated variables of values > exactprod

exactprod = self._exactprod

for variable in variables:

if variable_with_lt1 is not None and variable_with_lt1 != variable:

continue

domain = domains[variable]

for value in domain[:]:

if value > exactprod:

domain.remove(value)

elif value == 0 and exactprod != 0:

domain.remove(value)

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

exactprod = self._exactprod

prod = 1

missing = False

missing_lt1 = []

# find out which variables contain values less than 1 if not preprocessed

if len(self._variable_contains_lt1) != len(variables):

for variable in variables:

self._variable_contains_lt1.append(any(value < 1 for value in domains[variable]))

for variable, contains_lt1 in zip(variables, self._variable_contains_lt1):

if variable in assignments:

prod *= assignments[variable]

else:

missing = True

if contains_lt1:

missing_lt1.append(variable)

if isinstance(prod, float):

prod = round(prod, 10)

if (not missing and prod != exactprod) or (len(missing_lt1) == 0 and prod > exactprod):

return False

if forwardcheck:

for variable in variables:

if variable not in assignments and (variable not in missing_lt1 or len(missing_lt1) == 1):

domain = domains[variable]

for value in domain[:]:

if prod * value > exactprod:

domain.hideValue(value)

if not domain:

return False

return True

class VariableExactProdConstraint(Constraint):

"""Constraint enforcing that the product of variables equals the value of another variable.

Example:

>>> problem = Problem()

>>> problem.addVariables(["a", "b", "c"], [1, 2])

>>> problem.addConstraint(VariableExactProdConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', 1), ('b', 1), ('c', 1)], [('a', 1), ('b', 2), ('c', 2)], [('a', 2), ('b', 1), ('c', 2)]]

>>> problem = Problem()

>>> problem.addVariables(["a", "b"], [-2, -1, 2])

>>> problem.addVariable('c', [-2, 1])

>>> problem.addConstraint(VariableExactProdConstraint('c', ['a', 'b']))

>>> sorted(sorted(x.items()) for x in problem.getSolutions())

[[('a', -1), ('b', -1), ('c', 1)], [('a', -1), ('b', 2), ('c', -2)], [('a', 2), ('b', -1), ('c', -2)]]

"""

def __init__(self, target_var: str, product_vars: Sequence[str]):

"""Instantiate a VariableExactProdConstraint.

Args:

target_var (Variable): The target variable to match.

product_vars (sequence of Variables): The variables to calculate the product of.

"""

self.target_var = target_var

self.product_vars = product_vars

def _get_product_bounds(self, domain_dict, exclude_var=None):

"""Return min and max product of domains of product_vars (excluding `exclude_var` if given)."""

bounds = []

for var in self.product_vars:

if var == exclude_var:

continue

dom = domain_dict[var]

if not dom:

continue

bounds.append((min(dom), max(dom)))

all_bounds = [b for b in bounds]

if not all_bounds:

return 1, 1

# Get all combinations of min/max to find global min/max product

candidates = [b for b in product(*[(lo, hi) for lo, hi in all_bounds])]

products = [self._safe_product(p) for p in candidates]

return min(products), max(products)

def _safe_product(self, values):

prod = 1

for v in values:

prod *= v

return prod

def preProcess(self, variables: Sequence, domains: dict, constraints: list[tuple], vconstraints: dict): # noqa: D102

Constraint.preProcess(self, variables, domains, constraints, vconstraints)

target_domain = domains[self.target_var]

target_min = min(target_domain)

target_max = max(target_domain)

for var in self.product_vars:

other_min, other_max = self._get_product_bounds(domains, exclude_var=var)

domain = domains[var]

for value in domain[:]:

candidates = [value * other_min, value * other_max]

minval, maxval = min(candidates), max(candidates)

if maxval < target_min or minval > target_max:

domain.remove(value)

def __call__(self, variables: Sequence, domains: dict, assignments: dict, forwardcheck=False): # noqa: D102

if self.target_var not in assignments:

return True

target_value = assignments[self.target_var]

assigned_product = 1

unassigned_vars = []

for var in self.product_vars:

if var in assignments:

assigned_product *= assignments[var]