/*********************************************************** sokoban.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import planner. main => Facts = $[size(7,7), wall(2,2), wall(2,3), wall(3,5), wall(5,5), goal(3,3), goal(4,4), goal(4,5), goal(6,5)], cl_facts(Facts,$[wall(+,+), goal(+,+)]), SoLoc = (2,4), BoxLocs = [(2,6),(3,6),(5,2),(6,6)], best_plan_unbounded({SoLoc,BoxLocs},Plan), foreach (Step in Plan) println(Step) end. final({_SoLoc,BoxLocs}) => foreach ((R,C) in BoxLocs) goal(R,C) end. action({SoLoc,BoxLocs},NextS,Action,Cost) ?=> % pull a box NextS = {NewSoLoc,NewBoxLocs}, Action = $pull(BoxLoc,NewBoxLoc,OppDir), Cost=1, neib(SoLoc,BoxLoc,Dir), select(BoxLoc,BoxLocs,BoxLocs1), OppDir = opposite(Dir), neib(SoLoc,PrevLoc,OppDir), not member(PrevLoc,BoxLocs1), choose_move_destination(PrevLoc,BoxLocs1,OppDir,NewSoLoc), neib(NewSoLoc,NewBoxLoc,Dir), insert_ordered(BoxLocs1,NewBoxLoc) = NewBoxLocs. action({SoLoc,BoxLocs},NextS,Action,Cost) => % walk NextS = {NewSoLoc,BoxLocs}, Action = $walk(SoLoc,NewSoLoc,Dir), Cost=1, neib(SoLoc,NextLoc,Dir), not member(NextLoc,BoxLocs), choose_move_destination(NextLoc,BoxLocs,Dir,NewSoLoc). opposite(up) = down. opposite(down) = up. opposite(left) = right. opposite(right) = left. table neib((R,C),Next,Dir) => Next = (R1,C1), Neibs = [(R-1,C,up),(R+1,C,down),(R,C-1,left),(R,C+1,right)], member((R1,C1,Dir),Neibs), size(NRows,NCols), R1 > 1, R1 < NRows, C1 > 1, C1 < NCols, not wall(R1,C1). choose_move_destination(Loc,_BoxLocs,_Dir,Dest) ?=> Dest = Loc. choose_move_destination(Loc,BoxLocs,Dir,Dest) => neib(Loc,NextLoc,Dir), not member(NextLoc,BoxLocs), choose_move_destination(NextLoc,BoxLocs,Dir,Dest).