In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes the puzzle.
You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can take: (1) fill a jug, (2) empty a jug, and (3) pour water from one jug to the other. The action of pouring water from one jug to the other stops when either (a) the first jug is empty or (b) the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
Accessary Functions
A. Define rules for the basic operations of the two jugs, as described below:
Fill-A/3 – fill Jug A, Fill-B/3 Empty-A/3 Empty-B/3 A-to-B/3 – pour everything from A to B B-to-A/3 Each of these functors takes 3 (list) parameters (hence the /3): Size, Current, Next, or more specifically, [Size-A, Size-B], [Current-in-A, Current-in-B], [Next-in-A, Next-in-B]. For example:
?- A-to-B([5,3], [4,2], [A,B]).
A = 3
B = 3
?- A-to-B([5,3], [4,2], Next).
Next = [3,3]
You will then define a functor named move which combines all these operations, ex.,
Move(Size, Current, New) :- Fill-A(Size,Currect,New);Fill-B(Size,Current,New) ..
Alternatively, you could just name all 6 operations move. In any case, when a move is attempted, all 6 operations will be tried in the order in which they are listed. For example:
?- move([5, 3], [4, 2], [A, B]).
A = 5
B = 2 ;
A = 4
B = 3 ;
A = 0
B = 2 ;
A = 4
B = 0 ;
A = 3
B = 3 ;
A = 5
B = 1 ;
B. Define a functor printJugs/1 which accept as argument a list describing the solution path in the form of [state1, state2, …., goalState], where each state is a list of two numbers indicating the amount of water in jugs A and B. It should print the list of move as indicated in the solution path. See prolog2out.doc for sample output. Depth-first Search (40 points)
Write prolog rules that will allow a depth-first search by SWI Prolog to solve the jugs problem. Be sure to study class examples such as FWGC as your solution could be very similar the example. Note that the top level rule should be named jugs and should take 3 arguments: [SizeA, SizeB], GoalSize, and SolutionPath, where SizeA and SizeB are the sizes of the two jugs A and B, respectively, with SizeA >= SizeB, GoalSize is the desired amount of water in the larger jugs, and SolutionPath is the variable which will be instantiated with the solution path when it’s found. Since the SolutionPath could be longer than what swi-porlog is willing to display with full details, your rule must call the printJugs functor to print the list of moves when a solution is found.