Pattern databases for the 5x5 sliding puzzle

In 2002, Korf and Felner [1] used pattern databases to solve optimally 50 random instances of the 5x5 sliding puzzle. They used a static 6+6+6+6 partition of tiles (described below), along with its reflection in the main diagonal. In a 2004 paper by Felner, Korf and Hanan [2], the authors describe in a footnote the way they handled the empty tile as 'not trivial'; the empty tile was taken into account when precomputing the database, but then the tables were compressed by discarding the information about the empty location. The authors do not provide the distribution of values from the pattern databases, but do provide maximum values and the number of nodes generated when solving random instances of the 5x5 sliding puzzle.

``` =====================================================
Disjoint pattern databases from [1].
-----------------------------------------------------
The goal          The partition
--------------    -----------------------------------
0  1  2  3  4    group              tiles  max.value
5  6  7  8  9      1     1, 5, 6,10,11,12         34
10 11 12 13 14      2     2, 3, 4, 7, 8, 9         35
15 16 17 18 19      3    13,14,18,19,23,24         35
20 21 22 23 24      4    15,16,17,20,21,22         35
-----------------------------------------------------
0 stands for the unoccupied location/the empty tile.
Groups 2, 3, 4 are rotations of each other.
=====================================================
```

I did not find online actual distributions, so they are given below (not yet confirmed independently). The counts are given in terms of three different entities which I'm calling 'states', 'compressed states' and 'buckets'. 'States' are various arrangements of seven tiles, including the empty tile; for each of the pattern databases discussed in this post, there are 25 × 24 × 23 × 22 × 21 × 20 × 19 = 2,422,728,000 'states'. 'Compressed states' are various arrangements of six physical tiles included in a pattern database; for each table, there are 25 × 24 × 23 × 22 × 21 × 20 = 127,512,000 'compressed states'. 'Buckets' may be described as equivalence classes of 'states' where two 'states' are considered equivalent iff they are reachable from each other by a sequence of moves neither of which affects any physical tile included in the pattern database. Every 'state' maps to exactly one 'bucket', and every 'bucket' maps to exactly one 'compressed state'.

I implemented an optimal solver which uses these tables and ran it on 12 out of 50 puzzle instances from [1]. For all of these 12 configurations, the distances and the number of generated nodes reported by my implementation match those given in [1]. (In my implementation, the search is terminated when the first solution is found; the moves are tried in the fixed order [up, left, right, down], with move direction corresponding to the direction of movement of the empty tile; there is no duplicate pruning other than to eliminate pairs of consecutive moves which cancel each other. The 12 processed instances are numbered 38, 40, 25, 32, 44, 37, 30, 13, 1, 28, 36, 5 in the paper [1].)

