15 puzzle solver/Optimal solution

Solution in 52 moves:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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