title: Prolog - breadth first search for water jug
body: <p>I'm studying search strategies in the state space in Prolog, I'm looking at the following program, is the famous water jugs problem, to keep it simple you have 2 jugs (4 and 3 litres), you can fill, empty and transfer the water into the other jug until the first is empty or the second is full. The goal is to have 2 litres (the jugs don't have any measuring).
  This implementation should be a breadth first.</p>
  
  <pre><code>go:-solution(S).
  
  solution(ActionList):-init(I),nl,write(init),tab(4),write(I),
                        nl,solution(I,[],ActionList),!.
  
  solution(State,VisitedStates,[]) :- final(State).
  
  solution(State,VisitedStates, [Action|Rest]) :- applicable(Action,State) ,
                                          apply(Action,State,NewState),
                      \+visited(NewState,VisitedStates), write(Action), tab(4) , write(NewState), nl,
                      solution(NewState,[State|VisitedStates],Rest).
  
  visited(State,[VisitedState|OtherVisitedStates]) :-   sameState(State,VisitedState).
  
  visited(State,[VisitedState|OtherVisitedStates]) :- visited(State,OtherVisitedStates).
  sameState(S,S).
  
  
  init(state(0,0)).
  final(state(2,X)).
  applicable(emptyA,state(Qa,Qb)) :- Qa &gt; 0.
  applicable(emptyB,state(Qa,Qb)) :- Qb &gt; 0.
  applicable(fillA,state(Qa,Qb)) :- Qa &lt; 4.
  applicable(fillB,state(Qa,Qb)) :- Qb &lt; 3.
  applicable(emptyAinB,state(Qa,Qb)) :- Qa &gt; 0 , Qtot is Qa + Qb , Qtot =&lt; 3.
  applicable(emptyBinA,state(Qa,Qb)) :- Qb &gt; 0, Qtot is Qa + Qb , Qtot =&lt; 4.
  applicable(fillAwithB,state(Qa,Qb)) :- Qa &lt; 4, Qtrasf is 4 - Qa , Qtrasf =&lt; Qb.
  applicable(fillBwithA,state(Qa,Qb)) :- Qb &lt; 3, Qtrasf is 3 - Qb , Qtrasf=&lt;Qa.
  
  apply(emptyA,state(Qa,Qb),state(0,Qb)).
  apply(emptyB,state(Qa,Qb),state(Qa,0)).
  apply(fillA,state(Qa,Qb),state(4,Qb)).
  apply(fillB,state(Qa,Qb),state(Qa,3)).
  apply(emptyAinB,state(Qa,Qb),state(0,Qtot)) :- Qtot is Qa+Qb.
  apply(emptyBinA,state(Qa,Qb),state(Qtot,0)) :- Qtot is Qa+Qb.
  apply(fillAwithB,state(Qa,Qb),state(4,NewQb)) :- NewQb is Qb-(4-Qa).
  apply(fillAwithB,state(Qa,Qb),state(NewQa,3)) :- NewQa is Qa-(3-Qb).
  </code></pre>
  
  <p>What is not clear to me is how to understand that is beadthfirst and not depth first for example, looking at the code. I'm looking at the implementation of BF in the book "Prolog programming for Artificial Intelligence" (I.Bratko) and it seems different to me as it keep all the alternatives candidates (node or states in my case) with their path (as should be in theory). Another issue: BF should find the shortest path first, but this the response of my program:</p>
  
  <pre><code>init    state(0,0)
  fillA    state(4,0)
  fillB    state(4,3)
  emptyA    state(0,3)
  emptyBinA    state(3,0)
  fillB    state(3,3)
  fillAwithB    state(4,2)
  emptyA    state(0,2)
  emptyBinA    state(2,0)
  </code></pre>
  
  <p>clearly it's not the shortest path, operations 2 and 4 are unnecessarily.</p>
  
  <p>Additional details: I tried to execute with trace, and seems not to be a BF definitively, as starting from "state(0,0)" the only states directly reachable are "state(4,0)" and "state(0,3)", then in a BFS these 3 nodes as to be visited, but looking at the trace, they're not, after state(4,0) it visit state(4,3). Now can you confirm I am on the right way and this is not a BFS? but trying to follow the Bratko implementation I have a problem: I should enumerate every node with its successor, I think it's not feasible with the water jug problem. Any hints?</p>