Your task is to write a program that finds a solution in the fewest moves possible single moves to a random [[wp:15_puzzle|Fifteen Puzzle Game]].<br />
For this task you will be using the following puzzle:<br />
<pre>15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2</pre>
<br />
Solution:<pre>
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0
</pre>

The output must show the moves' directions, like so: left, left, left, down, right... and so on.<br />
There are two solutions, of fifty-two moves:<br>
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd<br>
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd<br>
see: [http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution Pretty Print of Optimal Solution]

Finding either one, or both is an acceptable result.<br>

;Extra credit.
Solve the following problem:
<pre>
  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1
</pre>


;Related Task:
* [[15_Puzzle_Game|15 puzzle game]]
* [[A* search algorithm]]
<br><br>
