Given two jugs of known capacities, you have to obtain a specified amount by filling jugs, emptying jugs, and pouring the contents of one jug into the other jug.
breadth(Moves):- initial_posn(Position), empty_queue(Queue0), enqueue(b(Position, []), Queue0, Queue), breadth_first(Queue, [], Moves). breadth_first(Queue, _, FinalMoves):- dequeue(b(Position, Path), Queue, _), final_posn(Position), reverse(Path, [], FinalMoves). breadth_first(Queue0, History, FinalMoves):- dequeue(b(Position, Path), Queue0, Queue1), findall(Move, move(Position, Move, _), Moves), filter(Moves, Position, Path, History, Queue1, Queue), breadth_first(Queue, [Position|History], FinalMoves). filter([], _, _, _, Queue, Queue). filter([Move|Moves], Position, Path, History, Queue0, Queue):- move(Position, Move, Position1), \+ member(Position1, History), !, enqueue(b(Position1, [Move|Path]), Queue0, Queue1), filter(Moves, Position, Path, History, Queue1, Queue). filter([_|Moves], Position, Path, History, Queue0, Queue):- filter(Moves, Position, Path, History, Queue0, Queue). empty_queue(q(zero, Ys, Ys)). enqueue(X, q(N, Ys, [X|Zs]), q(s(N), Ys, Zs)). dequeue(X, q(s(N), [X|Ys], Zs), q(N, Ys, Zs)). capacities(8, 5). /* These are the capacities of the jugs */ required(4). /* This is the amount to be obtained */ initial_posn(p(0, 0)). /* Both jugs are empty */ final_posn(p(N, _)):-required(N). /* The required amount is in jug 1 */ final_posn(p(_, N)):-required(N). /* The required amount is in jug 2 */ move(p(S, T), empty(1), p(0, T)):- /* Empty jug 1 */ S > 0. move(p(S0, T), fill(1), p(S, T)):- /* Fill jug 1 */ capacities(S, _), S0 < S. move(p(S, T), to(1, 2), p(0, V)):- /* Empty jug 1 into jug 2 */ S > 0, capacities(_, B), S + T =< B, V is S + T. move(p(S, T), to(1, 2), p(U, B)):- /* Fill jug 2 from jug 1 */ S > 0, capacities(_, B), T < B, S + T > B, U is S + T - B. move(p(S, T), empty(2), p(S, 0)):- /* Empty jug 2 */ T > 0. move(p(S, T0), fill(2), p(S, T)):- /* Fill jug 2 */ capacities(_, T), T0 < T. move(p(S, T), to(2, 1), p(U, 0)):- /* Empty jug 2 into jug 1 */ T > 0, capacities(A, _), S + T =< A, U is S + T. move(p(S, T), to(2, 1), p(A, V)):- /* Fill jug 1 from jug 2 */ T > 0, capacities(A, _), S < A, S + T > A, V is S + T - A.