water.pl

PRl教学程序 PRl教学程序 PRl教学程序

/***********************************************************
taken from "Extension Table Built-ins for Prolog", 
by Chang-Guan Fa & Suzanne W. Dietrich
Software Practive and Experience, Vol22, No.7, 573-597, 1992.
***********************************************************/
:-table solve_dfs/2.

top:-
    solve_dfs(jugs(0,0),Moves).

go:-
    cputime(Start),
    solve_dfs(jugs(0,0),Moves),
    cputime(End),
    write(Moves),nl,
    T is End-Start,
    write('TIME:'),write(T),nl.

solve_dfs(State,[]):-final_state(State).
solve_dfs(State,[Move|Moves]):-
    move(State,Move),
    update(State,Move,State1),
    solve_dfs(State1,Moves).

final_state(jugs(4,_)).
final_state(jugs(_,4)).

move(jugs(V1,V2),fill(1)).
move(jugs(V1,V2),fill(2)).
move(jugs(V1,V2),empty(1)):-V1>0.
move(jugs(V1,V2),empty(2)):-V2>0.
move(jugs(V1,V2),transfer(2,1)):-V2>0.
move(jugs(V1,V2),transfer(1,2)):-V1>0.

update(jugs(V1,V2),empty(1),jugs(0,V2)).
update(jugs(V1,V2),empty(2),jugs(V1,0)).
update(jugs(V1,V2),fill(1),jugs(C1,V2)):-capacity(1,C1).
update(jugs(V1,V2),fill(2),jugs(V1,C2)):-capacity(2,C2).
update(jugs(V1,V2),transfer(2,1),jugs(W1,W2)):-
    capcity(1,C1),
    Liquid is V1+V2,
    Excess is Liquid-C1,
    (Excess=<0->W1=Liquid,W2=0;
     W1 is C1,W2=Excess).
update(jugs(V1,V2),transfer(1,2),jugs(W1,W2)):-
    capcity(2,C2),
    Liquid is V1+V2,
    Excess is Liquid-C2,
    (Excess=<0->W2=Liquid,W1=0;
     W2 is C2,W1=Excess).

capacity(1,8).
capcity(2,5).