hanoi.pl

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

/********************************************************************
    Constraint-based Graphical Programming in B-Prolog
    %
    animate the plan for solving the Towers of Hanoi
*********************************************************************/
go:-
    hanoi(3).

hanoi(N):-
    hanoi_plan(N,1,3,2,Plan,[]),
    initialFacts(1,N,Fs),
    createShowFramesLoop(N,[top(1,1)|Fs],Plan).

initialFacts(N0,N,Fs):-N0=:=N,!,Fs=[onTable(N,1)].
initialFacts(N0,N,Fs):-
    N1 is N0+1,
    Fs=[on(N0,N1,1)|Fs1],
    initialFacts(N1,N,Fs1).
    
hanoi_plan(0,P1,P2,P3,Plan,PlanR):-!,Plan=PlanR.
hanoi_plan(N,P1,P2,P3,Plan,PlanR):-
    N1 is N-1,
    hanoi_plan(N1,P1,P3,P2,Plan,Plan1),
    Plan1 = [move(N,P1,P2)|Plan2],
    hanoi_plan(N1,P3,P2,P1,Plan2,PlanR).
    
createShowFramesLoop(N,Fs,Plan):-
    cgStartRecordAnimation('Hanoi'),
    not(not(createShowFrames(N,Fs,Plan))),
    cgStopRecord.


createShowFrames(N,Fs,[]):-
    createShowFrame(N,Fs).
createShowFrames(N,Fs,[Step|Steps]):-
    createShowFrame(N,Fs),
    cgSleep(1000),
    updateFacts(Fs,Step,NewFs),
    createShowFrames(N,NewFs,Steps).

/* use three same-size virtual rectangles to place the components */
createShowFrame(N,Fs):-
    not(not((createFrame(N,Fs,Frame),
	     cgPack(Frame),
	     cgCleanDefaultWindow,
	     cgShow(Frame),
	     cgSleep(1000)))).

createFrame(N,Fs,Frame):-
    Rs=[R1,R2,R3],
    cgRectangles(Rs),
    cgSame(Rs,width,RectWidth),
    cgSame(Rs,height,RectHeight),
    cgSameRow(Rs),
    %
    functor(Ds,disk,N),
    createDisks(1,N,Ds,R1),
    constrainDisks(Fs,Ds,pans(R1,R2,R3)),
    Ds=..[_|Disks],
    %
    Poles=[P1,P2,P3],
    cgRectangles(Poles),cgSame(Poles,color,red),
    P1^centerX #= R1^centerX,
    P2^centerX #= R2^centerX,
    P3^centerX #= R3^centerX,
    P1^bottomY #= R1^bottomY,
    %
    arg(1,Ds,D1),
    PoleWidth #= D1^width-20,
    PoleWidth #>= 5,
    cgSame(Poles,width,PoleWidth),
    cgSame(Poles,height,RectHeight),
    %
    cgRectangle(Table),
    Table^width #= 3*R1^width,
    Table^x #= R1^x,
    Table^height #= 30,
    cgAbove(R1,Table),
    Frame=[Table,P1,P2,P3|Disks].

constrainDisks([],Ds,Pans).
constrainDisks([on(N1,N2,P)|Fs],Ds,Pans):-!,
    arg(N1,Ds,D1),
    arg(N2,Ds,D2),
    cgSameCenterX([D1,D2]),
    D1^bottomY #= D2^y,
    constrainDisks(Fs,Ds,Pans).
constrainDisks([onTable(N,P)|Fs],Ds,Pans):-!,
    arg(N,Ds,D),
    arg(P,Pans,R),
    D^centerX #= R^centerX,
    D^bottomY #= R^bottomY,
    constrainDisks(Fs,Ds,Pans).
constrainDisks([_|Fs],Ds,Pans):-
    constrainDisks(Fs,Ds,Pans).

updateFacts(Fs,move(N,P1,P2),NewFs):-
    moveDiskFromPole(Fs,N,P1,Fs1),
    addDiskToPole(Fs1,N,P2,NewFs).

moveDiskFromPole(Fs,N,P,NewFs):-
    member(on(N,D,P),Fs),!,
    delete(Fs,on(N,_,P),Fs1),
    delete(Fs1,top(N,P),Fs2),
    NewFs=[top(D,P)|Fs2].
moveDiskFromPole(Fs,N,P,NewFs):-
    delete(Fs,top(N,P),Fs1),
    delete(Fs1,onTable(N,P),NewFs).

addDiskToPole(Fs,N,P,NewFs):-
    member(top(D,P),Fs),!,
    delete(Fs,top(_,P),Fs1),
    NewFs=[top(N,P),on(N,D,P)|Fs1].
addDiskToPole(Fs,N,P,NewFs):-
    NewFs=[top(N,P),onTable(N,P)|Fs].
    
createDisks(N0,N,Ds,Pan):-N0>N,!.
createDisks(N0,N,Ds,Pan):-
    createDisk(N0,N,D,Pan),
    arg(N0,Ds,D),
    N1 is N0+1,
    createDisks(N1,N,Ds,Pan).

createDisk(N0,N,D,Pan):-
    cgRectangle(D),
    W #= Pan^width//N,
    H #= Pan^height//N,
    D^width #= W*N0,
    D^height #= H,
    D^color #= gray.

delete([],X,Zs):-!,Zs=[].
delete([X|Xs],X,Zs):-!,Zs=Xs.
delete([X|Xs],Y,[X|Zs1]):-
    delete(Xs,Y,Zs1).