CSP backtrack inference problem
Closed this issue · 3 comments
When using inference, some times backtrack doesn't find a solution, even when there is a solution.
Check the stars problem.
What is the stars problem?
The "stars problem" was an example of csp we gave at the university.
Today we solved the issue, working with @ganiserb.
There were two issues, but we also did a big refactor to simplify the code. The original issues were:
- The algorithms assumed that the constraints are symetrical, but that isn't true for most problems. Anything different than (A = B) or (A != B), is not symetrical. Examples: (A > B), (A = B^2), (A = B + 10), ... So in most problems, ac3 removed a lot of correct values from the domains, leaving them empty. For example, for (A > B) with domains A=[3, 4], B=[1, 2], ac3 removed all the values from both domains, because it tried to satisfy (A > B) and (B > A), which isn't possible with any combination.
The arcs should be checked in both directions in ac3, that is correct. But always honoring the order of the neighbors defined on the constraint when calling it, we can't call the constraint inverting the order of the variables. There is a distinction between the direction of the arc check, and the order of the parameters passed to the constraint, they don't have to be the same. For example, when doing arc consistency from B to A, if the constraint was (A > B), for each B value check that there is a value from A that satisfies (A > B), it's wrong to try to satisfy (B > A) just because you are doing arc consistency from B to A. The constraint is still (A > B), no matter in which direction you are checking the consistency.
A lot of code was written just to be able to call the constraints in both orders, so fixing the issue was mostly simplifying all that code :)
- Not all the arcs were being created by the all_arcs function: if constraints had (A, B, consX), (A, B, consY), then just (A, B, consX) and (B, A, consX) were added, but no (A, B, consY) and (B, A, consY), so some constraints weren't checked. The refactor changed the structure, now we don't need the functions on the arcs, just the variables (then each arc is verified against all the constraints that contain the arc variables).
Release 0.7.9 includes this fix and refactor :)
Nice, thanks for the reply. I actually wanted to debug it myself. But there you go :-)