Prolog: how to avoid backtracking without cuts?

Question

So i am trying to write a predicate in prolog that can take a list L1 and a list L2 and return a list of all the elements in L1 that are not in L2. This is what i have so far:

% Append an element to a list.
myappendelem(X,L,[X|L]).

% True if input list contains X.
mycontains([H | T], X) :-
    H == X;
    mycontains(T,X).

% Does the work for notin().
nocontains([],_,A,A).
nocontains([H|T],L,A,R):-
    mycontains(L,H),
    nocontains(T,L,A,R);
    myappendelem(H,A,AR),
    nocontains(T,L,AR,R).

% Returns all elements in L1 not in L2.
notin(L1,L2,R):-
    nocontains(L1,L2,[],X).

This works, however it gives more than one answer, for example:

notin([5,1],[4,3,2,1],X).
X = [5];
X = [5,1].

This is a problem as i am using this predicate to sort out paths in a graph(L1 being the list of nodes i might go to, and L2 being the nodes i have already been to) to ensure that i wont visit the same node more than once and get stuck in a loop. But this implementation gets me stuck in a loop, because it backtracks after it tries with the first X and it fails, to the unaltered X, getting into an infinite loop between the same two nodes that can reach each other. I know this is easy to fix by adding cuts to nocontains like so:

% Does the work for notin().
nocontains([],_,A,A).
nocontains([H|T],L,A,R):-
    mycontains(L,H),!,
    nocontains(T,L,A,R);
    myappendelem(H,A,AR),!,
    nocontains(T,L,AR,R).

But is there a way to achieve the same without cuts? So when I use notin I get only one possible answer? (Its for school, and part of the assignment is to not use any built-in predicates or control operators)

Edit:

Just to be more specific on the limitations of the assignment: It should consist of pure facts and rules, we are not allowed to use any built-in predicates or control structures(including but not limited to arithmetic, cuts or negation-as-failure). Semicolon is okay. Any utility predicates needed we need to define ourselves.

Thanks for all the answers but I am starting to think that it might be more a problem with the method I use for finding a path between two nodes in a graph, as from the answers it doesn't look like there is an easy way around this.

Answer 1

Use a Prolog system that supports dif/2. There are many such systems, even free ones.

dif/2 is used to express, in a purely relational way, that two terms are different.

For example, in your case, describing that an element is not a member of a list:

not_in(_, []).
not_in(L, [X|Xs]) :-
        dif(L, X),
        not_in(L, Xs).

Or shorter, using maplist(dif(L), Ls).

You can use this in your example like this:

?- Ls1 = [5,1], Ls2 = [4,3,2,1], member(M, Ls1), not_in(M, Ls2).
Ls1 = [5, 1],
Ls2 = [4, 3, 2, 1],
M = 5 ;
false.

Note that this produces the unique solution M=5.

No cuts are necessary to express term disequality.