solve water jug with depth-first search

Question

I've got this water jug problem to solve, and I have to do it by depth-first algorithm. I have two water jugs, a 4-gallon and a 3-gallon, neither of them is marked. How can you get exactly 2 gallons of water into the 4-gallon jug? Initially both jugs are empty.

Rules are:

capacity(C,JC), for C equal j1 or j2; 
jugs(C1,C2), where C1 and C2 give the current contents of the jugs

initial starting fact: jugs(0,0) goal: jugs(2,0) or jugs(0,2)

initial_state(jugs,jugs(0,0)). 

final_state(jugs(2,C2)). 
final_state(jugs(C1,2)).  

transition(jugs(C1,C2),fill(j1)). 
transition(jugs(C1,C2),fill(j2)). 
transition(jugs(C1,C2),empty(j1)) :-  
    C1 > 0. 
transition(jugs(C1,C2),empty(j2)) :-  
    C2 > 0. 
transition(jugs(C1,C2),transfer(j2,j1)). 
transition(jugs(C1,C2),transfer(j1,j2)).  


update(jugs(C1,C2),empty(j1),jugs(0,C2)). 
update(jugs(C1,C2),empty(j2),jugs(C1,0)). 
update(jugs(C1,C2),fill(j1),jugs(Capacity,C2)) :-  
    capacity(j1,Capacity). 
update(jugs(C1,C2),fill(j2),jugs(C1,Capacity)) :-  
    capacity(j2,Capacity). 
update(jugs(C1,C2),transfer(j2,j1),jugs(W1,W2)) :-  
    capacity(j1,Capacity), 
    Water is C1 + C2, 
    Overhang is Water - Capacity , 
    adapt(Water,Overhang,W1,W2). 
update(jugs(C1,C2),transfer(j1,j2),jugs(W1,W2)) :-  
    capacity(j2,Capacity), 
    Water is C1 + C2, 
    Overhang is Water - Capacity , 
    adapt(Water,Overhang,W2,W1).  

adapt(Water,Overhang,Water,0) :- Overhang =< 0. 
adapt(Water,Overhang,C,Overhang) :- 
    Overhang > 0, 
    C is Water - Overhang. 




legal(jugs(C1,C2)).  

capacity(j1,4). 
capacity(j2,3).

Thank you in advance!

You have got a problem and a solution. where is the problem with the solution? Guessing: If it is running endlessly you need to add a list of states you were in so you never access one twice. — User, Oct 09 '13 at 22:05
You asked how, here's how: fill 4-jug, pour into 3-jug, empty 3-jug, empty 4 into 3, fill 4, pour into 3, DONE. ;) Is that what you asked for? What is the code attached for? :) — Will Ness, Oct 12 '13 at 18:56

solve water jug with depth-first search

0 Answers0