cube files
Indexed Cube Lovers Archive
Pattern databases for the 5x5 sliding puzzle
Submitted by stannic on Sun, 04/02/2017 - 11:37.
In 2002, Korf and Felner [1] used pattern databases to solve optimally 50 random instances of the 5x5 sliding puzzle. They used a static
===================================================== 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
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.
