15 puzzle solver/20 Random

The following table shows the result of solving 20 randomly generated 15 puzzles using the C++ imperative solver.
The average number of moves to solve the puzzle is 53, max 61 min 45.
The average time to solve the puzzle is 2.9524 seconds. With one outlier at 29 seconds.

 
0xdab6531480c2e79f	 0.040s	 45	luurdruldlurrrddlldrrulurdlluruldldrdlururdrd
0x92fd74c6810e5a3b	 0.477s	 54	druuulddruuldllurrdldlurdrruuldldrdluldrrruulullddrdrr
0x487c50df9163bea2	 0.174s	 48	drrdllluurdruulldrdrrdllurruullddrdruuulldlddrrr
0x7ab1093458d2e6cf	 0.118s	 47	ddrurdluldruuulddrururddldrululurdruldllurrrddd
0xeb8fc5d3629017a4	29.300s	 61	dluuurdllldrdruuldruulldddrruurddluuurdldrullulddruuldddrurrd
0x4cf92de35786b1a0	 2.818s	 56	ullurullddrdlurrurddlulururdluldrdrdlluuldrrruullldrdrdr
0xce2b170a65d489f3	 0.221s	 51	rddluululddruurdruldllddrruurdllldrruldrruluruldrdd
0x4d87a62950ebcf13	 4.106s	 55	uulddrurullddrrdruuldruuldldrdlluruurdddluulurrdrddlurd
0x45bd378c0e26af19	 3.889s	 56	rrdlurruuldrulldrulldrddluurrulldrdrdruuulldddruldlurrrd
0xf43627518b0ed9ac	 0.277s	 48	lurulldrrrulldrdllurdrrullddrurulullddrrulddrurd
0x7ad568b012ce34f9	 1.603s	 58	luldddluurddruuulddrrdllurruullldddrururulldldrurulldrdrrd
0xa90b16f7452ced38	 4.240s	 52	dlurddluulddrulddrurdruulldlururdruldddluuurddruldrd
0x4fe8a93c76d02b15	 1.835s	 57	ulddlurdruluulldrddruuulddldrruuruldllddrrululurdldrurdrd
0x97fc86d5e2b140a3	 7.038s	 60	ruullurddrrdllururullddldrulurrrullldrdrrullurdddruuuldldrdr
0x35e40ac7f96b21d8	 0.027s	 45	ddruulddruuulddrruulldrddruuldldrurrdlluurrdd
0x5f3a987e4dc2016b	 0.252s	 51	ruldrrurullurddlurdruuldrddlullurddruurulldlurddrrd
0x5872efca06914bd3	 0.951s	 54	rrulddruurddlullurdldrulurrrdlluurdlurrdldrulllurrrddd
0x36fe79ba21d50c84	 0.714s	 57	uurdrurddluurddlluldrulurrurdlulldrdrurddluuuldddrulurdrd
0x48d1b7ca230e659f	 0.079s	 50	rululdlurdlddrruuldrrulurdllurdllurdlddrurullddrrr
0x3c0ba57e6d2f8941	 0.676s	 56	dddruuuldddllurrrululdddrulldruluruldrrurdldrululddldrr

Phix solutions:

First, non-optimal - the following table shows the result of solving the same puzzles using the Phix solver, with MTM=0 and STM=0.
Move counts are listed below as mtm (stm) [stm-optimal from elsewhere (ie above)].
The average number of moves to solve a puzzle is 38.45, max 44 min 29.
The average time to solve a puzzle is none too shabby, but we can soon change that...

