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.
time n _n
0xdab6531480c2e79f 0.040s 45 6 luurdruldlurrrddlldrrulurdlluruldldrdlururdrd
0x92fd74c6810e5a3b 0.477s 54 8 druuulddruuldllurrdldlurdrruuldldrdluldrrruulullddrdrr
0x487c50df9163bea2 0.174s 48 7 drrdllluurdruulldrdrrdllurruullddrdruuulldlddrrr
0x7ab1093458d2e6cf 0.118s 47 8 ddrurdluldruuulddrururddldrululurdruldllurrrddd
0xeb8fc5d3629017a4 29.300s 61 10 dluuurdllldrdruuldruulldddrruurddluuurdldrullulddruuldddrurrd
0x4cf92de35786b1a0 2.818s 56 7 ullurullddrdlurrurddlulururdluldrdrdlluuldrrruullldrdrdr
0xce2b170a65d489f3 0.221s 51 7 rddluululddruurdruldllddrruurdllldrruldrruluruldrdd
0x4d87a62950ebcf13 4.106s 55 9 uulddrurullddrrdruuldruuldldrdlluruurdddluulurrdrddlurd
0x45bd378c0e26af19 3.889s 56 9 rrdlurruuldrulldrulldrddluurrulldrdrdruuulldddruldlurrrd
0xf43627518b0ed9ac 0.277s 48 8 lurulldrrrulldrdllurdrrullddrurulullddrrulddrurd
0x7ad568b012ce34f9 1.603s 58 9 luldddluurddruuulddrrdllurruullldddrururulldldrurulldrdrrd
0xa90b16f7452ced38 4.240s 52 11 dlurddluulddrulddrurdruulldlururdruldddluuurddruldrd
0x4fe8a93c76d02b15 1.835s 57 8 ulddlurdruluulldrddruuulddldrruuruldllddrrululurdldrurdrd
0x97fc86d5e2b140a3 7.038s 60 10 ruullurddrrdllururullddldrulurrrullldrdrrullurdddruuuldldrdr
0x35e40ac7f96b21d8 0.027s 45 7 ddruulddruuulddrruulldrddruuldldrurrdlluurrdd
0x5f3a987e4dc2016b 0.252s 51 7 ruldrrurullurddlurdruuldrddlullurddruurulldlurddrrd
0x5872efca06914bd3 0.951s 54 7 rrulddruurddlullurdldrulurrrdlluurdlurrdldrulllurrrddd
0x36fe79ba21d50c84 0.714s 57 8 uurdrurddluurddlluldrulurrurdlulldrdrurddluuuldddrulurdrd
0x48d1b7ca230e659f 0.079s 50 4 rululdlurdlddrruuldrrulurdllurdllurdlddrurullddrrr
0x3c0ba57e6d2f8941 0.676s 56 7 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