Help with backtracking with CLPFD

[emiruz]

I’ve a small code snippet below. The findit/4 predicate maps a seed ID with a location ID by zig-zagging through some connected categories. Seeds range from 55-67 and from 78-92. You can call it for any seed and it will give you its location: findit(59,Loc). You can call it for any location and it will give you its seed: findit(Seed,61).

THE PROBLEM: I want to enumerate all seeds and locations, I expect to be able to do this: findit(Seed,Loc),label([Seed,Loc]), but for some reason it skips seeds in the range 59-67. Another way to see that is to note this output:

?- findit(Seed,Loc).
Seed in 79..92, <-- OK
2+Seed#=Loc,
Loc in 81..94 ;
Seed in 55..58, <-- WHY NO 59-67?
2+Seed#=_A,
_A in 57..60,
-4+_A#=Loc,
Loc in 53..56.

?- ?- Seed in 59..70, findit(Seed,Loc).
Seed in 59..67, <-- APPEARS WHEN I FORCE DOMAIN OF Seed.
2+Seed#=Loc,
Loc in 61..69.

Here is the code. Any help would be appreciated.

:- use_module(library(clpfd)).

% Data.

c(79-79-14,none,seed).
c(55-55-13,none,seed).
c(50-98-2,seed,soil).
c(52-50-48,seed,soil).
c(0-15-37,soil,fertilizer).
c(37-52-2,soil,fertilizer).
c(39-0-15,soil,fertilizer).
c(49-53-8,fertilizer,location).
c(0-11-42,fertilizer,location).
c(42-0-7,fertilizer,location).
c(57-7-4,fertilizer,location).

findit(location,Src,Src,_) :- !.
findit(Fr,Src,Loc,Seed) :-
    c(D-S-L,Fr,To),
    Src#>=S,S+L-1#>=Src,
    SrcNew #= Src+D-S,
    findit(To,SrcNew,Loc,Seed),!.
findit(Fr,Src,Loc,Seed) :-
    c(_,Fr,To),
    findit(To,Src,Loc,Seed).
findit(Seed,Loc) :-
    c(_-S-L,none,To),
    Seed #>= S, S+L-1 #>= Seed,
    findit(To,Seed,Loc,Seed).

[emiruz]

@jan Is it the case that when CLPFD constrains a domain, there is no backtracking to a less constrained domain? I added some print statements to output fd_dom:

?- findit(Seed,Loc).
[a,79..92]
[b,seed,79..92]
[c,soil,79..92]
[c,fertilizer,79..92]
Seed in 79..92,
2+Seed#=Loc,
Loc in 81..94 ;
[a,55..67] <-- ALL GOOD HERE!
[b,seed,55..67]
[c,soil,55..67]
[b,fertilizer,55..58] <-- CONSTRAINED, AND DOESN'T BACKTRACK.
Seed in 55..58,
2+Seed#=_A,
_A in 57..60,
-4+_A#=Loc,
Loc in 53..56 ;
false.

Here is a version of find/4 used above with no cuts, but guards instead:

findit(location,Src,Src,_).
findit(Fr,Src,Loc,Seed) :-
    c(D-S-L,Fr,To),
    Src#>=S,S+L-1#>=Src,
    SrcNew #= Src+D-S,
    findit(To,SrcNew,Loc,Seed).
findit(Fr,Src,Loc,Seed) :-
    forall(c(_-S-L,Fr,_),(S#>Src;Src#>S+L-1)),
    c(_,Fr,To),
    findit(To,Src,Loc,Seed),!.
findit(Seed,Loc) :-
    c(_-S-L,none,To),
    Seed #>= S, S+L-1 #>= Seed,
    findit(To,Seed,Loc,Seed).

[jan]

@emiruz

forall(c(_-S-L,Fr,_),(S#>Src;Src#>S+L-1))

This might be your problem. forall/2 is defined as \+ (Generator, \+ Test), so it cuts. If you use constraints, there is a lot of stuff you should stop using, e.g., findall/3 and friends, !, ->, + ==/2, and all the other not pure logical stuff.

foreach/2 is more constraint friendly, although not entirely without problems. Some debate on the current implementation is in this forum somewhere. The old one was based on findall/3, which comes with its own problems.

[ridgeworks]

Just looking at your first attempt.

The logic behind findit/4 confuses me. Skipping the first clause (the terminating case), the second clause picks a c/3 (from multiple choices), then applies its constraints. If that succeeds, it moves on (recursively) to find the rest of the solution. If it finds such a solution it cuts (commits) to that solution, so any remaining choices due to c/3 are removed. I suspect that’s the reason you lose some solutions.

Now the reason for your cut seems to be to remove the effect of the third clause. This clause just generates solutions without applying any constraints. So without the cut it should just duplicate solutions generated by clause 2, among others (those that don’t satisfy the constraints). So I’m not sure what the intent is of that third clause.

Normally when looking at backtracking causing unexpected results I’d suggest using one of the debuggers to actually see what’s happening (often very educational). But debugging clpfd seems problematical for a couple of reasons:

1. clpfd performs significant goal expansion which means the code you end up debugging doesn’t look much like your source, which is very confusing. Maybe there’s a way of working around this but I haven’t used enough clpfd to know what it is.
2. clpfd doesn’t seem to provide an attribute portray hook (attr_portray_hook/2) so the debugger doesn’t provide any attribute information in its output, which is unfortunate.

@emiruz

Is it the case that when CLPFD constrains a domain, there is no backtracking to a less constrained domain?

Hope I understand the question; backtracking undoes constraints so the domains can only get wider (“less constrained”). On the other hand, forward computation can only narrow the domain. It’s the same model as unification: forward computation unifies variables with terms and “ununifying” can only happen on backtracking. (The domain of a logic variable is the set of legal terms.)

HTH.

[emiruz]

@ridgeworks

Now the reason for your cut seems to be to remove the effect of the third clause. This clause just generates solutions without applying any constraints. So without the cut it should just duplicate solutions generated by clause 2, among others (those that don’t satisfy the constraints). So I’m not sure what the intent is of that third clause.

The code maps an ID from a seed via a bunch of category IDs to a location. The rule is that if a mapping does not exist at some point along the way, then the previous ID is retained for the next step. So the idea is to try and map an ID into a range (clause 2) but if it cant be done to just carry the ID (clause 3).

[emiruz]

My conclusion is that it is a limitation with the CLPFD implementation. E.g. search starts with ranges Seed=55…67, but what happens when 55…58 map via clause 2 whilst 59…67 map via clause 3? Prolog backtracking undoes the whole domain (e.g. 55…67), meanwhile CLPFD just provides constraint on the domain. So when it cant find answers for all of 55…67 I end up with just 55…58, but if I force it by adding Seed in 59..67, then suddenly it can find the mapping for 59…67 in Loc, but it can never find both at the same time.

Hence it seems to me that this is a limitation to how constraints are propagated. I.e. what the solver wont do is solve Seed=55…58 via clause 2, split the domain and solve Seed=59…67 via clause 3… it’ll just backtrack with a “solution” of a restricted domain. @jan / @ridgeworks , does that tally with the facts?

[ridgeworks]

@emiruz

My conclusion is that it is a limitation with the CLPFD implementation. E.g. search starts with ranges Seed=55…67, but what happens when 55…58 map via clause 2 whilst 59…67 map via clause 3? Prolog backtracking undoes the whole domain (e.g. 55…67), meanwhile CLPFD just provides constraint on the domain. So when it cant find answers for all of 55…67 I end up with just 55…58, but if I force it by adding Seed in 59..67, then suddenly it can find the mapping for 59…67 in Loc, but it can never find both at the same time.

I believe the reason it can’t find both with a single query is because of the cut. From the single query Seed=55…67, it finds a solution using clause 2 (Seed=55…58) and then removes all choicepoints back to the point of call. this includes not only additional choices due to c/3 but also clause 3 of findit/4. This means findit/4 can only ever generate one solution using clause 2. (Clause 3 does not have a cut, so it may generate multiple solutions based on multiple c/3 choices.)

Now you can start a new query with a different Seed value, e.g., 59…67, but that has nothing to do with the previous query. Presumably the previous solution can’t be proven with this input, so it finds the next one (59…67 ?).

There is nothing special about the behaviour of clpfd goals on backtracking. Constraints are applied on forward computation and removed on backtracking. Failure (resulting in backtracking) occurs whenever the set of applied constraints is inconsistent. This may happen immediately, or it could happen sometime later when another constraint is added.

If you’re still not sure what’s going, try some very simple clpfd examples from the commandline that will either prove or disprove your assumptions.

[emiruz]

Ok so I solved this finally here:

Advent of code 2023

Here’s day 5 again this time implemented using fdset operations in clpfd. I think the set theoretic bit (not the parsing) is probably an optimal treatment of this problem (52 LOC). I map all seeds and categories to sets defined by ranges which the clpfd fdset abstraction makes simple. At every step, all IDs can be expressed as a single set. All that remains is to recursively map the set through the categories to the end, where the infimum of the final set is the answer. map/3 is the gist of it…

It can’t be done the way I suggest previously because its just not how clpfd works. I’ve found it much simpler to think about clpfd in terms of domains. I.e. what domains do I start with? How are they changed by the code to give me an answer at the end? The enumeration of domains is not important: its just enumeration.

I see now why “constraints” are incidental really, and why therefore you can define your own constraints: what matters is the domain they imply for the result. For example, say I have a domain such that X in 1…10, if I want a domain which is offset by 5 I could write 5…15, or I can write:

X in 1..10, Z #= X + 5, fd_dom(Z,Y).

The implication of the constraint above is entirely contained in the domain Y.

[ridgeworks]

@ridgeworks

But debugging clpfd seems problematical for a couple of reasons:

I just discovered that clpfd supports a optimise_clpfd flag (used to be clpfd_goal_expansion), to control goal expansion. Setting it to false greatly improves the ability to debug clpfd code.

To complete the debug picture, it would also be useful if it supported the attr_portray_hook hook, something like:

attr_portray_hook(_,X) :-
    fd_dom(X,Drep),
    format('~w',Drep).

which outputs the current domain, e.g.,

[debug]  ?- trace,X#\=10.
   Call: (11) clpfd:(_44050#\=10) ? skip
   Exit: (11) clpfd:(_45558{inf..9\/11..sup}#\=10) ? leap
X in inf..9\/11..sup.