Results

m × n puzzle (current state of the art)

02 / 16 / 2012

Tables below contain general results related to m × n puzzles. Note that some cells are clickable. For example, you can see all antipodes by clicking a number in column "a".

Classic (0-terminated, slot-last) goal configuration is assumed in all cases. All values from the tables are correct for any goal configuration with slot in a corner.

Notation
gngod's number
lblower bound
ubupper bound
athe number of antipodes
wdwidth (max. number of nodes at any depth)
ddepth at which width wd is reached
STM
m × n gnlbub a wd d
22 6 1 2 1
23 21 1 44 14
24 36 1 1,999 24
25 55 2 133,107 36
26 80 2 13,002,649 49
27 108 1 1,862,320,864 66
28 140 1 367,084,684,402 85
33 31 2 24,047 24
34 53 18 21,841,159 36
35 84 1 45,473,143,333 52
36 95130
37 96177
38 123237
39 150322
44 80 17 784,195,801,886 53
45 107138
46 132208
47 149290
48 188384
49 227490
55 152208
56 177297
66 230423
77 352752
MTM
m × n gnlbub a wd d
22 6 1 2 1
23 20 1 45 11
24 25 8 2,884 18
25 36 1 256,305 23
26 41 36 32,688,655 28
27 64
28 78
33 24 1 31,485 17
34 33 5 39,470,660 24
35 54
36 67
37 93
38 109
44 43 16
45 73
46 108
55 41109
66 228

References

  1. The Fifteen Puzzle can be solved in 43 "moves"
  2. Twenty-Four puzzle, some observations
  3. 5x5 can be solved in 109 MTM
  4. A151944 (OEIS)
    – maximal number of moves required for the m X n generalization of the sliding block 15-puzzle (or fifteen-puzzle)
  5. Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM 55 (6): Article 26, 40pp
About lower and upper bounds