prolog

Prolog: get the solution with minimal absolute value from the list of solutions


Suppose, we have the following equation in Z_{12} we want to solve in Prolog:

(x + y) mod 12 = z

with the following domains for variables:

We write the following predicate:

:- use_module(library(clpfd)).

solve(X, Y, Z) :-
    X #> -1,
    X #< 12,
    Y #> -12,
    Y #< 12,
    Z #> -1,
    Z #< 12,
    Z #= mod(X + Y, 12).

Then we try to solve the equation: (11 + y) mod 12 = 1

?- solve(11, Y, 1).
Y in -10..2,
11+Y#=_A,
_A in 1..13,
_A mod 12#=1.

Prolog says that there are 2 solutions: {-10, 2}, which is true:

1 2 3 4 5 6 7 8 9 10 (<-) 11 (->) 0 1

To reach 1 from 11 we can move ether 10 steps backwards and 2 steps forward.

Question: how get the the solution with minimal absolute value? So having {-10, 2} take 2 from it. If we have {-2, 10} take -2.

If the values are equal by the absolute value, take both of them: {-6, 6}.


Solution

  • Prolog says that there are 2 solutions: {-10, 2}, which is true:

    That -10..2 is a range telling you the solutions are bounded at -10 and 2, but could be any of the values in between. Exactly two solutions would look like -10\/2. You need to label Y for it to search for the answers.

    The order of solutions can be influenced with:

    min(Expr)
    max(Expr)
    

    So you can get the smallest absolute value first using that, e.g.:

    ?- solve(11,Y,1),
       labeling([min], [Y]).
    
    Y = -10
    
    ?- solve(11,Y,1),
       labeling([min(abs(Y))], [Y]).
    
    Y = 2
    

    But to do the test if they are equal you might need something like finding both values for Y (assuming there are always two) and if/else branching on the result, but this is a bit ugly:

    solve(11,Y,1), 
    findall(Y, 
            labeling([min(abs(Y))], [Y]), 
            [Y1, Y2]),
    
    (Y1 = Y2
        -> Answer = Y1-Y2
        ;  Answer = Y1)
    .