CODEWITHSUNDEEP
prolog
keont
keont

Reputation: 673

How to stop backtracking when recursively calling a rule

So I have a problem that should be easy to solve, come to this point where I know the flow of this program I'm working on.

There is code before but this piece of code I paste here is called with this:

pairs_nodes_arcs(C, C, SalidaCreacionEnum, EnumArcos).

What it should do: Travel through second argument till it's empty, find if it meets every condition, if it does, give the ouput list that got formed (EnumArcos should then hold the answer) because of the conditions as an "answer" (that I have the intention of sending "up" through backtracking to the rest of the code, since it's one of the answers of the real question).

Now, if fails, it should (and does), remove the head of the third argument, which is a list of lists, and "re-start" the second argument (I also do this succesfully because I always hold a copy to this first argument, which is the same than the second originally was).

So as I said, it should return, in it's 4th argument, the answer list. And it does, when I use trace I see the correct answer there (finally!!) but it gets lost because when it does backtracking, that answer list get's empty, and I end up returning empty.

I just read here http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse9 that an base query is mandatory. But I can't figure it out (in strict sense, my code does not get into an infinite loop, and even if it's by dumb luck, it's not the problem). The problem is that when backtracking, I loose the answer.

pairs_nodes_arcs(_, _, [],_).
pairs_nodes_arcs(_, [], _,_).
pairs_nodes_arcs([], _, _, _).
pairs_nodes_arcs([A-B | T],[C-D | Tail0], [H|NODES], LISTARCS) :-
    member(enum(NODE_ID_C, C), H),
    member(enum(NODE_ID_D, D), H),
    REMAINDER is abs(NODE_ID_C-NODE_ID_D),
    arcs_are_repeated([A-B  | T], [C-D | Tail0], [H|NODES], REMAINDER,LISTARCS).

arcs_are_repeated([A-B | T], [_ | Tail0], [H|NODES], REMAINDER, ListArcsInput):-
    %maplist(dif(enum(REMAINDER,_)), ListArcsInput),
    myMapList(enum(REMAINDER,_),ListArcsInput),
    pairs_nodes_arcs([A-B | T], Tail0, [H|NODES], [enum(REMAINDER, A-B) | ListArcsInput], ).

arcs_are_repeated([A-B | T], [_], [H|NODES],_,_):-
    pairs_nodes_arcs([A-B | T], [A-B | T], NODES, []).


myMapList(_, []).
myMapList(enum(NUM1,_), [enum(NUM2,_)|InputList]):-
    dif(NUM1,NUM2),
    myMapList(enum(NUM1,_), InputList).

I also have the trace, I paste only the specific part where I feel like I "loose the answer (I manually separate the 4th argument to give it emphasis, it's all part of the same parenthesis):

pairs_nodes_arcs([a-b, b-c], [], [[enum(1, c), enum(3, b), enum(2, a)], [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)], [enum(3, c), enum(1, b), enum(2, a)], [enum(3, c), enum(2, b), enum(1, a)]], 


[enum(2, a-b), enum(1, a-b)])


 Exit:pairs_nodes_arcs([a-b, b-c], [], [[enum(1, c), enum(3, b), enum(2, a)], [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)], [enum(3, c), enum(1, b), enum(2, a)], [enum(3, c), enum(2, b), enum(1, a)]], [enum(2, a-b), enum(1, a-b)])
 Exit:arcs_are_repeated([a-b, b-c], [b-c], [[enum(1, c), enum(3, b), enum(2, a)], [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)], [enum(3, c), enum(1, b), enum(2, a)], [enum(3, c), enum(2, b), enum(1, a)]], 2, 


[enum(1, a-b)])


 Exit:pairs_nodes_arcs([a-b, b-c], [b-c], [[enum(1, c), enum(3, b), enum(2, a)], [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)], [enum(3, c), enum(1, b), enum(2, a)], [enum(3, c), enum(2, b), enum(1, a)]], 


[enum(1, a-b)])

edit1 Ok so my way of fixing this so far seems to be to pass an empty list, which I operate, and a variable that I always keep for myself. Then when the base case of SUCCEED succeeds, I unify the operated list that is the solution with the variable. I do that at least 3 times in the code and need it 1 more time. Not 100% it's a nice way of doing it though, I end up with a number of arguments but... I mean that there seems to be problems with this approach but it's one, at least.

Upvotes: 2

Views: 662

Answers (1)

mat
mat

Reputation: 40768

You answer is not about backtracking (backtracking happens on failure), but about success: You expect your program to succeed with a specific binding, but it doesn't.

To debug this, think declaratively: Write down a goal that ought to succeed, but fails.

In your example, the query:

?- arcs_are_repeated([a-b, b-c], [b-c], [[enum(1, c), enum(3, b), enum(2,a)],
    [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)],
    [enum(3, c), enum(1, b), enum(2, a)], [enum(3, c), enum(2, b), enum(1, a)]], 
    2, [enum(1, a-b)]).

may be such an example.

Then, make the goal more general, in such a way that it still fails. For example, does the following still fail:

?- arcs_are_repeated([a-b, b-c], [b-c], [[enum(1, c), enum(3, b), enum(2,a)],
    [enum(2, c), enum(1, b), enum(3, a)], [enum(2, c), enum(3, b), enum(1, a)], _], 2, _).

if so, generalize it further. For example, what about:

?- arcs_are_repeated([a-b, b-c], _, _, _, _).

If this fails, you have narrowed down a case you have not yet taken into account, no matter what the arguments are.

This is how you debug declaratively: Think about what should succeed, but fails, and think about what should fail, but succeeds. In the former case, your program is too specific, and in the latter, it is too general. In your case, it is too specific, and so you either need to:

  • add a clause or
  • remove a constraints in the existing clauses

to make the program more general.

Upvotes: 4

Related Questions