/*********************************************************** hanoi.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ main => hanoi(3,{[1],[3,2],[]},{[1],[2],[3]},Plan,Len), writeln(plan=Plan), writeln(len=Len). table (+,+,+,-,min) hanoi(0,_CState,_GState,Plan,Len) => Plan=[],Len=0. hanoi(N,{[N|Pi1],Pi2,Pi3},{[N|Pg1],Pg2,Pg3},Plan,Len) => hanoi(N-1,{Pi1,Pi2,Pi3},{Pg1,Pg2,Pg3},Plan,Len). hanoi(N,{Pi1,[N|Pi2],Pi3},{Pg1,[N|Pg2],Pg3},Plan,Len) => hanoi(N-1,{Pi1,Pi2,Pi3},{Pg1,Pg2,Pg3},Plan,Len). hanoi(N,{Pi1,Pi2,[N|Pi3]},{Pg1,Pg2,[N|Pg3]},Plan,Len) => hanoi(N-1,{Pi1,Pi2,Pi3},{Pg1,Pg2,Pg3},Plan,Len). hanoi(1,CState,GState,Plan,Len) => Plan = [\$move(Peg1,Peg2)],Len=1, Peg1 = disk_on_peg(1,CState), Peg2 = disk_on_peg(1,GState). hanoi(N,CState,GState,Plan,Len) => Pni = disk_on_peg(N,CState), Png = disk_on_peg(N,GState), Po = other_peg(Pni,Png), CState1 = remove_btm_disk(CState,Pni), N1 = N-1, IState = {_,_,_}, IState[Po] = [I : I in N1..-1..1], IState[Pni] = [], IState[Png] = [], hanoi(N1,CState1,IState,Plan1,Len1), GState1 = remove_btm_disk(GState,Png), hanoi(N1,IState,GState1,Plan2,Len2), Plan = Plan1 ++ [\$move(Pni,Png)|Plan2], Len = Len1+Len2+1. remove_btm_disk({[_|P1],P2,P3},1) = {P1,P2,P3}. remove_btm_disk({P1,[_|P2],P3},2) = {P1,P2,P3}. remove_btm_disk({P1,P2,[_|P3]},_) = {P1,P2,P3}. disk_on_peg(N,{[N|_],_,_}) = 1. disk_on_peg(N,{_,[N|_],_}) = 2. disk_on_peg(_,_) = 3. other_peg(1,2) = 3. other_peg(1,3) = 2. other_peg(2,1) = 3. other_peg(2,3) = 1. other_peg(3,1) = 2. other_peg(3,2) = 1.