/*********************************************************** klotski.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import planner. main => initial(S0), best_plan_unbounded(S0,Plan), foreach (Step in Plan) println(Step) end, println(len=length(Plan)). initial(S) => S = {[(5,2), (5,3)], % empty spaces sort([{(2,2),(1,2)}, % one 2 x 2 piece {(2,1),(3,2)}, % one 2 x 1 piece {(1,2),(1,1)}, % four 1 x 2 pieces {(1,2),(3,1)}, {(1,2),(1,4)}, {(1,2),(3,4)}, {(1,1),(5,1)}, % four 1 x 1 pieces {(1,1),(4,2)}, {(1,1),(4,3)}, {(1,1),(5,4)}])}. final({_,Pieces}), member({(2,2),(4,2)},Pieces) => true. action({Spaces,Pieces},NextS,Action,Cost) => Cost = 1, select({Dim,Pos},Pieces,Pieces1), move_piece(Spaces,Dim,Pos,NSpaces,NPos,Action), NextS = {NSpaces,insert_ordered(Pieces1,{Dim,NPos})}. move_piece(Spaces,D@(W,H),P@(R,C),NSpaces,NP,Action) ?=> Action = \$move(D,P,left), C1 = C-1, NP = (R,C1), if H==1 then select((R,C1),Spaces,SpacesR), NSpaces = insert_ordered(SpacesR,(R,C1+W)) else Spaces = [(R,C1),(R+1,C1)], NSpaces = [(R,C1+W),(R+1,C1+W)] end. move_piece(Spaces,D@(W,H),P@(R,C),NSpaces,NP,Action) ?=> Action = \$move(D,P,right), C1 = C+1, NP = (R,C1), if H==1 then select((R,C+W),Spaces,SpacesR), NSpaces = insert_ordered(SpacesR,(R,C)) else Spaces = [(R,C+W),(R+1,C+W)], NSpaces = [(R,C),(R+1,C)] end. move_piece(Spaces,D@(W,H),P@(R,C),NSpaces,NP,Action) ?=> Action = \$move(D,P,up), R1 = R-1, NP = (R1,C), if W==1 then select((R1,C),Spaces,SpacesR), NSpaces = insert_ordered(SpacesR,(R1+H,C)) else Spaces = [(R1,C),(R1,C+1)], NSpaces = [(R1+H,C),(R1+H,C+1)] end. move_piece(Spaces,D@(W,H),P@(R,C),NSpaces,NP,Action) => Action = \$move(D,P,down), R1 = R+1, NP = (R1,C), if W==1 then select((R+H,C),Spaces,SpacesR), NSpaces = insert_ordered(SpacesR,(R,C)) else Spaces = [(R+H,C),(R+H,C+1)], NSpaces = [(R,C),(R,C+1)] end.