Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game.

For this task you will be using the following puzzle:


15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2


 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.

There are two solutions, of fifty-two moves:

rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd

see: Pretty Print of Optimal Solution

Finding either one, or both is an acceptable result.


Extra credit.
Solve the following problem:

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1



Related Task

 15 puzzle game
 A* search algorithm


import planner.
 
main =>
    init(InitS),
    goal(GoalS),
    best_plan((InitS,GoalS),Plan),
    println(Plan).
 
init(InitS) =>
    M = {{15, 14, 1,  6},
         {9 , 11, 4, 12},
         {0,  10, 7,  3},
         {13,  8, 5,  2}},
    InitS = [(R,C) : T in 0..15, pos(M,T,R,C)].
 
goal(GoalS) =>
    M = {{1,  2,  3,  4},
         {5,  6,  7,  8},
         {9, 10, 11, 12},
         {13,14, 15,  0}},
    GoalS = [(R,C) : T in 0..15, pos(M,T,R,C)].         
 
pos(M,T,R,C) =>
    N = len(M),
    between(1,N,R),
    between(1,N,C),
    M[R,C] == T,!.
 
final((S,GoalS)) => S == GoalS.
 
action((S,GoalS),NextS,Action,Cost) =>
    S = [P0|Tiles],
    P0 = (R0,C0),
    Cost = 1,
    (R1 = R0-1, R1 >= 1, C1 = C0, Action = u;
     R1 = R0+1, R1 =< 4, C1 = C0, Action = d;
     R1 = R0, C1 = C0-1, C1 >= 1, Action = l;
     R1 = R0, C1 = C0+1, C1 =< 4, Action = r),
    P1 = (R1,C1),
    slide(P0,P1,Tiles,Tiles1),
    S1 = [P1|Tiles1],
    NextS = (S1,GoalS).
 
% slide the tile at P1 to the empty square at P0
slide(P0,P1,[P1|Tiles],Tiles1) =>
    Tiles1 = [P0|Tiles].
slide(P0,P1,[Tile|Tiles],Tiles1) =>
    Tiles1=[Tile|Tiles1R],
    slide(P0,P1,Tiles,Tiles1R).
 
% called by the planner
heuristic((S,GoalS)) = Dist =>
    S = [_|Tiles],
    GoalS = [_|FTiles],
    Dist = sum([abs(R-FR)+abs(C-FC) : 
                {(R,C),(FR,FC)} in zip(Tiles,FTiles)]).
 
 