% klotski.pi in Picat % Solving the Klotski (Huarong Dao in Chinese) sliding puzzle % This problem is also called the Red Donkey problem % by Neng-Fa Zhou, Nov. 8, 2013. import planner. main => initial(S0), best_plan(S0,Plan,PlanLen), writeln(Plan), writeln(len=PlanLen). % The initial state (X-axis left-to-right, Y-axis up-to-down initial(S) => S = [[(2,5),(3,5)], % free spaces at (2,5) and (3,5) (2,1), % the 2*2 piece at (2,1) (2,3), % the 2*1 piece at (2,3) [(1,1),(1,3),(4,1),(4,3)], % the locations of the four 1*2 pieces [(1,5),(2,4),(3,4),(4,5)]]. % the locations of the four 1*1 pieces % The final state final([_,(2,4)|_]) => true. % the largest piece is at (2,4), so it can be slid out at the next move % Moves action([Spaces,P22|T],NS,Action,Cost) ?=> % move the 2*2 piece Cost=1, move_piece(2,2,P22,NP22,Spaces,Spaces1,Action), NS=[Spaces1,NP22|T]. action([Spaces,P22,P21|T],NS,Action,Cost) ?=> % move the 2*1 piece Cost=1, move_piece(2,1,P21,NP21,Spaces,Spaces1,Action), NS=[Spaces1,P22,NP21|T]. action([Spaces,P22,P21,P12L|T],NS,Action,Cost) ?=> % select a 1*2 piece to move Cost=1, select(P12,P12L,P12LR), move_piece(1,2,P12,NP12,Spaces,Spaces1,Action), NP12L = insert_ordered(P12LR,NP12), NS=[Spaces1,P22,P21,NP12L|T]. action([Spaces,P22,P21,P12L,P11L],NS,Action,Cost) => % select a 1*1 piece to move Cost=1, select(P11,P11L,P11LR), move_piece(1,1,P11,NP11,Spaces,Spaces1,Action), NP11L = insert_ordered(P11LR,NP11), NS=[Spaces1,P22,P21,P12L,NP11L]. % Move a piece of size W*H from P to NP. After this move, Spaces becomes Spaces1 move_piece(2,H,P@(X,Y),NP,[(X,Y1),(X1,Y1)],Spaces1,Action),X1==X+1, Y==Y1+1 ?=> Action = \$move(2*H,P,up), NP = (X,Y1), Spaces1 =[(X,Y1+H),(X1,Y1+H)]. move_piece(2,H,P@(X,Y),NP,[(X,Y1),(X1,Y1)],Spaces1,Action),X1==X+1, Y1==Y+H ?=> Action = \$move(2*H,P,down), NP = (X,Y+1), Spaces1 =[(X,Y),(X1,Y)]. move_piece(W,2,P@(X,Y),NP,[(X1,Y),(X1,Y1)],Spaces1,Action),Y1==Y+1,X==X1+1 ?=> Action = \$move(W*2,P,left), NP = (X1,Y), Spaces1 =[(X1+W,Y),(X1+W,Y1)]. move_piece(W,2,P@(X,Y),NP,[(X1,Y),(X1,Y1)],Spaces1,Action),X1==X+W,Y1==Y+1 ?=> Action = \$move(W*2,P,right), NP = (X+1,Y), Spaces1 =[(X,Y),(X,Y1)]. % move_piece(1,H,P@(X,Y),NP,Spaces,Spaces1,Action) ?=> Space=(X,Y1), select(Space,Spaces,SpacesR), Y == Y1+1, Action = \$move(1*H,P,up), NP = (X,Y1), Spaces1 = insert_ordered(SpacesR,(X,Y1+H)). move_piece(1,H,P@(X,Y),NP,Spaces,Spaces1,Action) ?=> Space=(X,Y1), select(Space,Spaces,SpacesR), Y1 == Y+H, Action = \$move(1*H,P,down), NP = (X,Y+1), Spaces1 = insert_ordered(SpacesR,(X,Y)). move_piece(W,1,P@(X,Y),NP,Spaces,Spaces1,Action) ?=> Space=(X1,Y), select(Space,Spaces,SpacesR), X1+1 == X, Action = \$move(W*1,P,left), NP = (X1,Y), Spaces1 = insert_ordered(SpacesR,(X1+W,Y)). move_piece(W,1,P@(X,Y),NP,Spaces,Spaces1,Action) => Space=(X1,Y), select(Space,Spaces,SpacesR), X+W == X1, Action = \$move(W*1,P,right), NP = (X+1,Y), Spaces1 = insert_ordered(SpacesR,(X,Y)).