Cat Army Riddle in Prolog

We solve the giant cat army riddle with logic programming technology. The riddle says we start with zero 0 and can only add 5, add 7 or take root of a square number. The goal is to reach 2, 10 and 14 without repeating

New school Prologers would jump to CLP(Z). But what about old school Prologers, how would one solve it? In our solution we fall back to magic set ideas. Since addition is commutation, we can observe that for a predica 2 where we only ask whether one number can be reached from another number, it is irrelevant whether 5 is added and then 7, or vice versa:

step1(X, Y) :- N is (60-X)//5, between(0, N, K), H is X+K*5,
         M is (60-H)//7, between(0, M, J), Y is H+J*7.
step2(X, Y) :- nth_integer_root_and_remainder(2, X, Y, 0).

:- table path/2.
path(X, Y) :- step1(X, H), (Y = H; step2(H, J), path(J, Y)).

We can now use the predicate path/2 as a guide in looking for non-repeating paths in a new predicate path/4. The predicate path/4 uses an accumulator list L and produces a new list R, by only adding not yet visited numbers. Whether a number is already on the list is checked with member/2.

step(X, Y) :- Y is X+5, Y =< 60.
step(X, Y) :- Y is X+7, Y =< 60.
step(X, Y) :- nth_integer_root_and_remainder(2, X, Y, 0).

/* without magic set */
path0(X, L, X, L).
path0(X, L, Y, R) :- step(X, H), \+ member(H, L), 
   path0(H, [H|L], Y, R).

/* with magic set */
path(X, L, X, L).
path(X, L, Y, R) :- step(X, H), \+ member(H, L), 
   path(H, Y), path(H, [H|L], Y, R).

In the above we had to program step/2 again, since we needed a single-step version and not the ordered multi-step version step2/2. We also provide a predicate path0/4 that does the search without the guidance of path/2, so that we can compare results. Running the problem gives:

SWI-Prolog (threaded, 64 bits, version 8.3.16)

/* without magic set */
?- time((path0(0, [0], 2, H), path0(2, H, 10, J), path0(10, J, 14, L))), 
   reverse(L, R), write(R), nl.
% 13,068,776 inferences, 0.832 CPU in 0.839 seconds (99% CPU, 15715087 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]

/* with magic set */
?- abolish_all_tables.
true.

?- time((path(0, [0], 2, H), path(2, H, 10, J), path(10, J, 14, L))), 
   reverse(L, R), write(R), nl.
% 2,368,325 inferences, 0.150 CPU in 0.152 seconds (99% CPU, 15747365 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]

Noice, the magic sets give a 5.5x speed-up!