# General Prolog Concept Questions

**URL:** <https://swi-prolog.discourse.group/t/general-prolog-concept-questions/2308>\
**Category:** General\
**Created:** [May 11, 2020, 7:27pm UTC](https://swi-prolog.discourse.group/t/general-prolog-concept-questions/2308 "2020-05-11T19:27:27Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![joefrank97](https://avatars.discourse-cdn.com/v4/letter/j/f4b2a3/32.png) [@joefrank97](https://swi-prolog.discourse.group/u/joefrank97)\
**Post date:** [May 11, 2020, 7:27pm UTC](https://swi-prolog.discourse.group/t/general-prolog-concept-questions/2308/1 "2020-05-11T19:27:28Z")

</div>

Hi, I am studying for a Final in my programming class. Two of the things we have to be familiar regarding Prolog are:

- **State-space problem solving**
- **Backtracking, derivation trees**

I tried Googling these things, but the information is lacking. I have posted my position of each of these below. Is anyone able to add to/correct my understanding?

State-space problem solving involved a beginning state, a goal state, and however many states between.

Backtracking derivation trees will try to find the first legal “route” or option to solve the problem. If a condition is true, it will continue to the next condition. If it is false, it will try another condition.

Are these correct understandings to some extent? If I were to ask you what each meant, what would you say?

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [May 12, 2020, 5:14pm UTC](https://swi-prolog.discourse.group/t/general-prolog-concept-questions/2308/2 "2020-05-12T17:14:23Z")

</div>

At a high level, this seems about right. However, backtracking can use more complex strategies, such as breadth-first or iterative deepening. Also, there are many ways of organizing a state space.

Prolog’s default strategy is to traverse the state space with depth-first backtracking. SWI-Prolog recently added tabling, which can sometimes avoid infinite recursions. It also has attributed variables, which can transform generate-and-test into an interleaving of testing and generating. And if none of these work for you, it’s not difficult to program other strategies in Prolog (most textbooks show a variety of these).