Skip to content

Fix VariableExactSumConstraint forwardcheck incorrectly pruning valid domain values - #108

Closed
gaoflow wants to merge 2 commits into
python-constraint:mainfrom
gaoflow:fix/variable-exact-sum-forwardcheck
Closed

Fix VariableExactSumConstraint forwardcheck incorrectly pruning valid domain values#108
gaoflow wants to merge 2 commits into
python-constraint:mainfrom
gaoflow:fix/variable-exact-sum-forwardcheck

Conversation

@gaoflow

@gaoflow gaoflow commented Jun 25, 2026

Copy link
Copy Markdown

Summary

VariableExactSumConstraint.__call__ (no-multipliers path) builds
sum_value by accumulating assigned variable values plus
min(domain) as a placeholder for each unassigned variable. In the
forward-check loop it then computed:

temp_sum = sum_value + value

This double-counts the placeholder for the variable whose domain is
being pruned, making temp_sum too large and hiding valid values.

Minimal reproducer (returns [] instead of [{a:1,b:2,c:3}, {a:2,b:1,c:3}]):

from constraint import Problem, VariableExactSumConstraint
problem = Problem()
problem.addVariable("a", [1, 2])
problem.addVariable("b", [1, 2])
problem.addVariable("c", [3])
problem.addConstraint(VariableExactSumConstraint("c", ["a", "b"]))
print(problem.getSolutions())   # [] — wrong

With a=1 assigned and c=3 assigned, sum_value is 1 + min([1,2]) = 2.
The check 2 + 2 = 4 > 3 then hides b=2, even though a + b = 1 + 2 = 3
satisfies the constraint.

Fix

Subtract the placeholder for the variable being checked before adding the
candidate value:

var_placeholder = min(domain)
for value in domain[:]:
    temp_sum = sum_value - var_placeholder + value
    if temp_sum > target_value:
        domain.hideValue(value)

The multipliers branch was not affected because it never adds a
placeholder (it only tracks missing = True without modifying sum_value).

Tests

All 34 existing constraint/solver tests continue to pass. The note
about test_if_compiled failing when .so files are absent is a
pre-existing CI condition unrelated to this fix.


This pull request was prepared with the assistance of AI, under my direction and review.

…d variable

In the no-multipliers branch of __call__, `sum_value` includes
`min(domain)` as a placeholder for each unassigned variable.  The
forward-check loop then computed `temp_sum = sum_value + value`,
inadvertently double-counting the placeholder for the variable under
scrutiny and pruning valid domain values too aggressively.

Example: with a=[1,2], b=[1,2], c=[3] and a=1 already assigned,
`sum_value` was 2 (1 from a plus min(b)=1 as placeholder).
The forward-check then computed temp_sum = 2 + 2 = 4 > 3 and
incorrectly hid b=2, making a+b=3 unreachable.

Fix: subtract the placeholder for the variable being checked before
adding the candidate value, so only the contribution from *other*
unassigned variables is retained:

    var_placeholder = min(domain)
    temp_sum = sum_value - var_placeholder + value

This mirrors the intent of the multipliers branch, which never added a
placeholder and was therefore unaffected.
@gaoflow

gaoflow commented Jun 25, 2026

Copy link
Copy Markdown
Author

CI triage note: the current red build job appears unrelated to this PR change. The failure happens before project tests run, while installing Poetry for the tests-3.9 nox session:

error: the configured PyPy interpreter version (3.9) is lower than PyO3's minimum supported version (3.11)
ERROR: Failed building wheel for cryptography

lint passed earlier in the same job, and the failure is from the dependency chain pulled during python -m pip install poetry on PyPy 3.9, not from the VariableExactSumConstraint code path.

@coveralls

Copy link
Copy Markdown

Coverage Status

coverage: 83.291% (+0.01%) from 83.28% — gaoflow:fix/variable-exact-sum-forwardcheck into python-constraint:main

@fjwillemsen

Copy link
Copy Markdown
Member

@gaoflow thank you for submitting this PR! I've checked it and wanted to make some improvements which I couldn't do on your fork, but I've included this fix and a test to prevent it in the future in the just-released 2.6.0. Thank you for your contribution!

@gaoflow

gaoflow commented Jun 29, 2026

Copy link
Copy Markdown
Author

Thanks @fjwillemsen — glad it made it into 2.6.0, and nice call adding the regression test. Appreciate the quick turnaround!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants