Prolog dot product with variables (constraint satisfaction)

Question

I'm working on a prolog assignment and I'm currently very very close to the solution. So, the problem is a constraint satisfaction problem where I have to find values for a set of variables such that certain conditions are true. Specifically, given 3 words (W1,W2,W3), assign their variables such that W1+W2=W3. An example of this would be SEND+MORE=MONEY, or IT+IS=ME.

The constraints are: (1) they have to add up correctly, (2) the starting letter cannot be 0 (3) and all variables must be distinct. And it has to work for a general word problem. My issue is happening when I try to ensure that they add up correctly (I've met the other conditions and I understand the problem). In terms of the second word problem we should have:

 10*I + 1*T
+10*I + 1*S
___________
 10*M + 1*E

So, I have made a function that makes lists of powers of 10 in a certain length, like so:

powlist(1,L) :-
    append([1.0],[],L). 
powlist(N,L) :-
    N1 is N-1,
    X is 10**N1,
    powlist(N1,L1),
    append([X],L1,L),
    !.

I also have the actual list of letters, say, [I,T,I,S,M,E]. I then constructed a list of coefficients (I'll explain that part later) out of powlist so we have something like the following: [10,1,10,1,-10,-1]. I did this so if we took the dot product between this list of coefficients and the list of letters, and it was zero, the constraint would be satisfied. But, I can't get this dot product theory to work. I currently have a line that says:

   scalar_product(Coefficients, Letters, #=, 0)

But this is giving me the following error:

! Instantiation error in argument 2 of is/2
! goal: _102 is 0+10.0*_109

I'm not sure how to define dot product so it can work on variables (instead of just atoms). All of the rest of the code works perfectly (and I don't want to put it on here because this is a very common question for introductory prolog courses, and I don't want to give lazy people answers). What do you guys suggest?

Unknown Unknown · Accepted Answer · 2011-04-12T05:08:47

Your strategy is indeed sound and does work, at least with SWI-Prolog CLP(FD) using the built-in scalar_product/4. I am unfamiliar with the definition of this predicate in SICStus, but it's interface appears to be the same as in SWI-Prolog.

I can make a couple of suggestions. Firstly, perhaps some aspect of the code you've written is generating choicepoints which, when executed in backtracking (e.g., to seek alternate solutions, such as via label/1), the interpreter executes the subgoal _102 is 0+10.0*_109 where _109 is unintentionally unbound. Have you written a predicate which contains such a line? Even if not, I recommend double checking your code to ensure that they do not generate unnecessary choicepoints, such as your definition of powlist/2. I recommend that you try the following instead:

powlist(1, [1]) :- !.
powlist(N, [F|Fs]) :-
    N > 1,
    N1 is N - 1,
    F is 10 ** N1,
    powlist(N1, Fs).

This version leaves no choicepoints for the Prolog interpreter to backtrack to, which might resolve the problem (though, without seeing more code, I simply can't tell).

Otherwise, if you are correct and the error is indeed emanating from within the definition of scalar_product/4 (though I'd be surprised), then perhaps you could generate the scalar product constraint term and add it to the store yourself, manually. For example, consider:

my_scalar_product([V|Vs], [C|Cs], Op, Value) :-
    construct_constraint(Vs, Cs, (V * C), Constr),
    Constraint =.. [Op, Constr, Value],
    Constraint.

construct_constraint([], [], Acc, Acc).
construct_constraint([V|Vs], [F|Fs], Acc, Res) :-
    construct_constraint(Vs, Fs, '+'(Acc, (V * F)), Res).

This version (my_scalar_product/4) assumes the same interface as the built-in scalar_product/4, but it adds the constraint to the store instead of attempting to execute it using is/2.

Prolog dot product with variables (constraint satisfaction)

1 Answers