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:

• x \in [0, 11]
• y \in [-11, 11]
• z \in [0, 11]

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