Search code examples
recursionprologinstantiation-error

Prolog - Arguments are not sufficiently instantiated. Recursion depth

I'm new to prolog and want to limit recursion depth, but it keeps throwing "Arguments are not sufficiently instantiated" error. I'll generalise the problem to a graph.

edge(a,b).
edge(a,x).
edge(b,c).
edge(b,x).
edge(c,d).

So, there's a path from a to d: a-b-c-d It's pretty easy to check if there's a path between two vertices:

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

Now I want to limit the length of the path to N:

limitedPath(X,Y,N) :- edge(X,Y), N >= 0.
limitedPath(X,Y,N) :- edge(X,Z),limitedPath(Z,Y,M), N = M + 1, N>0.

limitedPath(a,b,2) is true, but limitedPath(a,c,1) throws "Arguments are not sufficiently instantiated", and I can't get the reason.

Solution

  • To continue your idea:

    :- use_module(library(clpfd)).

limitedPath(X,Y,N) :- N #>= 0, edge(X,Y).
limitedPath(X,Y,N) :- N #>= 0, N #= M+1, edge(X,Z), limitedPath(Z,Y,M).