# 5x5 puzzle: Comparison between reduction chains (STM, 10000 instances)

The multi-chained approach used in kumi na tano allows to use multiple search chains at the same time. The main advantage is that the best chain can be choosen depending on the instance to be solved, rather than hard-coded into the search algorithm.

For example, the first of the following two 5x5 instances has its leftmost column solved, while second has solved four tiles in top-right corner.

```[1]
1 17  9 10 18    18  3 16  4  5
6  0  2  3  8    11  7 17  9 10
11  5 22  7  4    19  2 23  0 21
16 15 20 23 13     6 20 14 12  1
21 19 12 14 24    13  8 15 22 24```

We cah use multi-chained approach here. The following two partitioning schemes:

```[2]
I           II
1 2 3 3 3    2 2 1 1 1
1 2 3 3 3    2 2 2 1 1
1 2 4 4 4    3 3 4 4 4
1 2 4 4 4    3 3 4 4 4
1 2 4 4 -    3 3 4 4 -```

- in combination lead to a two-chained four-phase search algorithm. The first of instances on diagram [1] can be better solved (probably) using scheme I, since with this scheme the instance has its 1st stage already solved. Second one can be probably solved better using scheme II since 4 of 5 tiles that must be solved in phase 1 are already solved.

There is a question: given the size of the puzzle (width and heigth), the move metric and the number of search phases, what is the best chain to be used in simple single-chained multi-phase search? For example, what of two schemes on diagram [2] has higher probability to give optimal solution in STM metric for the randomly choosen 5x5 puzzle instance?

So I decided to perform comparison between some possible chains and combinations of chains by solving the sample of 10,000 random instances of Twenty-Four puzzle in STM metric. I've used six different chains. All these chains are shown on diagram [3] as four-stage reductions from 5x5 puzzle to the solved state (I). I note that 5x4 is the puzzle with 5 columns and 4 rows, while 4x5 is the puzzle with 4 columns and 5 rows.

```[3]
1) 5x5 > 5x4 > 5x3 > 5x2 > I
2) 5x5 > 5x4 > 5x3 > 3x3 > I
3) 5x5 > 5x4 > 4x4 > 3x3 > I

1a) 5x5 > 4x5 > 3x5 > 2x5 > I
2a) 5x5 > 4x5 > 3x5 > 3x3 > I
3a) 5x5 > 4x5 > 4x4 > 3x3 > I```

Below are given some statistics for various sets of these chains. Each row of the table [4] represents single launch of the solver over the sample of 10,000 random instances. The sample is the same in all runs.

The first column lists the chains used in launch. For example, 3+3a means that the solver was using reduction chain 5x5 > 5x4 > 4x4 > 3x3 > I along with its mirror reflection.

For each set of chains used, I ran the solver three times.

First, the program was set to find only one solution by finding the only optimal solution for each of phases. These launches are denoted by "1st" code in "limits" column.

Next, kumi na tano was set to try also alternative optimal solutions in each phase in order to possibly optimize overall solution. These launches are denoted in the table as "sl0" in "limits" column (sl0 stands for slackness = 0).

Finally, the solver was set to allow also one non-optimal move in any one of search phases (that is, the search was performed with 0 ≤ slackness ≤ 1). These launches shown in the table with "sl1" in "limits" column.

I note that the full set of chains (1+1a+2+2a+3+3a) has been launched additionally with limit 2 on slackness (0 ≤ slackness ≤ 2). This launch is shown in the last row of the table [4] with "sl2" in "limits" column.

For each launch, the average time per instance, the minimum, maximum and average length of solution and average number of visited regions (i.e. started search phases) is shown in the corresponding columns of the table. Last column shows the number of instances solved with each of chains used. For example, after running two-chained search with chains 1 and 1a from diagram [3] and slackness value limited to 0, the number of instances solved with chain 1 was 4964, and the number of instances solved with chain 1a was 5036.

