Prologue: Pythagorean Triple

Question

I have this code that uses the upper boundary variable N, which should end for X and Y of the Pythagorean trio. However, it only freezes when it reaches the upper limit. I was not sure how to use the cut to stop the rollback. The code:

is_int(0). is_int(X) :- is_int(Y), X is Y+1. minus(S,S,0). minus(S,D1,D2) :- S>0, S1 is S-1, minus(S1,D1,D3), D2 is D3+1. pythag(X,Y,Z,N) :- int_triple(X,Y,Z,N), Z*Z =:= X*X + Y*Y. int_triple(X,Y,Z,N) :- is_int(S), minus(S,X,S1), X>0, X<N, minus(S1,Y,Z), Y>0, Y<N. 

Will be called, for example, with

 ?- pythag(X,Y,Z,20). 

Answer 1

First, let's test your solution:

  ? - pythag (X, Y, Z, 20).
 X = 4
 Y = 3,
 Z is 5;
 X = 3,
 Y = 4
 Z is 5;
 X = 8,
 Y = 6,
 Z = 10;
 X = 6,
 Y = 8
 Z = 10;
 X = 12,
 Y = 5,
 Z is 13;
 X = 5,
 Y = 12
 Z is 13;
 X = 12,
 Y = 9
 Z = 15;
 X = 9,
 Y = 12
 Z = 15;
 X = 15,
 Y = 8
 Z = 17;
 X = 8,
 Y = 15
 Z = 17;
 X = 16,
 Y = 12
 Z = 20;
 X = 12,
 Y = 16,
 Z = 20 ...

Looks perfect for me! All answers are right decisions! ... up to the last decision. After that, your program loop.

Before we try to identify the problem, just hold on for a moment: you should be quite patient to go through 12 (that is: twelve) answers just to find this cycle. Do you think this method will also work for large cases? How many answers do you want to see before you give up? Isn't there an easier way to find out about a problem?

There is one interesting note here: The answers found are (almost) not related to the program loop! That is: looking at the answers, you get (often, as in this case) no information about the actual cause of the cycle! So why not turn off all the answers and focus on the relevant part! In fact, we can do this as follows:

  ? - pythag (X, Y, Z, 20), false.
 ** LOOP **

Now all answers are deleted due to the target false . Only the end result remains: either termination, or not termination, or some error. Nothing more. This should facilitate our observations on the completion of bits - no more dazzling answers scrolling the screen. Please note that this does not solve the problem at all. After all, how long are we ready to wait? 1s? 1m?

The actual reason for not receiving it can best be understood by looking at the corresponding piece of failure . This is a fragment of a program whose failure to fulfill means failure to complete the entire program. See this answer for more details . Here is the appropriate snippet for your program to pythag(X,Y,Z,20), false to request pythag(X,Y,Z,20), false :

  pythag (X, Y, Z, N): -
    int_triple (X, Y, Z, N), false ,
    Z * Z =: = X * X + Y * Y.

 int_triple (X, Y, Z, N): -
    is_int (S), false ,
    minus (S, X, S1), X> 0, X <N ,
    minus (S1, Y, Z), Y> 0, Y <N .

 is_int (0) : - false .
 is_int (X): -
    is_int (Y), false,
    X is Y + 1.

Please note that some information is left about your program. For example, the actual equation is gone (which is more or less the logical part ...). However, this fragment matters. And until you change something inside this fragment, the problem will persist! This is guaranteed for a clean, monotonous program like this ...

Here is my preferred solution: it uses length/2 and between/3 , two often supported predicates. Prolog prolog .

  pythag2 (X, Y, Z, N): -
    length (_, N),
    between (1, N, X),
    between (1, N, Y),
    between (1, N, Z),
    Z * Z =: = X * X + Y * Y.

Answer 2

I recently thought of a Prolog solution for finding Pythagorean trinity. I came up with a slightly different code. Suppose we have a function:

 isqrt(a) = floor(sqrt(a)) 

Then it is enough to list x and y and check that x * x + y * y is the square of some z. Namely for verification:

 h = x*x+y*y, z = isqrt(h), z*z = h ? 

The isqrt function can be implemented by dividing in half. For symmetry breaking we can list y after x. Assuming N = 99, the resulting code is:

 % between(+Integer, +Integer, -Integer) between(Lo, Hi, _) :- Lo > Hi, !, fail. between(Lo, _, Lo). between(Lo, Hi, X) :- Lo2 is Lo+1, between(Lo2, Hi, X). % bisect(+Integer, +Integer, +Integer, -Integer) bisect(Lo, Hi, X, Y) :- Lo+1 < Hi, !, M is (Lo+Hi) // 2, S is M*M, (S > X -> bisect(Lo, M, X, Y); S < X -> bisect(M, Hi, X, Y); M = Y). bisect(Lo, _, _, Lo). % pythago(-List) pythago(X) :- X = [A,B,C], between(1, 99, A), between(A, 99, B), H is A*A+B*B, bisect(0, H, H, C), C =< 99, H =:= C*C. 

There must be 50 such Pythagorean triplexes, see also Sloan A046083 :

 ?- findall(-, pythago(_), L), length(L, N). N = 52. 

One could cross with the next CLP (FD).

 :- use_module(library(clpfd)). % pythago3(-List) pythago3(X) :- X = [A,B,C], X ins 1..99, A*A+B*B #= C*C, A #=< B, label(X). 

It gives the same number of solutions:

 ?- findall(-, pythago3(_), L), length(L, N). N = 50.