% 15_puzzle.pi in Picat % http://dtai.cs.kuleuven.be/events/ASP-competition/Benchmarks/15Puzzle.shtml % by Neng-Fa Zhou and Hakan Kjellerstrand, Nov. 3, 2013 % % use the following OS command to solve an instance file % % picat 15_puzzle < instance_file % % or use the picat top-level command 'test' to solve an included instance % % picat> test % import planner. main => % read facts from stdin test_hard. asp(As) => cl_facts(As,[$in0(-,-,+)]), Board = [[R|C] : I in 0..15, in0(R,C,I)], writeln(Board), maxtime(MaxStep), best_plan(Board,MaxStep,Plan), % plan(Board,MaxStep,Plan), writeln(Plan). /* the final configuration [[ 0,1,2,3], [ 4,5,6,7], [ 8,9,10,11], [12,13,14,15]]). */ % b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 final(State) => State=[[1|1],[1|2],[1|3],[1|4],[2|1],[2|2],[2|3],[2|4],[3|1],[3|2],[3|3],[3|4],[4|1],[4|2],[4|3],[4|4]]. action([P0@[R0|C0]|Board],NextS,Move,Cost) ?=> R1 is R0-1, R1 >= 1, Move=up, Cost=1, P1 = [R1|C0], update(Board,P0,P1,NBoard), NextS=[P1|NBoard]. action([P0@[R0|C0]|Board],NextS,Move,Cost) ?=> R1 is R0+1, R1 =< 4, Move=down, Cost=1, P1 = [R1|C0], update(Board,P0,P1,NBoard), NextS=[P1|NBoard]. action([P0@[R0|C0]|Board],NextS,Move,Cost) ?=> C1 is C0-1, C1 >= 1, Move=left, Cost=1, P1 = [R0|C1], update(Board,P0,P1,NBoard), NextS=[P1|NBoard]. action([P0@[R0|C0]|Board],NextS,Move,Cost) => C1 is C0+1, C1 =< 4, Move=right, Cost=1, P1 = [R0|C1], update(Board,P0,P1,NBoard), NextS=[P1|NBoard]. % Move the empty square from P0 to P1, % this means to move the tile at P1 to P0 update([P1|Tiles],P0,P1,NTiles) => NTiles = [P0|Tiles]. update([Tile|Tiles],P0,P1,NTiles) => NTiles=[Tile|NTiles1], update(Tiles,P0,P1,NTiles1). % the remaining resource (the number of allowed steps) must be greater than the Manhattan distance between the two boards heuristic([_|NBoard]) = Dist => final([_|FBoard]), manhattan_dist(NBoard,FBoard,0,Dist). manhattan_dist([],_,Dist0,Dist) => Dist=Dist0. manhattan_dist([[R1|C1]|Board],[[R2|C2]|NBoard],Dist0,Dist) => manhattan_dist(Board,NBoard,Dist0+abs(R1-R2)+abs(C1-C2),Dist). test => asp($[maxtime(10), in0(1,1,1), in0(1,2,2), in0(1,3,0), in0(1,4,7), in0(2,1,4), in0(2,2,5), in0(2,3,3), in0(2,4,11), in0(3,1,8), in0(3,2,9), in0(3,3,6), in0(3,4,15), in0(4,1,12), in0(4,2,13), in0(4,3,10), in0(4,4,14)]). test1 => asp($[maxtime(14), in0(1,1,1), in0(1,2,5), in0(1,3,2), in0(1,4,7), in0(2,1,8), in0(2,2,4), in0(2,3,3), in0(2,4,11), in0(3,1,0), in0(3,2,9), in0(3,3,6), in0(3,4,15), in0(4,1,12), in0(4,2,13), in0(4,3,10), in0(4,4,14)]). test2 => asp($[maxtime(19), in0(1,1,1), in0(1,2,5), in0(1,3,2), in0(1,4,7), in0(2,1,8), in0(2,2,4), in0(2,3,3), in0(2,4,11), in0(3,1,9), in0(3,2,13), in0(3,3,15), in0(3,4,0), in0(4,1,12), in0(4,2,10), in0(4,3,6), in0(4,4,14)]). test3 => asp($[maxtime(20), in0(1,1,0), in0(1,2,1), in0(1,3,2), in0(1,4,3), in0(2,1,4), in0(2,2,5), in0(2,3,6), in0(2,4,7), in0(3,1,8), in0(3,2,9), in0(3,3,10), in0(3,4,11), in0(4,1,12), in0(4,2,13), in0(4,3,15), in0(4,4,14)]). test4 => asp($[maxtime(35), in0(1,1,4), in0(1,2,0), in0(1,3,3), in0(1,4,6), in0(2,1,12), in0(2,2,1), in0(2,3,11), in0(2,4,7), in0(3,1,9), in0(3,2,5), in0(3,3,10), in0(3,4,15), in0(4,1,13), in0(4,2,8), in0(4,3,14), in0(4,4,2)]). test_hard => asp($[maxtime(40), in0(1,1,4), in0(1,2,6), in0(1,3,2), in0(1,4,1), in0(2,1,12), in0(2,2,0), in0(2,3,9), in0(2,4,3), in0(3,1,10), in0(3,2,8), in0(3,3,15), in0(3,4,7), in0(4,1,14), in0(4,2,13), in0(4,3,5), in0(4,4,11)]).