# Bridge problem

**URL:** <https://swi-prolog.discourse.group/t/bridge-problem/4625>\
**Category:** Help!\
**Created:** [November 2, 2021, 11:27pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625 "2021-11-02T23:27:28Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![XavierDebecq](https://avatars.discourse-cdn.com/v4/letter/x/e47774/32.png) [@XavierDebecq](https://swi-prolog.discourse.group/u/XavierDebecq)\
**Post date:** [November 2, 2021, 11:27pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/1 "2021-11-02T23:27:28Z")

</div>

Hello,

I have a solution for the bridge crossing problem (4 people crossing a bridge with a time of 1,2,5,10 with a torch and they need to take the torch back as long as they didnt all crossed the bridge).  
here is my code :

```prolog
time(b,1).
time(e,2).
time(a,5).
time(l,10).

traverser(Tmax,[],MembresResDG,Temps,Transitions).
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-
    select(Me1,MembresResGD,MembresResGD1),
    select(Me2,MembresResGD1,MembresResGD2),
    append([Me1],MembresResDG,MembresResDG1),
    append([Me2],MembresResDG1,MembresResDG2), 
    select(Me3,MembresResDG2,MembresResDG3),
    append([Me3],MembresResGD2,MembresResGD3),
    time(Me1,X),
    time(Me2,Y),
    time(Me3,Z),
    NewTemps is Temps + max(X,Y) + Z,
    NewTemps =< Tmax,
    append(["Rive gauche : ", MembresResGD3," Rive Droite : ", MembresResDG3," Temps : ",NewTemps],Transitions,NewTransitions),
 % write(NewTransitions),
    traverser(Tmax, MembresResGD3, MembresResDG3, NewTemps,NewTransitions).

```

I don’t get why i cant get the solution.  
Can anybody help ?

---

<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:** [November 3, 2021, 6:23am UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/2 "2021-11-03T06:23:10Z")

</div>

When I tried your program, (in file `/tmp/pont.pl`), I got these warnings:

```prolog
Warning: /tmp/pont.pl:6:
Warning: Singleton variables: [Tmax,MembresResDG,Temps,Transitions]

```

You might start by looking at those.

Also, what is the form of your query? I got this:

```prolog
?- traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions).
MembresResGD = [] ;
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR: [11] _11792 is _11804+ ... + 1
ERROR: [10] traverser(_11830,[b,b|_11850],_11834,_11836,_11838) at /tmp/pont.pl:17
ERROR: [9] toplevel_call(user:user: ...) at /usr/lib/swi-prolog/boot/toplevel.pl:1117

```

PS: When posting, if you surround your code with triple back-quotes, it preserves the layout.

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [November 3, 2021, 8:17am UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/3 "2021-11-03T08:17:40Z")

</div>

> [@peter.ludemann](#):
>
> PS: When posting, if you surround your code with triple back-quotes, it preserves the layout.

I fixed it for them.

---

<div class="post-metadata">

**Author:** ![XavierDebecq](https://avatars.discourse-cdn.com/v4/letter/x/e47774/32.png) [@XavierDebecq](https://swi-prolog.discourse.group/u/XavierDebecq)\
**Post date:** [November 3, 2021, 3:16pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/4 "2021-11-03T15:16:39Z")

</div>

Hello,  
the call you have to do for the function traverser is traverser(17,[b,e,a,l],[],0,[]). The idea is that you start the problem with 4 guys on left of the bridge. You start to move 2 guys on the right and examine if you still have people on the left. If they are not 0, (and that s the point where i have a lack of knowledge in prolog i think), you move one guy from with to left and call the function.  
I have reworked my code and here is the new version :

“”"  
time(b,1).  
time(e,2).  
time(a,5).  
time(l,10).

traverser(\_Tmax,[],\_MembresResDG,\_Temps,\_Transitions).  
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-  
select(Me1,MembresResGD,MembresResGD1),  
select(Me2,MembresResGD1,MembresResGD2),  
append([Me1],MembresResDG,MembresResDG1),  
append([Me2],MembresResDG1,MembresResDG2),  
time(Me1,X),  
time(Me2,Y),  
Temps2 is Temps + max(Y,X),  
not(length(MembresResDG2,0)),  
select(Me3,MembresResDG2,MembresResDG3),  
append([Me3],MembresResGD2,MembresResGD3),  
time(Me3,Z),  
NewTemps is Temps2 + Z,  
NewTemps =\< Tmax,  
append([“Rive gauche : “, MembresResGD3,” Rive Droite : “, MembresResDG3,” Temps : “,NewTemps],Transitions,NewTransitions),  
write(NewTransitions),  
traverser(Tmax, MembresResGD3, MembresResDG3, NewTemps,NewTransitions).””"

My last problem is that i cannot take that line not( length(MembresResDG2,0)), and put instead a test that enable me to write all the transitions that has been used for solving the problem. I dont know how to deal with such test in prolog4 but i know i m close to the solutions (by looking at all the transitions).  
Can you help me ?

---

<div class="post-metadata">

**Author:** ![XavierDebecq](https://avatars.discourse-cdn.com/v4/letter/x/e47774/32.png) [@XavierDebecq](https://swi-prolog.discourse.group/u/XavierDebecq)\
**Post date:** [November 3, 2021, 3:18pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/5 "2021-11-03T15:18:36Z")

</div>

i tried the triple quote but i am not sure of what i did.  
Can you tell me if its ok.

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [November 3, 2021, 3:25pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/6 "2021-11-03T15:25:33Z")

</div>

> [@XavierDebecq](#):
>
> i tried the triple quote but i am not sure of what i did.

You used “”" when you need to use ```, e.g.

``` Prolog code goes here ```

See: [Language highlighting](https://swi-prolog.discourse.group/t/language-highlighting/2260)

---

<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:** [November 3, 2021, 6:45pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/7 "2021-11-03T18:45:09Z")

</div>

First, a minor thing: you can test for a zero-length (empty) list by `MembresResDG2 = [_|_]` – that is, it has at least one member. (Alternatively: `MembresResDG2 \= []`).

Also, your debug output would be easier to read if you used writeln/1.

I think you need to think in terms of “what conditions allow me to terminate”. The first clause seems to be the termination (when `MembresResGD = []`). The second clause allows either an empty or a non-empty list for `MembresResGD`; however, the two calls to select/3 require that `MembresResGD` has at least 2 elements. You can see this for yourself:

```prolog
?- L0 = [1], select(A, L0, L1), select(B, L1, L2).
false.

?- L0 = [1,2], select(A, L0, L1), select(B, L1, L2).
L0 = [1, 2],
A = 1,
L1 = [2],
B = 2,
L2 = [] ; % backtrack for another solution
L0 = [1, 2],
A = 2,
L1 = [1],
B = 1,
L2 = [].

```

---

<div class="post-metadata">

**Author:** ![XavierDebecq](https://avatars.discourse-cdn.com/v4/letter/x/e47774/32.png) [@XavierDebecq](https://swi-prolog.discourse.group/u/XavierDebecq)\
**Post date:** [November 4, 2021, 4:36pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/8 "2021-11-04T16:36:39Z")

</div>

The fact of having at least in the worst case 2 elements for the two select is garanteed by the test. My problem is that i have no if then else. I reworked my code and got an error i still not understand. My problem is that i dont have any knowledge in prolog syntax. From the algorithmical point of view i have a clear idea of what i want to do, but I have no idea how (and if i can) to do it in Prolog. I dont understand clearly the previous post as i dont understand the behaviour of prolog. Backtracking should be commanded by conditions. If it fails, the program just stop and jump to another possible solution, at least its how i see its behaviour.  
I have worked once again :

````prolog
time(e,2).
time(a,5).
time(l,10).

ecrire([]).
ecrire([H|T]) :- write(H), nl, ecrire(T).

traverser(_Tmax,[],_MembresResDG,_Temps,Transitions).
    
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-
    select(Me1,MembresResGD,MembresResGD1),
    select(Me2,MembresResGD1,MembresResGD2),
    append([Me1],MembresResDG,MembresResDG1),
    append([Me2],MembresResDG1,MembresResDG2), 
    time(Me1,X),
    time(Me2,Y),
    Temps2 is Temps + max(Y,X),
    append(["Rive gauche : ", MembresResGD2," Rive Droite : ", MembresResDG2," Temps : ",Temps2],Transitions,Transitions2),
    Temps2 =< Tmax,
    ( not(length(MembresResGD2,0))-> select(Me3,MembresResDG2,MembresResDG3),
    append([Me3],MembresResGD2,MembresResGD3),
    time(Me3,Z),
    NewTemps is Temps2 + Z,
    NewTemps =< Tmax,
    write(Transitions2),
    append(["Rive gauche : " MembresResGD3" Rive Droite : " MembresResDG3 " Temps : " NewTemps],Transitions2,NewTransitions),
    append(MembresResGD3, [], MembreResGFinal),
    append(MembreResDG3,[], MembresResDFinal),
    TempsFinal is NewTemps + 0,
    append(NewTransitions, [],TransitionsFinales);
    append(MembresResGD2, [], MembreResGFinal),
    append(MembreResDG2,[], MembresResDFinal),
    TempsFinal is Temps2 + 0,
    append(Transitions2, [],TransitionsFinales)),    
    traverser(Tmax, MembresResGFinal, MembresResDFinal, TempsFinal,TransitionsFinales).```
````

---

<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:** [November 5, 2021, 5:40pm UTC](https://swi-prolog.discourse.group/t/bridge-problem/4625/9 "2021-11-05T17:40:34Z")

</div>

Perhaps it would help if you fully stated the problem (in French, if you wish – some of us can read French and Google Translate will help the others). E.g.: is it allowed for a single person to cross? Are there constraints on who can cross together? Etc.

Then write down in detail (in English or French) how you would find a single solution (not necessarily the best solution, just a solution). Very often, that solution can be translated directly into Prolog – one of the advantages of working in a high-level language.

As for backtracking: it’s best to think of it as simply finding something with constraints. So, for example, `select(Me1,MembresResGD,MembresResGD1)` simply says "pick an element (called `Me1`) from `MembresResGd`, leaving the residue in `MembresResGD1`. If a subsequent test (“goal”) determines that `Me1` isn’t suitable, backtracking will select a different element for `Me1` and all the subsequent tests (goals) will be tried again. If there is no suitable element, then everything fails. (This is not quite accurate, but I hope it gives you the idea)

That is, the following will select an item that’s divisible by 2:

```prolog
?- select(X, [1,2,3,4], Residue), 0 is X mod 2.
X = 2,
Residue = [1, 3, 4] ;
X = 4,
Residue = [1, 2, 3].

```

Suggestion: some of your variable names are very similar. I would suggest, e.g., changing `MembresResGD` to `MembresDroite` and `MembresResDG` to `MembresGauche`, etc. to avoid typos. (Also, `Membres` doesn’t add information, so just `Droite` and `Gauche` should be enough.)

PS: why is there a goal `TempsFinal is Temps2 + 0`?

_Edit:_ Added an “interpretation” of how select/3 backtracks.