``` puzzle width 5, puzzle height 5,          puzzle width 5, puzzle height 5,
included tiles: 1 5 6 10 11 12.           included tiles: 2 3 4 7 8 9.
=====================================     =====================================
depth    states    buckets compressed     depth    states    buckets compressed
-------------------------------------     -------------------------------------
0           1          1          1       0          19          1          1
1          20          2          2       1          41          5          5
2         135          9          9       2         328         22         22
3         754         55         54       3        1334        103         95
4        3886        280        273       4        5105        397        370
5       14799       1155       1074       5       16338       1385       1232
6       53401       4129       3757       6       52937       4320       3791
7      164729      13356      11553       7      149856      12651      10563
8      491543      39117      32980       8      420868      34384      28437
9     1325609     106101      85905       9     1075536      88761      71058
10     3405635     265914     210543      10     2655989     213419     168426
11     7927164     616664     472673      11     6005367     482235     367936
12    17130913    1308777     985781      12    12877023    1009584     756771
13    33432774    2535817    1871683      13    25320552    1964433    1438714
14    60084276    4482475    3284912      14    46632587    3538326    2573547
15    97925708    7229511    5262740      15    78674074    5890359    4254808
16   146886439   10683502    7799786      16   122954224    9042318    6558453
17   200201594   14433632   10556162      17   174610198   12705389    9236626
18   249961826   17871658   13134678      18   226990170   16327060   11950095
19   282708284   20210658   14834746      19   267186882   19118948   14030534
20   292285449   20960619   15330827      20   287751894   20512342   15094797
21   274506700   19963596   14391820      21   281955429   20216127   14783693
22   236752952   17541704   12400468      22   254162891   18447110   13318514
23   186311927   14269210    9738365      23   209744247   15659774   10973204
24   135074301   10739111    7035973      24   159926679   12377348    8341436
25    89238452    7498469    4622876      25   111613147    9116498    5792559
26    54039824    4805688    2779377      26    71757121    6200945    3699450
27    29387026    2823636    1496425      27    41761333    3895004    2133436
28    14370145    1488576     723202      28    22072436    2216440    1115979
29     6063503     703149     300217      29    10250084    1135170     511246
30     2187330     282320     106335      30     4203931     508256     206439
31      629351      96111      29673      31     1415390     202524      67647
32      139288      26648       6250      32      393892      65498      18264
33       20782       5734        832      33       78660      16890       3438
34        1456        592         48      34       10706       3350        408
35          24         24          0      35         732        624          6
-------------------------------------     -------------------------------------
=  2422728000  181008000  127512000       =  2422728000  181008000  127512000
=====================================     =====================================
time: 3776                                time: 3634
```

For the irregular pattern, there are 55 depth-3 'buckets' but only 54 depth-3 'compressed states'. This is because there are two different depth-3 'buckets' mapping to the same depth-3 'compressed state'.

``` =================================
1  6  -  -  -      1  6  -  -  -
5  0 12  -  -      5  - 12  -  -
10 11  -  -  -     10 11  -  -  -
-  -  -  -  -      -  -  -  0  -
-  -  -  -  -      -  -  -  -  -
=================================
```

For the 2x3 pattern, there are 103 depth-3 'buckets' but only 95 depth-3 'compressed states', so 8 "missing" 'compressed states' need to be explained. There are six pairs of depth-3 'buckets' such that two 'buckets' in the same pair map to the same depth-3 'compressed state'. Two other depth-3 'buckets' map to 'compressed states' already reached at depth 1.

``` =====================================================================
- 2 - 3 4   - 7 - 3 4   - 2 - 3 4   - - 2 3 4   - - - 3 4   - - - 3 4
- 7 8 - 9   - - 2 8 9   - - 8 - 9   - - 8 - 9   - 7 2 - 9   - - 2 - 9
- - - - -   - - - - -   - - 7 - -   - - - 7 -   - - - 8 -   - - 7 8 -
- - - - -   - - - - -   - - - - -   - - - - -   - - - - -   - - - - -
- - - - -   - - - - -   - - - - -   - - - - -   - - - - -   - - - - -
=====================================================================
- - 2 3 4   - 2 - 3 4
- - 7 - 9   - - 7 8 9
- - - 8 -   - - - - -
- 0 - - -   - 0 - - -
- - - - -   - - - - -
=====================================================================
```

References

• [1] Richard E. Korf, Ariel Felner Disjoint pattern database heuristics, Artificial Intelligence 134 (2002) 9-22.
• [2] Ariel Felner, Richard E. Korf, Sarit Hanan Additive pattern database heuristics, Journal of Artificial Intelligence Research 22 (2004) 279-318.

Comment viewing options

Preliminary results and an update on WD (edited)

(Edited to add the configurations and a few missing entries.)

Late but hopefully not too late, here are some preliminary results from my experiments. (Nodecounts for DPDB match those given by Korf and Felner, so I believe my implementation of DPDB is correct. Nodecounts for WD, ID, WD+ID seem to match those produced by my slow solver written in 2011 (the new solver is written in another language without looking at the old code), so I believe these are correct too.)

I'm manually recompiling the code for different combinations of heuristics:

