cube files
Indexed Cube Lovers Archive
One Million Random Twenty-Four Puzzle Instances in the STM metric
Submitted by stannic on Sun, 10/07/2012 - 07:56.
I have solved sub-optimally 1,000,000 random instances of 5x5 sliding tile puzzle in STM metric (single-tile moves). The actual running time was about 18,5 hours. The minimum, maximum and average solution length were 73, 171 and 124.48 moves respectively. About 52% of 1,000,000 solutions were in range [118; 132]. There were only 32 instances with (suboptimal) solution length less than 81 (range [73; 80]). Only one instance was solved in 171 moves.
The suboptimal solver (kumi na tano 3.10 in batch mode) uses four phases as on the diagram below.
1 1 1 1 1 2 3 3 3 3 2 3 4 4 4 2 3 4 4 4 2 3 4 4 x
Along with this scheme, mirror reflection through main diagonal was also used. The program was allowed only to optimal solutions on each phase (the "slackness" value was limited to 0).
The header of the report is given below. The full report from batch solver can be downloaded from (7z archive) or (zip archive). The archive contains two text files: report.txt is the report, and instances.txt is just list of all solved configurations without any additional information. The archive expands to about 200 MB.
Puzzle: 5 x 5
Move metric: STM
Start search at: off
Stop search at: off
Start with slackness: off
Stop at slackness: 1
Time limit: off
Right turns only: off
Instances Solved: 1000000
Total Time: 67102.171 s
Average Time: 67.102 ms
Min. Length: 73
Max. Length: 171
Average Length: 124.4809
Total rNodes: 1505742903
Average rNodes: 1505.7429
length count
73 2
74 4
75 2
76 4
77 4
78 5
79 7
80 4
81 17
82 24
83 26
84 46
85 66
86 96
87 97
88 154
89 173
90 304
91 331
92 515
93 530
94 745
95 873
96 1196
97 1428
98 1926
99 2260
100 2882
101 3367
102 4293
103 4814
104 5996
105 6722
106 8557
107 9025
108 11264
109 11948
110 14706
111 15629
112 18661
113 19246
114 23049
115 23429
116 27506
117 27353
118 31613
119 30715
120 35137
121 33700
122 37859
123 35612
124 39417
125 36343
126 39202
127 35806
128 38200
129 33875
130 35289
131 31161
132 31747
133 27451
134 27206
135 23205
136 22558
137 18707
138 17872
139 14648
140 13744
141 10780
142 9897
143 7697
144 6765
145 5214
146 4616
147 3453
148 2849
149 2078
150 1777
151 1167
152 956
153 661
154 522
155 373
156 298
157 166
158 141
159 65
160 61
161 48
162 23
163 20
164 4
165 5
166 6
167 2
168 2
171 1
I have attempted to run the same batch in MTM metric; however, the number of alternative optimal solutions for each phase in this metric is significantly larger, and each instance requires 20 seconds in average to finish search with slackness = 0 (compared to 67 milliseconds in STM metric). So I've solved only 100 random instances in MTM metric with the same settings (searching only for optimal solutions for each phase). Results are given below.
Puzzle: 5 x 5
Move metric: MTM
Start search at: off
Stop search at: off
Start with slackness: off
Stop at slackness: 1
Time limit: off
Right turns only: off
Instances Solved: 100
Total Time: 2001.022 s
Average Time: 20.010 s
Min. Length: 49
Max. Length: 72
Average Length: 64.3000
Total rNodes: 808429478
Average rNodes: 8084294.7800
length count
49 1
57 5
58 6
59 3
60 2
61 8
62 11
63 6
64 7
65 12
66 7
67 7
68 8
69 6
70 1
71 4
72 6
Goal configuration: Blank Last 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0
Regions (6):
A fixed tiles: { }, current tiles: { 1 2 3 4 5 }
B fixed tiles: { 1 2 3 4 5 }, current tiles: { 6 11 16 21 }
C fixed tiles: { }, current tiles: { 1 6 11 16 21 }
D fixed tiles: { 1 6 11 16 21 }, current tiles: { 2 3 4 5 }
E fixed tiles: { 1 2 3 4 5 6 11 16 21 }, current tiles: { 7 8 9 10 12 17 22 }
F fixed tiles: { 1 2 3 4 5 6 7 8 9 10 11 12 16 17 21 22 }, current tiles: { 13 14 15 18 19 23 }
Chains (2):
[A,B,E,F] 45
[C,D,E,F] 55
# Instance Length Time, ms rNodes Chain
1 17 10 16 4 7 14 19 1 20 5 24 8 6 22 21 9 13 3 18 12 15 23 2 11 0 68 15625 2364109 [A,B,E,F]
2 19 5 4 20 9 22 14 21 17 6 10 24 1 3 12 8 16 11 2 13 0 23 15 7 18 66 4516 329536 [C,D,E,F]
3 9 14 2 6 22 4 13 18 7 16 20 5 10 8 24 23 17 21 12 0 11 19 1 15 3 72 10890 3288922 [C,D,E,F]
4 23 16 5 3 12 6 18 7 24 10 19 17 9 20 8 0 1 13 15 4 21 22 14 2 11 63 81734 30454580 [C,D,E,F]
5 1 6 14 12 15 24 22 13 16 7 0 8 19 18 20 2 3 23 11 10 17 21 4 9 5 66 2344 862938 [A,B,E,F]
6 17 23 12 14 22 10 2 19 15 7 18 4 6 3 21 1 13 16 20 0 8 5 11 9 24 64 10547 3321975 [A,B,E,F]
7 5 20 10 17 7 6 11 13 12 8 9 4 3 2 16 24 21 15 22 19 0 1 14 23 18 64 63281 25227109 [A,B,E,F]
8 18 0 5 13 15 17 24 21 9 19 11 22 6 7 14 2 8 16 12 4 23 10 20 3 1 68 4266 1942328 [C,D,E,F]
9 20 12 8 23 16 6 7 14 19 2 0 18 21 17 13 22 10 1 3 11 24 9 5 4 15 65 4844 1301122 [A,B,E,F]
10 22 16 14 21 19 20 2 17 5 3 4 13 12 18 15 10 11 0 9 23 8 6 24 1 7 72 2265 264099 [C,D,E,F]
11 5 10 13 0 3 17 9 4 6 8 18 7 2 19 15 20 14 12 21 23 11 16 22 1 24 57 50484 20508436 [C,D,E,F]
12 15 23 7 2 4 17 24 5 16 0 19 10 8 13 14 9 12 11 1 3 22 6 20 21 18 65 16422 4338673 [A,B,E,F]
13 7 16 21 19 9 4 13 5 6 8 10 24 14 20 23 17 3 2 0 18 12 1 11 15 22 61 1453 543453 [A,B,E,F]
14 14 8 11 7 17 1 23 13 15 0 12 16 22 6 10 18 4 21 3 19 9 5 2 24 20 58 67641 20815945 [C,D,E,F]
15 17 2 0 24 18 12 23 5 3 13 15 22 14 6 7 4 21 1 19 20 8 10 16 11 9 62 3390 579982 [C,D,E,F]
16 18 11 23 1 5 16 17 2 0 4 20 3 12 10 9 22 24 6 14 15 21 19 13 8 7 49 422 85282 [A,B,E,F]
17 2 0 11 16 9 19 23 10 8 4 5 12 15 20 13 18 21 6 3 14 7 22 24 1 17 66 4547 1215456 [A,B,E,F]
18 21 24 8 20 14 11 12 10 0 22 2 6 7 5 23 9 4 19 3 13 18 15 16 17 1 67 4953 1086766 [A,B,E,F]
19 6 17 0 4 7 13 22 14 16 23 19 2 1 5 20 21 24 3 10 12 11 8 9 18 15 58 10937 4702300 [A,B,E,F]
20 4 3 14 2 11 12 20 21 15 17 16 13 5 22 18 8 6 10 9 7 19 0 1 24 23 68 484 78615 [A,B,E,F]
21 21 19 17 15 24 13 11 3 4 20 0 10 6 7 12 5 14 16 9 1 18 23 2 22 8 64 61734 28688899 [A,B,E,F]
22 1 5 24 4 14 22 6 16 2 3 0 17 19 9 10 18 11 15 23 7 13 21 8 20 12 57 266 19261 [C,D,E,F]
23 24 14 0 12 6 3 4 1 19 17 23 16 2 15 11 18 10 20 5 9 22 21 13 8 7 63 3453 736051 [C,D,E,F]
24 23 21 10 3 24 4 0 5 11 18 9 22 14 13 6 1 19 16 12 17 7 15 20 8 2 69 14469 2403736 [C,D,E,F]
25 11 18 9 12 1 20 4 17 10 5 13 8 0 6 19 21 14 2 15 16 22 24 7 3 23 59 5500 1645635 [C,D,E,F]
26 2 10 21 13 12 11 17 4 1 23 14 16 18 19 8 24 3 0 5 15 6 9 7 22 20 61 1782 837255 [C,D,E,F]
27 16 6 10 2 21 23 15 20 17 0 24 7 1 4 19 13 9 5 11 12 8 18 3 22 14 61 36156 16022992 [A,B,E,F]
28 19 9 15 0 22 6 21 16 14 18 12 1 4 17 3 13 10 23 7 11 24 2 20 5 8 66 469 204538 [C,D,E,F]
29 0 7 8 2 22 12 20 23 5 16 3 15 17 6 10 19 13 21 9 18 1 14 4 11 24 66 11546 4913908 [C,D,E,F]
30 13 11 3 14 22 24 19 8 17 21 1 4 9 0 15 18 6 7 12 16 10 2 5 23 20 62 17687 8755985 [A,B,E,F]
31 9 5 24 19 2 13 18 10 6 14 12 22 23 4 7 0 16 21 3 8 11 20 1 15 17 63 14625 5705597 [C,D,E,F]
32 17 6 21 16 1 5 18 19 4 15 2 14 12 23 7 8 10 3 9 11 0 22 13 24 20 62 60906 24395670 [A,B,E,F]
33 7 16 17 6 18 14 21 20 11 0 24 10 12 23 4 9 3 8 5 15 19 2 1 22 13 65 63313 24722577 [C,D,E,F]
34 7 8 0 23 21 15 20 22 3 6 2 19 24 10 14 16 17 11 18 9 5 1 4 13 12 66 274625 111291709 [C,D,E,F]
35 8 11 24 6 1 10 14 13 15 19 5 0 7 18 16 9 22 23 2 20 17 12 21 3 4 64 8735 3240705 [A,B,E,F]
36 9 3 23 13 21 18 1 19 14 4 8 20 22 5 15 6 24 10 11 7 12 2 0 17 16 61 3500 1131400 [A,B,E,F]
37 5 16 15 2 21 19 17 22 6 8 4 13 1 23 7 18 24 10 9 20 11 12 0 3 14 65 60016 26948453 [C,D,E,F]
38 1 20 18 7 24 16 10 9 3 2 21 11 5 12 0 19 4 13 6 14 17 23 8 22 15 57 2391 789338 [C,D,E,F]
39 9 17 13 6 19 8 15 16 21 14 23 5 11 7 22 18 2 0 4 24 3 10 1 12 20 61 2235 978543 [A,B,E,F]
40 15 1 3 20 21 7 18 6 5 0 24 17 9 11 10 13 23 12 19 8 4 16 2 14 22 67 12672 5648079 [C,D,E,F]
41 2 1 8 23 21 4 5 11 6 18 17 22 12 14 0 16 19 7 3 15 13 9 24 20 10 62 5391 1979476 [A,B,E,F]
42 20 2 24 19 18 5 6 0 3 23 4 8 9 11 7 22 10 15 12 13 14 1 17 21 16 58 7062 2267176 [C,D,E,F]
43 7 11 1 6 16 14 23 0 18 21 5 4 15 24 22 10 9 19 17 20 2 13 3 8 12 71 66031 34794500 [C,D,E,F]
44 15 9 20 10 18 22 17 5 8 7 11 0 3 4 23 24 13 12 6 2 14 21 1 16 19 65 5750 989661 [A,B,E,F]
45 17 23 2 14 12 4 6 11 0 20 9 21 15 10 16 5 19 18 13 24 8 3 22 1 7 65 8781 4018920 [C,D,E,F]
46 24 9 22 3 8 18 11 19 21 2 5 6 15 7 1 0 10 16 17 12 4 23 20 13 14 71 19578 7299144 [A,B,E,F]
47 11 10 4 14 0 18 20 21 2 23 12 5 8 9 13 3 24 15 19 7 6 1 22 17 16 67 1187 139938 [A,B,E,F]
48 3 23 9 2 10 18 12 14 15 8 17 19 0 1 22 5 13 24 11 20 6 4 21 16 7 63 5578 2752704 [C,D,E,F]
49 1 20 12 5 6 23 2 9 22 7 11 17 18 0 19 8 4 16 3 21 24 10 13 15 14 61 1860 438761 [C,D,E,F]
50 4 0 21 13 14 8 19 11 9 7 1 6 2 16 23 15 12 3 20 24 10 18 22 17 5 62 20719 9676830 [C,D,E,F]
51 10 4 23 3 1 8 0 16 7 9 21 11 18 22 17 2 13 24 14 5 6 12 19 15 20 62 2344 993458 [C,D,E,F]
52 15 18 11 0 13 14 23 1 2 19 7 3 12 4 5 8 16 21 20 24 17 6 22 10 9 59 2047 607672 [A,B,E,F]
53 15 9 24 6 21 5 8 13 17 12 22 14 19 18 16 20 3 10 0 1 4 2 23 7 11 69 126422 61608710 [A,B,E,F]
54 19 5 23 10 0 17 8 9 18 4 6 2 1 22 7 21 11 16 12 24 3 13 20 14 15 57 1328 199642 [C,D,E,F]
55 3 2 1 23 17 9 19 8 6 12 5 0 13 22 24 18 7 11 10 20 15 21 4 16 14 66 7047 1471169 [A,B,E,F]
56 7 16 3 4 0 12 8 18 6 19 23 21 1 13 2 10 9 17 20 15 24 11 22 5 14 62 297 51387 [C,D,E,F]
57 1 20 3 2 8 15 13 12 21 22 5 23 19 10 11 0 24 9 7 16 4 17 18 6 14 68 7656 3334984 [A,B,E,F]
58 1 5 24 23 13 18 9 8 17 14 16 11 2 6 15 20 10 22 7 3 21 4 12 0 19 58 218 23925 [C,D,E,F]
59 4 13 20 21 16 10 15 6 23 1 2 19 14 12 11 3 22 7 17 24 9 5 0 8 18 65 38860 9974118 [C,D,E,F]
60 22 4 24 16 13 12 2 1 18 3 5 10 11 15 23 14 6 8 19 0 20 7 17 9 21 68 1375 143252 [A,B,E,F]
61 13 9 5 8 7 18 14 15 17 20 3 1 16 19 21 2 6 23 22 10 11 24 4 0 12 61 2672 1006829 [C,D,E,F]
62 3 24 21 19 15 22 0 14 11 10 5 1 13 9 16 6 17 23 8 2 4 12 20 7 18 68 2765 977561 [C,D,E,F]
63 8 22 0 24 23 20 10 17 1 6 11 21 9 5 14 4 7 15 12 16 2 13 18 3 19 70 7485 1241101 [A,B,E,F]
64 21 5 24 12 2 22 14 3 6 15 16 11 9 4 10 8 18 20 23 1 17 13 19 7 0 64 4188 523962 [C,D,E,F]
65 17 4 1 18 11 16 9 21 7 24 3 15 2 8 14 19 12 6 23 0 20 10 13 22 5 62 5547 1796898 [A,B,E,F]
66 20 4 23 15 12 21 24 7 8 18 2 1 22 6 19 5 14 0 3 9 10 16 17 13 11 69 15094 1793012 [C,D,E,F]
67 23 15 14 12 1 3 8 11 22 24 6 21 10 4 9 2 17 7 5 0 19 20 13 16 18 64 9062 1430957 [C,D,E,F]
68 7 6 17 4 9 0 21 2 12 20 10 1 15 8 3 11 13 23 16 14 18 5 24 22 19 58 734 73969 [A,B,E,F]
69 10 16 4 15 18 0 6 11 22 24 8 3 1 13 9 17 7 19 12 14 21 5 23 20 2 65 922 100400 [C,D,E,F]
70 10 19 18 0 6 5 3 17 2 13 9 22 21 11 16 24 23 1 15 8 20 4 12 7 14 68 1094 244580 [C,D,E,F]
71 17 22 15 21 0 8 9 6 4 5 16 1 11 19 2 12 7 23 20 10 24 18 14 13 3 58 54766 26183863 [C,D,E,F]
72 5 7 6 11 14 17 3 1 24 0 4 9 2 23 13 22 16 21 15 12 18 20 10 19 8 59 2562 1011956 [A,B,E,F]
73 7 16 5 21 10 1 12 9 15 24 8 14 23 19 18 13 2 6 3 0 20 17 22 4 11 60 20875 7108795 [A,B,E,F]
74 13 7 19 24 4 23 15 18 22 5 21 16 3 14 11 1 17 10 2 9 0 6 8 12 20 65 1469 319130 [A,B,E,F]
75 20 3 0 15 23 1 12 13 5 10 8 22 21 6 11 2 7 14 24 17 9 16 18 19 4 61 3704 1241366 [A,B,E,F]
76 7 21 24 8 9 16 10 6 11 23 2 0 15 12 17 3 4 22 1 5 20 19 18 13 14 68 1579 223532 [C,D,E,F]
77 18 20 19 10 12 23 8 11 24 5 0 16 17 4 15 22 2 9 6 13 7 21 14 3 1 69 3079 625239 [C,D,E,F]
78 23 15 14 6 4 20 17 19 10 21 2 24 22 0 1 13 18 16 11 9 8 7 3 5 12 72 14765 5273099 [A,B,E,F]
79 10 3 12 23 22 16 0 5 4 17 7 19 8 13 21 6 15 2 11 9 20 14 18 1 24 65 9313 3075238 [C,D,E,F]
80 9 2 20 17 18 15 11 23 6 7 12 4 14 24 19 13 21 8 16 1 10 3 5 22 0 67 42469 19436832 [C,D,E,F]
81 3 17 12 7 21 18 10 20 13 15 6 22 19 0 4 9 16 1 8 23 11 2 5 24 14 63 96750 46267106 [A,B,E,F]
82 8 17 14 6 15 5 18 21 2 9 13 11 1 12 23 3 22 20 7 16 24 19 4 10 0 64 35344 15834118 [C,D,E,F]
83 6 14 23 15 16 24 7 19 10 20 18 3 4 0 2 13 9 12 21 5 1 22 8 11 17 72 2657 967913 [C,D,E,F]
84 0 3 10 1 24 22 14 21 5 18 6 20 11 9 17 4 19 15 23 12 8 13 16 7 2 62 42031 13467875 [A,B,E,F]
85 23 4 24 1 18 7 11 2 12 14 13 5 10 17 6 20 16 15 19 8 0 21 22 3 9 65 4797 919814 [A,B,E,F]
86 9 8 13 0 23 18 5 7 3 19 20 6 16 21 15 17 2 22 4 10 1 14 24 11 12 67 4782 491437 [A,B,E,F]
87 11 4 12 15 9 24 18 19 22 16 20 7 17 6 8 10 0 3 13 2 14 23 5 21 1 72 3828 1162876 [A,B,E,F]
88 24 9 10 17 3 14 18 22 13 12 16 0 21 11 2 20 4 15 6 5 23 7 1 19 8 62 2656 416363 [C,D,E,F]
89 12 16 11 1 5 20 22 8 9 6 17 7 0 15 4 19 14 3 24 10 23 13 21 2 18 57 1562 387487 [A,B,E,F]
90 7 15 24 16 6 13 21 3 19 12 0 23 9 20 11 10 4 8 14 17 22 1 5 2 18 69 139735 73969673 [A,B,E,F]
91 16 13 6 17 2 3 1 9 7 15 14 20 21 22 24 0 8 18 10 11 5 23 19 4 12 63 1828 554163 [C,D,E,F]
92 22 20 9 24 16 13 19 2 10 3 18 17 15 0 6 4 23 1 21 8 7 11 14 12 5 71 7703 2504389 [C,D,E,F]
93 21 7 15 9 13 22 24 23 1 19 6 3 8 10 16 5 2 14 20 4 17 12 0 11 18 69 1516 338280 [C,D,E,F]
94 21 1 9 11 10 0 23 13 22 4 12 14 2 8 7 18 15 24 6 20 19 16 5 17 3 60 672 289571 [C,D,E,F]
95 22 14 16 6 13 2 24 15 20 21 1 10 23 17 7 3 0 11 18 19 12 4 5 8 9 72 20672 8466378 [C,D,E,F]
96 15 13 16 4 7 9 11 24 21 2 23 8 20 5 14 22 1 17 18 6 0 3 19 12 10 71 2578 430369 [C,D,E,F]
97 21 14 18 2 17 10 9 16 3 7 19 0 12 11 4 1 22 20 23 13 5 6 15 8 24 67 48063 21236300 [C,D,E,F]
98 15 6 4 21 20 0 7 24 12 3 17 11 2 13 9 16 1 5 14 18 10 23 22 8 19 67 7110 1641391 [A,B,E,F]
99 16 1 24 12 23 4 8 14 7 19 22 20 6 13 5 0 18 3 2 11 10 21 15 9 17 65 7875 1442361 [C,D,E,F]
100 20 18 19 15 5 3 13 12 24 11 14 0 4 6 16 2 1 22 10 8 17 21 23 7 9 62 18063 8795911 [A,B,E,F]
I've solved 10 instances from Korf and Taylor paper 'Finding Optimal Solutions to the Twenty-Four Puzzle' (1996). Search settings were the same; only optimal solutions in each phase were considered. The results are given below along with optimal solution lengths from the mentioned paper.
------------------------------------------------------------------------------------ Instance Solved in Optimal ------------------------------------------------------------------------------------ 17 1 20 9 16 2 22 19 14 5 15 21 0 3 24 23 18 13 12 7 10 8 6 4 11 124 100 14 5 9 2 18 8 23 19 12 17 15 0 10 20 4 6 11 21 1 7 24 3 16 22 13 119 95 7 13 11 22 12 20 1 18 21 5 0 8 14 24 19 9 4 17 16 10 23 15 3 2 6 126 108 18 14 0 9 8 3 7 19 2 15 5 12 1 13 24 23 4 21 10 20 16 22 11 6 17 120 98 2 0 10 19 1 4 16 3 15 20 22 9 6 18 5 13 12 21 8 17 23 11 24 7 14 125 101 16 5 1 12 6 24 17 9 2 22 4 10 13 18 19 20 0 23 7 21 15 11 8 3 14 114 96 21 22 15 9 24 12 16 23 2 8 5 18 17 7 10 14 13 4 0 6 20 11 3 1 19 128 104 6 0 24 14 8 5 21 19 9 17 16 20 10 13 2 15 11 22 1 3 7 23 4 18 12 115 97 3 2 17 0 14 18 22 19 15 20 9 7 10 21 16 6 24 23 8 5 1 4 11 12 13 129 113 23 14 0 24 17 9 20 21 2 18 10 13 22 1 3 11 4 16 6 5 7 12 8 15 19 138 114 ------------------------------------------------------------------------------------
- Bulat
