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.

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. 

LPA Index     Home Page

Valid HTML 4.01 Strict