• DPDB = disjoint pattern databases from (Korf Felner 2002) discussed above. My implementation uses 470 MB of RAM when the tables are already built, and generates 11M+ nodes per second.
• WD = the 5x5 version of the WD heuristic. My implementation uses 315 MB of RAM and generates 20M+ nodes per second.
• ID = the 5x5 version of the ID heuristic. My implementation uses almost no memory and generates 20M+ nodes per second. I implemented only direct generalization of the InvertDistance heuristic as proposed by Ken'ichiro Takahashi and did not use additional improvements suggested here.
• MD = Manhattan distance.

According to my experiments, on 12 easier out of 50 test instances from (Korf Felner 2002), in terms of the number of generated nodes, DPDB is improved by several percents when WD and/or ID are added. In two out of 12 cases, my implementation generated approximately 17% less nodes when WD and ID are added.

I cannot say much about relative speeds since neither of my implementations is particularly optimized for speed. (I tried to optimize for memory first to make it possible to build all tables from scratch under 2 GB memory limit, and to be able to have two instances of the solver running at the same time.)

```===========================================================================================================================================
#   = sequential number in (Korf Felner 2002)
d   = optimal solution length
sol = the number of optimal solutions
---+---------+-----------------------------------------------------------+-----------------------------------------------------------------
|         |  nodes generated before finding a solution                |
# |   d sol |        DPDB          DPDB+WD+ID      DPDB+WD     DPDB+ID  | the configuration (tiles listed row-by-row; 0 = the empty tile)
---+---------+-----------------------------------------------------------+-----------------------------------------------------------------
38 |  96   2 |    38173507     31909075 (0.83+)    31909327    38172445  | 10 3 24 12 0 7 8 11 14 21 22 23 2 1 9 17 18 6 20 4 13 15 5 19 16
40 |  82  29 |    65099578     60703289 (0.93+)    60848519    64681879  | 2 17 4 13 7 12 10 3 0 16 21 24 8 5 18 20 15 19 14 9 22 11 6 1 23
25 |  81   1 |   292174444    280442696 (0.95+)   280643307   291366540  | 3 17 9 8 24 1 11 12 14 0 5 4 22 13 16 21 15 6 7 10 20 23 2 18 19
32 |  97  90 |   428222507    414924814 (0.96+)   414924814   428222507  | 1 12 18 13 17 15 3 7 20 0 19 24 6 5 21 11 2 8 9 16 22 10 4 23 14
44 |  93  32 |   867106238    838822884 (0.96+)   838842012   867014829  | 8 12 18 3 2 11 10 22 24 17 1 13 23 4 20 16 6 15 9 21 19 5 14 0 7
37 | 100  28 |  1496759944   1463297461 (0.97+)  1463311850  1496632184  | 23 22 5 3 9 6 18 15 10 2 21 13 19 12 20 7 0 1 16 24 17 4 14 8 11
30 |  92  92 |  1634941420   1614542297 (0.98+)  1614578934  1634889246  | 8 19 7 16 12 2 13 22 14 9 11 5 6 3 18 24 0 15 10 23 1 20 4 17 21
13 | 101  51 |  1959833487   1918576443 (0.97+)  1919885948  1957978536  | 21 24 8 1 19 22 12 9 7 18 4 0 23 14 10 6 3 11 16 5 15 2 20 13 17
1 |  95   4 |  2031102635   1695367987 (0.83+)  1696826918  2020361038  | 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
28 |  98  10 |  2258006870   2248334854 (0.99+)  2248347897  2257978947  | 17 15 7 12 8 3 4 9 21 5 16 6 19 20 1 22 24 18 11 14 23 10 2 13 0
36 |  90   4 |  2582008940   2534864132 (0.98+)  2535333654  2580372583  | 2 10 1 7 16 9 0 6 12 11 3 18 22 4 13 24 20 15 8 14 21 23 17 19 5
5 | 100  16 |  2899007625   2690055790 (0.92+)  2690244496  2897937637  | 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
===+=========+===========================================================+=================================================================
```

