Water Jug problem in Die Hard 3 into a graph

Question

Hi, im not too sure how to implement this...

I need to create a weighted directed graph based on the water jug problem from the movie Die Hard 3 (http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3).

I need to create nodes for all the possible moves (fill, empty, pour). After i need to find the shortest path to the solution. But i am have trouble creating this graph. I am using my own created linked list/node.

Any help with the algorithm to create this graph would be great. Thanks.

ex) given 3 gallon, 5 gallon. Get 4 gallons in the 5 gallon jug. I need to create a graph of all the possible moves to get to 4 gallons. Each different gallon represents a different node.

Happy Thanksgiving =)

Answer 1

Presumably each node holds two positive integers -- number of gallons in the 3-gal jug, number of gallons in the 5-gal jug. Arcs, aka edges (directed), are the "moves" (and labeled with the action the arc represents) -- apparently you also have an unnamed tap handy, since you can always fill either of the jugs; you can also always empty a jug away (so you also have a sink); and so forth (other moves all involve moving water from one gallon to the other, until either the first one is empty, or the second one is full). It's no doubt better to avoid generating legal but useless arcs ("moves"), such as "filling" a jug that's already full, or undoing a move you just made (such as emptying a jug you just filled from the tap), though adding such arcs will only mean a little more work, not an incorrect solution.

So start with (0, 0) -- both jugs full, as you have at the start. Clearly the two arcs from here take you to (3, 0) and (0, 5) respectively (filling one or the other from the tap), and so on. Hope this helps!

Answer 2

At each step you have 6 different options

1.A=full
2.B=full
3.A->B
4.B->A
5.A=0
6.B=0

And here you go. Put states in lookup table and check that none of solution will repeat. This is also stopping condition.

size of lookup table is A * B, and calculating hash is just A*vol(B)+B

In table[A*vol(B)+B] save from witch position you came from. Make initialisation of table elements on -1 (i supose that first index is 0 in your language)

Answer 3

hi i kno that how to crete graph for water jug problem,but sombdy says,"this is wrong". any body know the answer, draw the graph for problem.which is shown below: a 8ltr jug full of wAter.two another jug are given which is 3ltr and 5ltr.divid into two equql part(4,4).and one condition is that "tleast one jug is full or empty"