```[4]
---------------------------------------------------------------------------------------------
chains        limits         time       length                  rnodes   proportion of chains
avg       min  max       avg         avg
---------------------------------------------------------------------------------------------
1                1st        3.272 ms     89  188  144.5478      4.0000   10000
sl0       46.150 ms     85  178  132.7038   1703.6038   10000
sl1      227.103 ms     85  166  129.4326  10243.3826   10000

2                1st        4.704 ms     87  186  138.6718      4.0000   10000
sl0       46.339 ms     81  168  128.7222    912.2307   10000
sl1      198.343 ms     81  163  126.0578   5487.0849   10000

3                1st        4.541 ms     89  177  137.6858      4.0000   10000
sl0       52.348 ms     85  165  127.4860    870.2424   10000
sl1      154.030 ms     85  163  124.9416   4646.3157   10000

1+1a             1st        3.564 ms     85  183  142.8618      4.0000   5194 + 4806
sl0       69.875 ms     84  167  128.7094   2697.4575   4964 + 5036
sl1      289.384 ms     84  161  125.8832  15015.9378   4945 + 5055

2+2a             1st        3.229 ms     87  183  137.1806      4.0000   5194 + 4806
sl0       56.624 ms     81  158  125.2678   1456.2104   5064 + 4936
sl1      222.304 ms     81  155  123.0036   8420.9046   5044 + 4956

3+3a             1st        3.159 ms     89  176  136.9672      4.0000   5194 + 4806
sl0       66.205 ms     85  159  124.5896   1459.2220   5100 + 4900
sl1      236.012 ms     81  157  122.4238   7646.5086   5074 + 4926

1+1a+2+2a+3+3a   1st        3.350 ms     89  183  138.0446      4.0000   2352 + 2179 +  143 +  136 + 2699 + 2491
sl0      110.230 ms     81  156  122.9030   2590.1651    468 +  486 + 1886 + 1897 + 2716 + 2547
sl1      410.076 ms     81  155  120.8876  13490.9681    491 +  524 + 1877 + 1877 + 2677 + 2554
sl2     2398.839 ms     79  149  117.5580  79379.3114    526 +  557 + 1950 + 1857 + 2564 + 2546
---------------------------------------------------------------------------------------------```

The following table shows for each launch the number of configurations solved in n moves as function of n. Each column represents a single launch.