{13,10,11,6,5,3,1,4,8,0,12,2,14,7,9,15}   0.25s  33 (53) [45]  lu2r2dlur2d2l3u2r2d3l2ur2ul2drur2uld3lu3r2dldldr2
{9,2,15,13,7,4,12,6,8,1,0,14,5,10,3,11}   1.03s  38 (68) [54]  dru3l2d2r2u2l2d2r2ul3d2r3u2l3dr2u2rdl3ur3dl3drdlu2r2dl2urd2r2
{4,8,7,12,5,0,13,15,9,1,6,3,11,14,10,2}   0.28s  34 (56) [48]  dru2l2d3r3u3l2d2rdru3ld3l2urdlu3r2d2lu2rdld2ruldr2
{7,10,11,1,0,9,3,4,5,8,13,2,14,6,12,15}   3.20s  35 (55) [47]  rdr2ul3dr2u2rd2lu2l2dr2uld3lu3rd3ru3rd3l2urdruldr
{14,11,8,15,12,5,13,3,6,2,9,0,1,7,10,4}   0.92s  44 (79) [61]  u2l3d3r2u3l2d3r2u3l2d3r2u2rd2lu3rd2l2uldr2u2rdl3d2r3ul2u2rd2luruld2rdr
{4,12,15,9,2,13,14,3,5,7,8,6,11,1,10,0}   1.72s  41 (68) [56]  ul2u2ld3ru2r2ul3d3r3u3ld3lur2ul3dr2ul2dr2dlur2dlu3ldlur2drd2
{12,14,2,11,1,7,0,10,6,5,13,4,8,9,15,3}   0.14s  36 (57) [51]  luld2ru2r2d3lu2l2d2r2u3rd2l3dr2uldr2ulu2ldr2dl2u2rd2rd
{4,13,8,7,10,6,2,9,5,0,14,11,12,15,1,3}   0.30s  42 (67) [55]  u2ld2r2dlu2r2ul3d2r3dl3u3rd3rul2ur3dl2ur2ul3d2ru2rdldruldrdr
{4,5,11,13,3,7,8,12,0,14,2,6,10,15,1,9}   0.14s  38 (66) [56]  r2dl2ur3ul2uld2r3u2l3d2r3u2l3dr2d2rul2dr2ul3dr3u2l2dldrur2d
{15,4,3,6,2,7,5,1,8,11,0,14,13,9,10,12}   2.36s  36 (52) [48]  lurul2dr3ul2dr2dl3ur3dlu2l2drd2ru2l2drdru2rdlurd2
{7,10,13,5,6,8,11,0,1,2,12,14,3,4,15,9}   0.31s  42 (62) [58]  l2d2r2u2l2ur2d2l2u2rd3lu2ldr2dl2urdrulu2ldrurd3ru3ldld2rurd
{10,9,0,11,1,6,15,7,4,5,2,12,14,13,3,8}   2.02s  34 (58) [52]  l2d2r2ul2urd3ru3l2d2r3u2l2d3ru3ld2rulurdrd2l3ur2urd2
{4,15,14,8,10,9,3,12,7,6,13,0,2,11,1,5}   0.14s  43 (71) [57]  ulul2d3r2u2l2d2r2u3l2d2r2ul2d2r3u2l3d2r2u2ld2luru2ld2rur2dluruld2rd
{9,7,15,12,8,6,13,5,14,2,11,1,4,0,10,3}   0.50s  44 (70) [60]  lu2r3dl3ur3ul2drdl2u2rd3r2ul2dlu3r2d3lu3rd2ru2ld2rul2d2rurdlurd
{3,5,14,4,0,10,12,7,15,9,6,11,2,1,13,8}   0.06s  29 (45) [45]  d2ru2ld2ru3ld2r2u2l2drd2ru2ldldrur2dl2u2r2d2
{5,15,3,10,9,8,7,14,4,13,12,2,0,1,6,11}   1.88s  40 (59) [51]  rur2ul3d2r3u3ld2lu2ld2ru2ldr3dldrul2dru2rul2d2ruruld2rd
{5,8,7,2,14,15,12,10,0,6,9,1,4,11,13,3}   0.11s  40 (68) [54]  r3uld2l2ur3dl2u2ld2ru3rd3lu3r2d2l3u2r3d2lu2rd2luld2rurdl2ur2d
{3,6,15,14,7,9,11,10,2,1,13,5,0,12,8,4}   0.06s  40 (69) [57]  uruldr3ul3dr3dl3u2r2urd3lu3ld3ru3rd3lu3l2drd2lur2u2ld2ldr3
{4,8,13,1,11,7,12,10,2,3,0,14,6,5,9,15}   0.95s  39 (70) [50]  ul2d2r3ul2u2r2dl3ur3dl3ur2dl2d2ru3rd3lu2ld2r3u3l2d3rulu2rdrd2
{3,12,0,11,10,5,7,14,6,13,2,15,8,9,4,1}   0.45s  41 (66) [56]  l2d3rulur2d2ru3l3d3r3u3ld3rul2dr2u2ldlu2r2dldluruldlur2d3r

STM-optimal solutions are quite a bit slower.. With move counts again shown as mtm (stm) [else]:

