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


-V
   nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]
   nc = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]
 
T Solver
   n = 0
   np = 0
   n0 = [0] * 100
   n2 = [UInt64(0)] * 100
   n3 = [Char("\0")] * 100
   n4 = [0] * 100
 
   F (values)
      .n0[0] = values.index(0)
 
      UInt64 tmp = 0
      L(val) values
         tmp = (tmp << 4) [|] val
      .n2[0] = tmp
 
   F fI()
      V n = .n
      V g = (11 - .n0[n]) * 4
      V a = .n2[n] [&] (UInt64(15) << g)
      .n0[n + 1] = .n0[n] + 4
      .n2[n + 1] = .n2[n] - a + (a << 16)
      .n3[n + 1] = Char(‘d’)
      .n4[n + 1] = .n4[n] + Int(:nr[Int(a >> g)] > .n0[n] I/ 4)
 
   F fG()
      V n = .n
      V g = (19 - .n0[n]) * 4
      V a = .n2[n] [&] (UInt64(15) << g)
      .n0[n + 1] = .n0[n] - 4
      .n2[n + 1] = .n2[n] - a + (a >> 16)
      .n3[n + 1] = Char(‘u’)
      .n4[n + 1] = .n4[n] + Int(:nr[Int(a >> g)] < .n0[n] I/ 4)
 
   F fE()
      V n = .n
      V g = (14 - .n0[n]) * 4
      V a = .n2[n] [&] (UInt64(15) << g)
      .n0[n + 1] = .n0[n] + 1
      .n2[n + 1] = .n2[n] - a + (a << 4)
      .n3[n + 1] = Char(‘r’)
      .n4[n + 1] = .n4[n] + Int(:nc[Int(a >> g)] > .n0[n] % 4)
 
   F fL()
      V n = .n
      V g = (16 - .n0[n]) * 4
      V a = .n2[n] [&] (UInt64(15) << g)
      .n0[n + 1] = .n0[n] - 1
      .n2[n + 1] = .n2[n] - a + (a >> 4)
      .n3[n + 1] = Char(‘l’)
      .n4[n + 1] = .n4[n] + Int(:nc[Int(a >> g)] < .n0[n] % 4)
 
   F fY()
      I .n2[.n] == 1234'5678'9ABC'DEF0
         R 1B
      I .n4[.n] <= .np
         R .fN()
      R 0B
 
   F fN() -> Bool
      V n = .n
      I .n3[n] != ‘u’ & .n0[n] I/ 4 < 3 {.fI(); .n++; I .fY() {R 1B}; .n--}
      I .n3[n] != ‘d’ & .n0[n] I/ 4 > 0 {.fG(); .n++; I .fY() {R 1B}; .n--}
      I .n3[n] != ‘l’ & .n0[n]  % 4 < 3 {.fE(); .n++; I .fY() {R 1B}; .n--}
      I .n3[n] != ‘r’ & .n0[n]  % 4 > 0 {.fL(); .n++; I .fY() {R 1B}; .n--}
      R 0B
 
   F run()
      L !.fY()
         .np++
      print(‘Solution found with ’(.n)‘ moves: ’, end' ‘’)
      L(g) 1 .. .n
         print(.n3[g], end' ‘’)
      print(‘.’)
 
V solver = Solver([15, 14,  1,  6,
                    9, 11,  4, 12,
                    0, 10,  7,  3,
                   13,  8,  5,  2])
solver.run()