I ran the solver on some non-random instances. The configuration "rotate_180" seems to be a particularly bad case for disjoint pattern databases: ID using almost no memory generates less nodes to complete depth 140 than DPDB does. On the other hand, combining ID and/or WD with DPDB does reduce nodecounts even on "rotate_180". To complete depth 140, WD-only solver generates 17M nodes while (WD+DPDB) solver generates 15M nodes. To complete depth 146, WD-only solver generates almost 500 billion nodes, while (WD+DPDB) generates about 233 billion nodes.

```rotate_180:
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
The goal configuration rotated 180 degrees.
One of two first moves is eliminated by symmetry.
flip_vert_axis:
4 3 2 1 0 9 8 7 6 5 14 13 12 11 10 19 18 17 16 15 24 23 22 21 20
The goal configuration flipped through the vertical axis.
================================================================================================================================
generated nodes (cumulative)
instance   bound     DPDB+WD+ID          DPDB            WD        DPDB+WD            ID        ID+MD     DPDB+ID        WD+ID
--------------------------------------------------------------------------------------------------------------------------------
rotate_180     124              0             1             0              0             0            0           0            0
126              0             9             0              0             0            0           0            0
128              0           788             0              0             0            0           0            0
130              0         62355             0              0             0            0           0            0
132              0       1095629             0              0             0            0           0            0
134              0      15486762             0              0             0            0           0            0
136              0     187876189             0              0             0            0           0            0
138              0    2100817840             0              0       5622757      2502496     1003660            0
140       12975839   22314038172      17474091       14806992    4767725265   1145523489   277632941     14797086
142      418185493  229631960768     614995376      458921922  666572445943  77431345211 11664615494    537394496
144    10474491406             ?   18445278588    11227620518             ?            ?           ?  16407796369
146   221146700659             ?  499016231478   232963173634             ?            ?           ? 448726571169
--------------------------------------------------------------------------------------------------------------------------------
flip_vert_axis  70              0             0             9              0            28           28           0            2
72              0             0            83              0           294          236           0           16
74              0             0           605              0          2304         1519           0          101
76              0             0          4217              0         16205         9450           0          793
78              0             0         26271              0        113387        57541           0         5145
80              0             0        158447              0        798441       340801           0        33054
82              0             0        915434              0       5530766      1980858           0       207560
84              0             0       5212048              0      38129709     11603898           0      1276773
86              8             8      29578865              8     261212298     67974229           8      7723169
88             86            86     168919378             86    1779522375    398768365          86     46616634
90           1661          1661     971808143           1661   12063225941   2345443093        1661    281856918
92          18412         18412    5632104471          18412   81413664534  13837611904       18412   1709042186
94         166037        166038   32870765969         166038             ?            ?      166037  10393317127
96        1357292       1357336             ?        1357328             ?            ?     1357300            ?
98       10378614      10379891             ?       10379257             ?            ?    10379248            ?
100       75583656      75605743             ?       75591057             ?            ?    75598255            ?
102      532193383     532501338             ?      532266095             ?            ?   532426444            ?
104     3661141266    3664795873             ?     3661803060             ?            ?  3664100851            ?
106    24763129767             ?             ?    24768714395             ?            ?           ?            ?
108   165448583536             ?             ?              ?             ?            ?           ?            ?
================================================================================================================================
```

To me it looks like DPDB is better on random instances (but WD and ID are still helpful), while WD and ID are much better on some non-random instances such as "rotate_180" (but DPDB is still helpful).

The WD ("WalkingDistance") heuristic suggested by Ken'ichiro Takahashi may be a re-discovery of "X-Y heuristic" (Prieditis 1993). I could not find any earlier mention of the ID ("InvertDistance") heuristic in the literature, though. I am trying to organize available to me information, but unfortunately I cannot tell how long it will take to me, so below are links for anyone interested.

Solving 4x4 antipodes as 5x5 puzzle instances

Some 4x4 configurations can be solved with fewer moves, when extended to 5x5 configurations. The following instance is solvable in 31s* (single-tile moves) if the fringe tiles (rightmost column and bottom row) are fixed, but in 29s* when all tiles can be moved:

