#### The Jugs Puzzle

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.

initial_posn(Position),
empty_queue(Queue0),
enqueue(b(Position, []), Queue0, Queue),

dequeue(b(Position, Path), Queue, _),
final_posn(Position),
reverse(Path, [], FinalMoves).
dequeue(b(Position, Path), Queue0, Queue1),
findall(Move, move(Position, Move, _), Moves),
filter(Moves, Position, Path, History, Queue1, Queue),

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.