{13,10,11,6,5,3,1,4,8,0,12,2,14,7,9,15}   2.42s  38 (45) [45]  lu2rdruldlur3d2l2uldrdr2ulurdl2dlururuldrdrd
{9,2,15,13,7,4,12,6,8,1,0,14,5,10,3,11} 196.23s  38 (54) [54]  ul2ur3dluld2lur2urdld2ru2ldlu2rd3luldr3u2l2uld2rdr2
{4,8,7,12,5,0,13,15,9,1,6,3,11,14,10,2}  46.23s  30 (48) [48]  dr2dl3u2rdru2l2drdr2dl2ur2u2l2d2rdru3l2dld2r3
{7,10,11,1,0,9,3,4,5,8,13,2,14,6,12,15}  71.92s  37 (47) [47]  d2rurdluldru3ld2rururd2ldrululurdruldl2ur3d3
{14,11,8,15,12,5,13,3,6,2,9,0,1,7,10,4} 5.5 hrs! 43 (61) [61]  dlu2l2drdru2ldru2rdlul2d3r2u2rd2lu3rdldrul2uld2ru2ld3rur2d
{4,12,15,9,2,13,14,3,5,7,8,6,11,1,10,0} 657.56s  44 (56) [56]  ul2urul2d2rdlur2urdl2ururdluldrd2ruldlu2ldr3u2l3drdrdr
{12,14,2,11,1,7,0,10,6,5,13,4,8,9,15,3}  48.39s  39 (51) [51]  luld2ruld2rur2dl2ulururdrdl2ururd2l2ururd2lul2d2r3
{4,13,8,7,10,6,2,9,5,0,14,11,12,15,1,3} 462.69s  41 (55) [55]  u2ld2rurul2d2r2dru2ldru2ldldrdl2uru2rd3lu2lur2drd2lurd
{4,5,11,13,3,7,8,12,0,14,2,6,10,15,1,9} 388.74s  40 (56) [56]  r2dl2ur3ul2uld2rururdlul2d2r2uldrdru3l3d2rdruldlur3d
{15,4,3,6,2,7,5,1,8,11,0,14,13,9,10,12}  36.92s  36 (48) [48]  lurul2dr3ul2drdl2urdr2ul2d2rurulul2d2r2uld2rurd
{7,10,13,5,6,8,11,0,1,2,12,14,3,4,15,9}  98.28s  42 (58) [58]  luld3lu2rd2ru2ldr2dl2ur2ulul2d3ruru2rdl3dru2rdluldrdr2d
{10,9,0,11,1,6,15,7,4,5,2,12,14,13,3,8} 421.03s  36 (52) [52]  l2d2rdru2l2drdrurululd3ru3ld2rurul2dr2d2l3ur2urd2
{4,15,14,8,10,9,3,12,7,6,13,0,2,11,1,5} 134.48s  44 (57) [57]  ldlurdru2lul2drd2r2ulu2ld2ldr2u2l2d2r2ululurdldrur2uld2rd
{9,7,15,12,8,6,13,5,14,2,11,1,4,0,10,3} 678.39s  43 (60) [60]  lurur2d2l2u2ldrururd2ldrulu2rd2l2u2r2dld2ru2l3urd3lu2rdrdr
{3,5,14,4,0,10,12,7,15,9,6,11,2,1,13,8}   4.78s  29 (45) [45]  d2ru2ld2ru3ld2r2u2l2drd2ru2ldldrur2dl2u2r2d2
{5,15,3,10,9,8,7,14,4,13,12,2,0,1,6,11}  60.02s  40 (51) [51]  ruldr2urul2urd2lurdru2ldrd2lul2urd2ru2rul2dlurd2r2d
{5,8,7,2,14,15,12,10,0,6,9,1,4,11,13,3}  68.48s  38 (54) [54]  r2ul2drdru2rd2lululd2rulur3dl2u2rdlur2dldrul3ur3d3
{3,6,15,14,7,9,11,10,2,1,13,5,0,12,8,4} 145.20s  43 (57) [57]  u2rdrurd2lu2rd2l3urdlu2r2urdlul2drdrurd2lu3ld3rulurdrd
{4,8,13,1,11,7,12,10,2,3,0,14,6,5,9,15}  17.14s  37 (50) [50]  rulul2druld3r2u2ldr2ulurdl2urdl2urdld2rurul2d2r3
{3,12,0,11,10,5,7,14,6,13,2,15,8,9,4,1} 278.75s  43 (56) [56]  ldld2rur2dluruldl2ur2drdlul2uruldr2urd2lu2rd2lu2ld2ldr3

MTM-optimal solutions take even longer to find, so much so that I only did the first!

puzzle = {13,10,11,6,5,3,1,4,8,0,12,2,14,7,9,15}
mtm-optimal solution of 30 moves found in 2 hours, 13 minutes and 18s: lu2r2d2l2u2r3dl3ur2d3l2ur3ul3drurd2ru3ld2lu2r2d3