```==================================================
5  1  2  3  #     5  1  2  3  4     0  1  2  3  4
10 18 13  8  #    10 18 13  8  9     5  6  7  8  9
15  6 11  7  #    15  6 11  7 14    10 11 12 13 14
0 16 17 12  #     0 16 17 12 19    15 16 17 18 19
#  #  #  #  #    20 21 22 23 24    20 21 22 23 24
--------------    --------------    --------------
31s*              29s*             goal
==================================================
```

(For comparison, the diameter of the square subgroup of the Rubik's Cube is 15, yet any element of the square subgroup can be solved in at most 13 moves when all 18 face turns are allowed.)

It seemed natural to check whether any of 17 antipodes of the 4x4 puzzle can be solved in less than 80 single-tile moves as a 5x5 configuration. However, according to my solver, all of them remain 80s*, even when extended to 5x5. I did not check whether there are any additional optimal solutions which temporarily disturb the fringe tiles.

On these 17 instances of the 5x5 sliding puzzle, WD-only solver generated roughly 7 to 18 times more nodes than DPDB-only solver, while DPDB-only solver generated roughly 1.6 to 2.2 times more nodes than (DPDB+WD) solver.

(Added 20 Apr 2017) (WD+ID) solver generated roughly 1.06 to 1.47 times less nodes than WD-only solver. Answering myself: My 5x5 solver found all optimal solutions to every 4x4 antipode extended to 5x5. Then I used Kociemba's 15 puzzle optimal solver to find all optimal solutions to every 4x4 antipode. The number of solutions was the same in both cases (it ranges between 440 and 4452), so for these 17 instances there are no optimal solutions which touch fringe tiles.

Nodecounts

The next table gives the number of optimal solutions and the number of generated nodes for each of 17 4x4 antipodes extended to 5x5. Nodecounts are recorded when the last iteration of IDA* is completed. The WD-only solver took almost two weeks to find all optimal solutions. Although there are pairs of antipodes equivalent by the reflection in the main diagonal (e.g. #1 and #16), I decided to actually run all 17 instances. As expected, the number of solutions and the number of generated nodes are the same for equivalent configurations.

```===+==================================================================+===========+===================================
# | configuration                                                    | solutions |            DPDB                 WD
---+------------------------------------------------------------------+-----------+-----------------------------------
1 | 18 12 10 15 4 13 17 11 16 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |       910 |  61,386,708,118    914,128,113,559
2 | 18 12 10 15 4 13 17 11 16 9 8 2 6 1 14 3 7 5 0 19 20 21 22 23 24 |      1140 |  44,495,088,172    468,779,470,388
3 | 18 13 10 15 4 17 12 11 16 9 2 7 1 5 14 3 8 6 0 19 20 21 22 23 24 |      4452 | 170,316,871,450  1,439,376,195,033
4 | 18 13 10 15 4 17 12 11 16 9 2 7 5 6 14 3 8 1 0 19 20 21 22 23 24 |      4452 | 170,316,871,450  1,439,376,195,033
5 | 18 13 10 15 4 17 12 11 16 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |       440 |  70,453,139,840  1,201,499,910,036
6 | 18 13 10 15 4 17 12 11 16 9 7 8 6 1 14 3 2 5 0 19 20 21 22 23 24 |       588 |  57,549,187,795  1,035,280,751,391
7 | 18 13 10 15 4 17 12 11 16 9 8 2 6 1 14 3 7 5 0 19 20 21 22 23 24 |       874 |  59,238,029,171    781,918,528,526
8 | 18 13 10 15 4 17 12 11 16 9 8 7 2 1 14 3 6 5 0 19 20 21 22 23 24 |      2600 |  83,242,139,315  1,751,302,912,656
9 | 18 13 10 15 4 17 12 16 11 9 2 8 6 1 14 3 7 5 0 19 20 21 22 23 24 |      1836 |  93,202,855,922  1,382,212,228,198
10 | 18 13 11 15 4 17 12 10 16 9 7 2 6 1 14 3 8 5 0 19 20 21 22 23 24 |      1836 |  73,600,093,024  1,458,004,959,066
11 | 18 13 11 15 4 17 12 16 10 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |       588 |  57,549,187,795  1,035,280,751,391
12 | 18 13 11 15 4 17 12 16 10 9 7 8 6 1 14 3 2 5 0 19 20 21 22 23 24 |      2908 |  42,846,821,608    778,775,680,054
13 | 18 13 16 15 4 17 12 10 11 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |       874 |  59,238,029,171    781,918,528,526
14 | 18 13 16 15 4 17 12 10 11 9 8 2 6 1 14 3 7 5 0 19 20 21 22 23 24 |      3072 |  46,143,201,010    419,638,047,688
15 | 18 13 16 15 4 17 12 11 6 9 2 7 10 1 14 3 8 5 0 19 20 21 22 23 24 |      2600 |  83,242,139,315  1,751,302,912,656
16 | 18 17 10 15 4 12 13 11 16 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |       910 |  61,386,708,118    914,128,113,559
17 | 18 17 16 15 4 12 13 10 11 9 2 7 6 1 14 3 8 5 0 19 20 21 22 23 24 |      1140 |  44,495,088,172    468,779,470,388
===+==================================================================+===========+===================================
```

The next table gives nodecounts recorded when the first solution is found, for the same 17 instances. Unlike previous table, this one may give different counts for mirror-symmetric pairs. As previously, the move ordering is u/l/r/d.

```===+=================================================================================================
# |           DPDB         DPDB+ID         DPDB+WD      DPDB+WD+ID            WD+ID               WD
---+-------------------------------------------------------------------------------------------------
1 |  7,301,542,915   7,267,691,032   3,840,846,429   3,839,756,412   83,449,420,523   88,727,433,639
2 |  5,293,583,742   5,212,321,172   2,475,863,836   2,473,400,757   38,965,153,650   43,348,959,604
3 | 20,394,436,550  20,279,301,620  10,069,090,192  10,059,642,252  125,641,851,367  138,865,808,763
4 | 20,183,371,194  20,069,399,727   9,946,214,793   9,936,828,898  123,172,066,401  136,098,508,504
5 |  8,255,111,753   8,223,693,335   4,689,727,775   4,686,945,608  102,266,545,781  118,243,263,060
6 |  6,455,013,816   6,383,001,344   3,799,682,848   3,789,581,455   75,897,775,491   95,636,751,217
7 |  6,956,677,750   6,865,124,988   3,686,188,342   3,678,717,807   60,944,706,446   75,041,333,619
8 |  9,787,886,278   9,556,674,596   6,034,694,007   5,990,081,387  124,590,810,415  175,634,034,165
9 | 10,705,339,984  10,565,349,892   6,203,203,210   6,178,021,487  102,385,201,828  130,964,138,618
10 |  8,248,197,644   8,174,098,123   5,124,234,476   5,114,664,212  110,201,200,254  137,300,518,731
11 |  6,459,127,588   6,387,121,482   3,802,122,335   3,792,021,858   75,984,110,905   95,731,469,649
12 |  4,751,060,036   4,605,608,908   2,941,269,389   2,909,411,563   48,573,149,374   71,278,712,628
13 |  6,917,790,748   6,828,046,668   3,651,808,994   3,644,615,112   60,355,994,867   74,030,273,220
14 |  5,432,152,503   5,227,237,856   2,575,692,374   2,561,084,633   28,275,806,935   38,525,045,841
15 |  9,829,674,100   9,598,085,198   6,058,561,902   6,013,894,736  125,225,463,151  176,487,541,957
16 |  7,248,488,192   7,214,701,119   3,795,950,596   3,794,887,259   81,155,950,967   85,972,625,626
17 |  5,226,317,803   5,146,225,868   2,429,128,831   2,426,789,541   37,300,640,889   41,148,709,102
===+=================================================================================================
```