### Lower bounds

4x5, lb = 107 stm
(0-first goal!)
18 19 17 16 15
14 13 12 11 10
9 8 7 6 5
4 3 2 1 0
5x5, lb = 152 stm
(0-first goal!)
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

### Upper bounds

2x7 can be reduced to 2x4 in 39 multi-tile moves. Avoiding 25-move configuration in 2x4 is not always possible, so upper bound for 2x7 is 39 + 25 = 64 MTM.

2x8 can be reduced to 2x5 in 43 MTM. It is possible to avoid 36-move configuration in 2x5 sub-puzzle.

3x5 can be reduced to 3x3 in 31 multi-tile move. Last move always can be combined with first move in 3x3, thus upper bound for 3x5 is 31 + 24 - 1 = 54 MTM.

3x6 can be reduced to 3x4 in 77 STM or 35 MTM. In MTM, first move in 3x4 can be cancelled.

3x7 can be reduced to 3x5 in 93 STM or 39 MTM.

3x8 can be reduced to 3x6 in 107 STM or 42 MTM.

3x9 can be reduced to 3x6 in 192 STM.

4x5 can be reduced to 4x4 in 58 STM.

4x5 can be reduced to 4x4 in 31 MTM. Last move can always be combined with first move in 4x4, so upper bound for 4x5 is 31 + 43 - 1 = 73 MTM.

4x6 can be reduced to 4x5 in 70 STM or 35 MTM.

4x7 can be reduced to 4x6 in 82 STM.

4x8 can be reduced to 4x7 in 94 STM.

4x9 can be reduced to 4x8 in 106 STM.

5x6 can be reduced to 5x5 in 89 STM.

6x6 can be solved in 95 + 92 + 98 + 58 + 80 = 423 STM through the following stages:

1 1 1 2 2 2
1 2 2 3 3 3
1 4 5 5 5 5
3 4 5 5 5 5
3 4 5 5 5 5
3 4 5 5 5 x

6x6 can be solved in 42 + 41 + 37 + 108 = 228 MTM through the following phases:

1 1 2 2 2 2
1 1 3 3 3 3
4 4 4 4 4 4
4 4 4 4 4 4
4 4 4 4 4 4
4 4 4 4 4 x