The 15 Puzzle is a famous puzzle involving sliding 15 tiles around on a 4x4 grid. Starting from a random configuration, the goal is to arrange the tiles in the correct order. Here is an example of a solved 15 Puzzle:
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15
Each move on the puzzle is of the form Up/Down/Left/Right. The move "Down" consists of sliding the tile that is above the empty spot downward. The move "Right" consists of sliding a tile to the right, into the empty spot. Here is how the board looks after the moves Down and Right.
01 02 03 04
05 06 07 08
09 10 11
13 14 15 12
The goal of this challenge is to write a program that can output the series of moves needed to solve the 15 Puzzle. The winner is the program who solves the five test cases (below) in the fewest total moves. The generated solution does not need to be a perfect solution, it merely has to be better than the competitors. For each individual test case, the program should not take more than ten seconds on a reasonable machine.
Your program must be able to solve any puzzle that is solvable, I'm just using these five test cases as the scoring.
Your program will receive the unsolved 15 Puzzle as input in the format of a 2D array. The 2D array can be formatted according to the language used, or changed if the language does not have 2D arrays. The first element of the first sub-array will be the number in the upper left, and the last element of the first sub-array will be the number in the upper right. A 0 will be the empty space.
As output, your program should print a list of moves in the order that they need to be performed. Each step should be numbered in order to increase the usability of the results.
EDIT: Based on comments, I will allow output to be in either the form of Down/Up/etc or in the form of the coordinates of the piece to move. As this is not code golf, the most important part is to solve the puzzle.
Some other general rules involve no using an outside source, etc.
Test Case 1
([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])
Example Output:
1: Down
2: Down
3: Down
4: Left
....
Test Case 2
([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])
Test Case 3
([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])
Test Case 4
([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])
Test Case 5
([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])
