python-constraint Allequal

Question

This question is about the python package constraint (see http://labix.org/python-constraint), in particular the built-in "AllEqualConstraint". In a problem involving 4 variables, I would like to enforce the first two and the second two to be equal, i.e.:

p = Problem()
p.addVariables([1,2,3,4], [0,1])
p.addConstraint(AllEqualConstraint(), [1,2])
p.addConstraint(AllEqualConstraint(), [3,4])

I only get two solutions:

for sol in p.getSolutions():
  print sol

> {1: 1, 2: 1, 3: 1, 4: 1}
> {1: 0, 2: 0, 3: 0, 4: 0}

where I would expect to see four, namely:

> {1: 1, 2: 1, 3: 1, 4: 1}
> {1: 1, 2: 1, 3: 0, 4: 0}
> {1: 0, 2: 0, 3: 1, 4: 1}
> {1: 0, 2: 0, 3: 0, 4: 0}

My question is: Can anyone confirm that this is what the package intends to compute and what the reasoning behind it is?

Ps: I have contacted the authors of this package, but got no reply yet. I know that this package is fairly well known and that there have been questions about it on StackOverflow before.

In answer to LVC: The constraint does not always apply the constraint to all variables:

p = Problem()
p.addVariables([1,2,3], [0,1])
p.addConstraint(AllEqualConstraint(), [1,2])

gives

> {1: 1, 2: 1, 3: 1}
> {1: 1, 2: 1, 3: 0}
> {1: 0, 2: 0, 3: 1}
> {1: 0, 2: 0, 3: 0}

as expected. If the AllEqualConstraint didn't respect variables, it would be very limited.

Answer 1

The module's source code contains this in how it enforeces AllEqualConstraint:

def __call__(self, variables, domains, assignments, forwardcheck=False,
             _unassigned=Unassigned):
    singlevalue = _unassigned
    for value in assignments.values():
        if singlevalue is _unassigned:
            singlevalue = value
        elif value != singlevalue:
            return False

The code that calls this in each Solver does this:

for constraint, variables in vconstraints[variable]:
    if not constraint(variables, domains, assignments,
                      pushdomains):
        # Value is not good.
        break

assignments contains all assignments for all variables, not just the variables affected by the constraint. This means that AllEqualConstraint doesn't care about the variables you put in addConstraint - it always tests that all the variables in the potential solution are equal, which is why you're missing the two solutions where that isn't the case.

The only time AllEqualConstraint looks at the variables argument is when it is called with forwardcheck being truthy. In that case, it does this:

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)

But none of the provided solvers appear to ever call a constraint with any forwardcheck value other than the default - which, in the case of AllEqualConstraint is False.

So, you will have to specify your own manual constraint - but this isn't too hard, since they can just be functions that take the appropriate number of variables (it gets wrapped in a FunctionConstraint, so you don't need to care about all the other stuff that gets passed to Constraint.__call__).

What you want as a Constraint, therefore, is a function that takes two variables, and returns whether they are equal. operator.eq fits the bill nicely:

p.addConstraint(operator.eq, [1, 2])
p.addConstraint(operator.eq, [3, 4])

Should give you the result you're looking for.

So scale this to more than two variables, you can write your own function:

def all_equal(a, b, c):
    return a == b == c

Or, more generally:

def all_equal(*vars):
    if not vars:
       return True
    return all(var == var[0] for var in vars)