15 puzzle solver/extra credit/solution

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

Move Number: 0; Manhatten Distance: 58; Choose move from rd: d

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

Move Number: 1; Manhatten Distance: 59; Choose move from rud: d

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

Move Number: 2; Manhatten Distance: 58; Choose move from rud: d

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

Move Number: 3; Manhatten Distance: 57; Choose move from ru: r

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

Move Number: 4; Manhatten Distance: 58; Choose move from lru: u

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

Move Number: 5; Manhatten Distance: 59; Choose move from lrud: r

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

Move Number: 6; Manhatten Distance: 58; Choose move from lrud: d

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

Move Number: 7; Manhatten Distance: 57; Choose move from lru: r

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

Move Number: 8; Manhatten Distance: 56; Choose move from lu: u

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

Move Number: 9; Manhatten Distance: 57; Choose move from lud: u

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

Move Number: 10; Manhatten Distance: 56; Choose move from lud: u

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

Move Number: 11; Manhatten Distance: 55; Choose move from ld: l

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

Move Number: 12; Manhatten Distance: 56; Choose move from lrd: l

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

Move Number: 13; Manhatten Distance: 55; Choose move from lrd: l

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

Move Number: 14; Manhatten Distance: 54; Choose move from rd: d

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

Move Number: 15; Manhatten Distance: 53; Choose move from rud: d

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

Move Number: 16; Manhatten Distance: 52; Choose move from rud: r

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

Move Number: 17; Manhatten Distance: 53; Choose move from lrud: u

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

Move Number: 18; Manhatten Distance: 52; Choose move from lrud: l

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

Move Number: 19; Manhatten Distance: 51; Choose move from rud: d

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

Move Number: 20; Manhatten Distance: 50; Choose move from rud: d

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

Move Number: 21; Manhatten Distance: 49; Choose move from ru: r

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

Move Number: 22; Manhatten Distance: 50; Choose move from lru: r

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

Move Number: 23; Manhatten Distance: 49; Choose move from lru: r

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

Move Number: 24; Manhatten Distance: 48; Choose move from lu: u

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

Move Number: 25; Manhatten Distance: 47; Choose move from lud: u

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

Move Number: 26; Manhatten Distance: 46; Choose move from lud: u

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

Move Number: 27; Manhatten Distance: 45; Choose move from ld: l

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

Move Number: 28; Manhatten Distance: 44; Choose move from lrd: l

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

Move Number: 29; Manhatten Distance: 43; Choose move from lrd: d

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

Move Number: 30; Manhatten Distance: 42; Choose move from lrud: d

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

Move Number: 31; Manhatten Distance: 43; Choose move from lrud: r

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

Move Number: 32; Manhatten Distance: 42; Choose move from lrud: u

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

Move Number: 33; Manhatten Distance: 41; Choose move from lrud: u

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

Move Number: 34; Manhatten Distance: 40; Choose move from lrd: l

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

Move Number: 35; Manhatten Distance: 39; Choose move from lrd: l

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

Move Number: 36; Manhatten Distance: 38; Choose move from rd: d

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

Move Number: 37; Manhatten Distance: 37; Choose move from rud: d

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

Move Number: 38; Manhatten Distance: 36; Choose move from rud: d

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

Move Number: 39; Manhatten Distance: 35; Choose move from ru: r

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

Move Number: 40; Manhatten Distance: 34; Choose move from lru: r

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

Move Number: 41; Manhatten Distance: 33; Choose move from lru: u

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

Move Number: 42; Manhatten Distance: 34; Choose move from lrud: r

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

Move Number: 43; Manhatten Distance: 33; Choose move from lud: u

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

Move Number: 44; Manhatten Distance: 32; Choose move from lud: l

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

Move Number: 45; Manhatten Distance: 33; Choose move from lrud: l

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

Move Number: 46; Manhatten Distance: 32; Choose move from lrud: d

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

Move Number: 47; Manhatten Distance: 31; Choose move from lrud: r

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

Move Number: 48; Manhatten Distance: 30; Choose move from lrud: r

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

Move Number: 49; Manhatten Distance: 29; Choose move from lud: u

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

Move Number: 50; Manhatten Distance: 28; Choose move from lud: u

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

Move Number: 51; Manhatten Distance: 27; Choose move from ld: l

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

Move Number: 52; Manhatten Distance: 26; Choose move from lrd: l

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

Move Number: 53; Manhatten Distance: 25; Choose move from lrd: d

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

Move Number: 54; Manhatten Distance: 26; Choose move from lrud: l

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

Move Number: 55; Manhatten Distance: 25; Choose move from rud: d

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

Move Number: 56; Manhatten Distance: 24; Choose move from rud: d

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

Move Number: 57; Manhatten Distance: 23; Choose move from ru: r

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

Move Number: 58; Manhatten Distance: 22; Choose move from lru: u

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

Move Number: 59; Manhatten Distance: 21; Choose move from lrud: r

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

Move Number: 60; Manhatten Distance: 20; Choose move from lrud: u

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

Move Number: 61; Manhatten Distance: 19; Choose move from lrud: l

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

Move Number: 62; Manhatten Distance: 18; Choose move from lrud: l

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

Move Number: 63; Manhatten Distance: 17; Choose move from rud: d

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

Move Number: 64; Manhatten Distance: 16; Choose move from rud: d

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

Move Number: 65; Manhatten Distance: 15; Choose move from ru: r

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

Move Number: 66; Manhatten Distance: 14; Choose move from lru: r

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

Move Number: 67; Manhatten Distance: 13; Choose move from lru: r

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

Move Number: 68; Manhatten Distance: 12; Choose move from lu: u

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

Move Number: 69; Manhatten Distance: 11; Choose move from lud: u

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

Move Number: 70; Manhatten Distance: 10; Choose move from lud: l

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

Move Number: 71; Manhatten Distance: 9; Choose move from lrud: l

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

Move Number: 72; Manhatten Distance: 8; Choose move from lrud: u

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

Move Number: 73; Manhatten Distance: 7; Choose move from lrd: l

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

Move Number: 74; Manhatten Distance: 6; Choose move from rd: d

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

Move Number: 75; Manhatten Distance: 5; Choose move from rud: d

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

Move Number: 76; Manhatten Distance: 4; Choose move from rud: r

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

Move Number: 77; Manhatten Distance: 3; Choose move from lrud: d

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

Move Number: 78; Manhatten Distance: 2; Choose move from lru: r

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

Move Number: 79; Manhatten Distance: 1; Choose move from lru: r

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

Solved in 80 moves