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.
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 > 0.
applicable(emptyB,state(Qa,Qb)) :- Qb > 0.
applicable(fillA,state(Qa,Qb)) :- Qa < 4.
applicable(fillB,state(Qa,Qb)) :- Qb < 3.
applicable(emptyAinB,state(Qa,Qb)) :- Qa > 0 , Qtot is Qa + Qb , Qtot =< 3.
applicable(emptyBinA,state(Qa,Qb)) :- Qb > 0, Qtot is Qa + Qb , Qtot =< 4.
applicable(fillAwithB,state(Qa,Qb)) :- Qa < 4, Qtrasf is 4 - Qa , Qtrasf =< Qb.
applicable(fillBwithA,state(Qa,Qb)) :- Qb < 3, Qtrasf is 3 - Qb , Qtrasf=<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).
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:
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)
clearly it's not the shortest path, operations 2 and 4 are unnecessarily.
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?
Found a solution, based on the Bratko implementation of BFS and the representation of the state provided by logtalk. This is my final code, I verified that is a BFS with trace.
go:-start(Start),solve(Start,Solution),reverse(Solution,L),print(L).
solve( Start, Solution) :-
breadthfirst( [ [Start] ], Solution).
% breadthfirst( [ Path1, Path2, ...], Solution):
% Solution is an extension to a goal of one of paths
breadthfirst( [ [Node | Path] | _], [Node | Path]) :-
goal( Node).
breadthfirst( [Path | Paths], Solution) :-
extend( Path, NewPaths),
append( Paths, NewPaths, Paths1),
breadthfirst( Paths1, Solution).
extend( [Node | Path], NewPaths) :-
bagof( [NewNode, Node | Path],
( next_state( Node, NewNode), \+member( NewNode, [Node | Path] ) ),
NewPaths),
!.
extend( Path, [] ). % bagof failed: Node has no successor
% states are represented by the compound term (4-gallon jug, 3-gallon jug);
% in the initial state both jugs are empty:
start((0, 0)).
% the goal state is to measure 2 gallons of water:
goal((2, _)).
goal((_, 2)).
% fill up the 4-gallon jug if it is not already filled:
next_state((X, Y), (4, Y)) :- X < 4.
% fill up the 3-gallon jug if it is not already filled:
next_state((X, Y), (X, 3)) :- Y < 3.
% if there is water in the 3-gallon jug Y > 0) and there is room in the 4-gallon jug (X < 4) THEN use it to fill up
% the 4-gallon jug until it is full (4-gallon jug = 4 in the new state) and leave the rest in the 3-gallon jug:
next_state((X, Y), (4, Z)) :- Y > 0, X < 4,
Aux is X + Y, Aux >= 4,
Z is Y - (4 - X).
% if there is water in the 4-gallon jug (X > 0) and there is room in the 3-gallon jug (Y < 3) THEN use it to fill up
% the 3-gallon jug until it is full (3-gallon jug = 3 in the new state) and leave the rest in the 4-gallon jug:
next_state((X, Y), (Z, 3)) :- X > 0, Y < 3,
Aux is X + Y, Aux >= 3,
Z is X - (3 - Y).
% there is something in the 3-gallon jug (Y > 0) and together with the amount in the 4-gallon jug it fits in the
% 4-gallon jug (Aux is X + Y, Aux =< 4) THEN fill it all (Y is 0 in the new state) into the 4-gallon jug (Z is Y + X):
next_state((X, Y),(Z, 0)) :- Y > 0,
Aux is X + Y, Aux =< 4,
Z is Y + X.
% there is something in the 4-gallon jug (X > 0) and together with the amount in the 3-gallon jug it fits in the
% 3-gallon jug (Aux is X + Y, Aux =< 3) THEN fill it all (X is 0 in the new state) into the 3-gallon jug (Z is Y + X):
next_state((X, Y),(0, Z)) :- X > 0,
Aux is X + Y, Aux =< 3,
Z is Y + X.
% empty the 4-gallon jug IF it is not already empty (X > 0):
next_state((X, Y), (0, Y)) :- X > 0.
% empty the 3-gallon jug IF it is not already empty (Y > 0):
next_state((X, Y), (X, 0)) :- Y > 0.
print([]).
print([H|T]):-write(H),nl,print(T).
Only one last little question, I'd like to store the action performed to reach each state, but I don't know how to do it. For example if the state is (0,0), the next state could be (0,3) with action "fillB", how could I store this action? I'd like to don't modify the BFS implementation and simply putting this into the state representation, for example (0,3,fillB) shouldn't work because more than one state correspond to an action, so the membership check of the new state in the path will fail.
EDIT
Action performed can be retrieved from two adjacent states of the solution so I just added this lines to the code:
action((_,Y),(4,Y),fill1).
action((X,_),(X,3),fill2).
action((_,Y),(4,Z),put(2,1)):-Y\=Z.
action((X,_),(Z,3),put(1,2)):-X\=Z.
action((X,_),(Z,0),put(2,1)):-X\=Z.
action((_,Y),(0,Z),put(2,1)):-Y\=Z.
action((_,Y),(0,Y),empty1).
action((X,_),(X,0),empty2).
And redefined the print predicate:
print([],_).
print([H|T],0):-write(start),tab(4),write(H),nl,print(T,H).
print([H|T],Prev):-action(Prev,H,X),write(X),tab(4),write(H),nl,print(T,H).