```[5]
--------------------------------------------------------------------------------------------------------
chains     1            2            3            1+1a         2+2a         3+3a         1+1a+2+2a+3+3a
limits     1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1 sl2
--------------------------------------------------------------------------------------------------------
length     the number of puzzle configurations
--------------------------------------------------------------------------------------------------------
79       -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   1
80       -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
81       -   -   -    -   1   1    -   -   -    -   -   -    -   1   1    -   -   1    -   1   1   4
82       -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   3
83       -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   1
84       -   -   -    -   -   -    -   -   -    -   1   1    -   -   2    -   -   -    -   1   2   3
85       -   1   1    -   -   -    -   1   1    1   2   2    -   -   -    -   1   1    -   1   1   1
86       -   -   -    -   -   -    -   -   -    -   -   -    -   2   -    -   1   2    -   1   -   3
87       -   1   1    1   2   3    -   -   2    -   1   1    1   2   3    -   -   2    -   2   5   8
88       -   -   -    -   1   1    -   1   2    -   -   -    1   1   1    -   1   2    -   1   2   3
89       1   -   1    1   1   -    1   2   5    1   1   2    1   2   1    2   2   6    2   4   6   4
90       -   1   1    -   2   2    -   -   1    -   1   2    -   3   3    -   1   1    -   4   3  18
91       -   1   1    -   4   5    1   3   3    -   1   1    2   7   7    2   9   6    1   9   6  13
92       1   1   2    -   -   1    1   4   7    -   4   4    -   -   4    1   9  15    1   7  17  25
93       1   2   2    -   2   2    1   4   4    2   5   5    1   3   4    1   6   9    1   6   8  25
94       -   3   3    -   2   5    1   6   7    1   6   7    1   6  11    2  10  11    3  15  17  22
95       -   6   5    -   1   5    2   8   8    -   8   8    2   6  11    -   6   8    -   8  13  15
96       -   3   4    2   8  12    1   8  12    1   3   7    3  14  19    -  12  17    1  16  23  49
97       -   2   7    2   6  10    2   6   5    1   5  11    2  12  18    2   8  10    1  15  19  46
98       -   4   8    -  10  18    2  12  16    -   5  12    2  17  31    2  24  31    2  28  42  67
99       2   4   5    1  10  18    4  10  26    4   4   8    2  10  16    3  23  34    5  26  40  75
100       -   6  16    4  16  22    3  25  37    2  13  32    8  30  37    2  32  45    3  46  55  76
101       4   9  16    7  19  27    4  12  26    4  15  24    5  27  42    4  22  33    9  39  53  89
102       -  12  23    8  30  44    9  37  39    6  29  37    9  47  52    8  45  51    7  60  70 127
103       -  16  18    2  23  31    4  34  44    -  25  35    4  33  51    7  52  72    5  56  79 138
104       4  20  40    9  43  51   10  35  56    3  35  56   12  56  73   18  52  83   15  71  94 152
105       3  13  29    6  31  48    9  48  68    1  25  40   13  54  73    7  70  89    6  84 104 157
106       5  20  35   16  40  58   17  54  70    6  38  56   18  78 112   18  81 107   15 111 141 212
107       1  25  48   11  36  58   11  71  81    1  41  69   16  70  98   16  87 109   13  95 143 212
108       5  45  52   19  65  91   18  78 104   10  66  88   29  90 123   20 109 136   23 134 160 236
109       7  37  49   16  77  95   22  66  94    8  67  89   15 118 138   22 105 156   23 150 175 256
110      10  55  70   27 106 158   17  93 131   13 100 122   35 131 172   19 142 178   15 179 211 269
111      11  45  73   22  67 116   31 114 136   11  88 125   28 117 174   38 146 169   34 163 208 287
112      13  93 129   30 129 145   46 143 182   19 128 160   37 193 215   54 181 230   46 221 283 357
113      15  72 108   46 126 174   44 143 189   22 119 163   40 186 247   44 189 226   42 233 279 348
114      28 116 154   37 145 208   52 178 219   27 146 190   56 218 272   57 241 272   60 278 302 353
115      23  95 142   48 178 217   58 160 219   31 151 216   57 251 288   65 221 277   63 287 326 392
116      37 109 166   59 187 227   71 205 251   45 158 233   60 251 300   74 264 288   78 291 330 410
117      24 129 181   66 185 243   82 220 274   38 181 244   81 230 299   86 277 320   89 302 332 399
118      41 161 214  109 237 252   79 251 307   49 231 284  105 293 303   95 305 381   91 333 380 422
119      41 167 210   87 235 282   85 255 325   39 226 265  107 303 339   89 330 372   84 349 389 380
120      59 196 247  110 243 299  121 288 361   63 264 309  145 310 356  121 356 399  109 361 412 418
121      50 218 281  103 272 316  100 301 363   55 290 356  134 328 354  135 332 380  114 346 380 366
122      72 218 265  139 293 352  164 318 351   88 280 343  143 343 413  161 346 385  166 370 404 410
123      76 229 269  141 312 353  166 337 339  101 283 321  161 369 385  167 365 383  162 389 398 339
124      80 274 314  161 338 385  185 361 390   91 349 389  174 369 402  191 389 414  176 393 404 380
125      88 294 367  160 311 346  168 302 361  103 377 422  189 369 374  166 343 353  141 339 334 282
126     119 271 337  191 357 387  185 370 405  137 347 409  222 422 422  198 400 400  203 418 398 311
127     104 261 321  188 327 363  227 359 359  126 335 345  200 374 381  241 350 344  218 356 350 267
128     130 311 370  190 381 411  262 386 405  146 371 401  207 386 406  271 390 397  231 381 370 271
129     136 297 334  230 367 376  237 338 317  149 322 342  275 338 329  252 368 324  231 339 283 214
130     130 325 399  265 378 367  266 359 368  170 398 416  292 396 353  277 382 332  243 350 302 223
131     161 329 342  243 339 316  282 347 318  206 345 345  283 314 244  282 322 270  278 281 220 132
132     187 356 373  272 358 374  273 399 355  208 370 364  300 355 320  300 357 300  279 318 258 141
133     212 327 335  270 297 276  274 320 300  254 359 294  270 298 252  284 282 243  282 247 184 115
134     221 415 382  314 361 300  305 319 265  253 386 294  308 308 223  333 270 216  321 243 170 110
135     240 326 327  306 303 252  306 282 221  251 295 276  306 223 187  317 231 187  301 180 153  84
136     257 329 332  303 301 275  323 281 257  277 308 286  323 244 196  337 236 189  334 191 142  71
137     246 339 276  298 300 233  323 228 206  259 266 203  291 219 147  312 184 140  283 163 106  51
138     271 320 308  315 263 211  334 255 178  295 308 230  340 184 144  329 194 120  315 135  87  37
139     279 280 228  318 232 166  292 219 153  316 259 177  333 154 110  303 146  93  306 108  68  31
140     301 298 228  356 223 179  355 199 150  326 246 171  337 155 102  331 135  89  308  95  68  24
141     281 244 201  308 170 124  322 145  86  280 177 116  309 120  77  299  92  55  265  61  44  14
142     311 272 204  320 205 134  362 167  97  306 199 132  317 106  59  331  91  57  323  64  33  20
143     291 211 143  310 145 103  277 132  80  308 157  90  275  68  43  263  68  39  270  46  21   5
144     313 231 154  284 146  98  284 127  71  323 144  78  291  81  44  319  65  39  295  53  26   6
145     302 190 125  283  98  68  260  94  54  283  97  72  263  70  30  265  47  20  279  35  13   8
146     335 215 147  350 123  75  286  93  63  332  93  46  310  64  35  266  49  27  256  35  18   7
147     291 152  93  248  98  54  247  71  47  313  81  37  248  39  20  232  40  17  253  20  12   1
148     332 160  96  274  92  40  242  72  37  332  77  27  263  37  14  230  36  12  252  16   7   2
149     275 118  76  222  67  39  211  47  20  252  53  26  184  21  10  216  16   6  203  10   4   2
150     321 118  65  241  48  21  214  49  24  299  54  26  193  20  12  214  18   7  219   8   6   -
151     291  88  57  175  48  12  155  41  13  244  46  14  154   6   4  157  10   2  178   5   1   -
152     278  95  44  206  41  14  185  27  16  241  33  17  182  11   5  170   3   4  177   4   1   -
153     231  73  43  158  24  15  141  15   4  215  18  10  140   8   2  148   4   2  154   4   3   -
154     279  60  23  145  34  12  140  21   4  265  19   6  129  13   2  135  10   1  165   5   -   -
155     215  60  16  150  21   7  128  10   6  208  15   4  122  10   3  103   5   3  121   3   1   -
156     227  52  14  125  11   5  140   9   -  206  17   3  115   1   -  116   1   -  140   1   -   -
157     223  42  11   88  13   6   85   8   1  166  12   3   73   2   -   69   1   1   79   -   -   -
158     192  24   6  114   8   2   89   5   -  176   7   -   92   3   -   77   -   -  108   -   -   -
159     142  24   6   75   6   1   63   4   2  149   3   -   60   -   -   49   2   -   88   -   -   -
160     172  19   6   81   6   1   55   1   -  141   2   -   68   -   -   54   -   -   77   -   -   -
161     129  12   7   63   4   -   52   1   -  105   4   1   45   -   -   51   -   -   58   -   -   -
162     129  10   5   52   3   1   58   2   -  104   2   -   39   -   -   43   -   -   58   -   -   -
163     116   8   5   31   2   1   29   3   2   80   2   -   21   -   -   21   -   -   44   -   -   -
164      98  11   1   41   2   -   31   -   -   80   -   -   34   -   -   26   -   -   38   -   -   -
165      69   8   2   20   2   -   23   1   -   56   -   -   18   -   -   18   -   -   30   -   -   -
166      87   3   1   24   -   -   19   -   -   65   -   -   14   -   -    9   -   -   26   -   -   -
167      56   7   -   20   -   -   12   -   -   42   1   -   10   -   -   12   -   -   19   -   -   -
168      69   1   -   18   2   -   16   -   -   47   -   -   10   -   -   14   -   -   25   -   -   -
169      37   -   -   16   -   -    8   -   -   27   -   -   10   -   -    2   -   -    7   -   -   -
170      50   3   -   14   -   -    8   -   -   33   -   -    9   -   -    6   -   -   12   -   -   -
171      26   -   -   12   -   -   10   -   -   19   -   -    3   -   -    9   -   -   10   -   -   -
172      25   1   -    3   -   -    7   -   -   26   -   -    2   -   -    6   -   -   10   -   -   -
173      27   -   -    6   -   -    2   -   -   14   -   -    5   -   -    1   -   -    3   -   -   -
174      18   -   -    7   -   -    1   -   -    9   -   -    2   -   -    1   -   -    3   -   -   -
175       9   -   -    2   -   -    -   -   -    6   -   -    1   -   -    -   -   -    3   -   -   -
176      13   -   -    2   -   -    1   -   -    7   -   -    -   -   -    2   -   -    5   -   -   -
177      10   -   -    1   -   -    1   -   -    3   -   -    -   -   -    -   -   -    -   -   -   -
178       9   1   -    -   -   -    -   -   -    8   -   -    1   -   -    -   -   -    3   -   -   -
179       7   -   -    -   -   -    -   -   -    1   -   -    -   -   -    -   -   -    -   -   -   -
180       5   -   -    -   -   -    -   -   -    1   -   -    -   -   -    -   -   -    1   -   -   -
181       5   -   -    1   -   -    -   -   -    4   -   -    1   -   -    -   -   -    2   -   -   -
182       2   -   -    -   -   -    -   -   -    1   -   -    -   -   -    -   -   -    -   -   -   -
183       2   -   -    -   -   -    -   -   -    3   -   -    1   -   -    -   -   -    2   -   -   -
184       1   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
185       2   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
186       -   -   -    1   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
187       -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
188       1   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -    -   -   -   -
--------------------------------------------------------------------------------------------------------
limits     1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1  1st sl0 sl1 sl2
chains     1            2            3            1+1a         2+2a         3+3a         1+1a+2+2a+3+3a
--------------------------------------------------------------------------------------------------------```

Obviously the more various chains are used, the shorter are solutions both in each concrete instance and in average. For example, with all six chains used and slackness limited to 2, the maximum length of solution was 149 moves, which is the best result over all runs. This is because the solver was allowed to choose between all six chains, and limit on the slackness was higher.

Last three rows of the table [4] show that reduction 5x5 > 5x4 > 4x4 > 3x3 (or symmetric reduction) was used in more than 50% of all instances (5263 of 10000 with slackness limit 0, 5231 with slackness limit 1, 5110 with slackness limit 2). This agrees with the fact that this reduction chain uses largest region, "fringe 4x4" region with 518,918,400 configurations/entries in the lookup table.

Note however that the higher slackness limit, the less instances are solved using this reduction. It seems like with enough slackness allowed, other chains become more "popular".

I can check any other chain(s) on the same sample of 10,000 instances if anyone is interested. I am currently working on similar table for MTM metric. I will not probably perform comparison for other metrics (2TM or 3TM) unless someone is interested in these metrics.

- Bulat