0

Assuming I have:

makeTillDone(X) :- try(X).
makeTillDone(X1) :- changeOne(X1, X2), makeTillDone(X2).
makeTillDOne(X1) :- changeTwo(X1, X2), makeTillDone(X2).

prolog will try to satisfy makeTillDone(X) in sequence: 

try(X), 
ChangeOne(X1, X2), makeTillDone(X2) -> try(X)
ChangeOne(X1, X2), makeTillDone(X2) -> changeOne(X3, X4), makeTillDone(X4) -> try(X) 
etc

how can I achieve more uniform backtracking:

try(X), 
ChangeOne(X1, X2), makeTillDone(X2) -> try(X)
ChangeTwo(X1, X2), makeTillDone(X2) -> try(X)
ChangeOne(X1, X2), makeTillDone(X2) -> changeOne(X3, X4), makeTillDone(X4) -> try(X) 
changeOne(X1, X2), makeTillDone(X2) -> changeTwo(X3, X4), makeTillDone(X4) -> try(X) 
etc
karol wołonciej
  • 109
  • 1
  • 1
  • 10
  • 1
    You need to become consistent in the use of contants: Some of your predicates (`ChangeOne(X1, X2)`) have a functor that starts with a capital letter (thus the functor look like a variable instead of a constant): That's not allowed in base Prolog. – David Tonhofer May 22 '20 at 19:37
  • There are still some `ChangeOne/2` and `ChangeTwo/2` ... – David Tonhofer May 22 '20 at 20:09

1 Answers1

2

It is unclear what you are asking.

Your program is a representation of the following search tree (or proof tree).

base tree

...which is traversed in a leftmost-first, depthmost-first manner until a the root node has been proven true (constructively, so we get a valid value for X).

This is of course done recursively, essentially copying the base search tree into lower nodes (with suitable variable renaming, not done here):

recursive tree

The search order you seem to want is a bit more jumpy:

maybe this tree?

Possibly Breadth-First Search or better Iterative Deepening is what you want.

However, this is not as straightforward as it might be as you cannot just change the search strategy of Prolog, but need to write a little interpreter: https://www.cpp.edu/~jrfisher/www/prolog_tutorial/3_3.html

David Tonhofer
  • 14,559
  • 5
  • 55
  • 51