3x3のスライドパズル（8パズル）の最短移動距離と配置数

3x3のスライドパズルの異なる２つのゴールについて、その全配置パターンの最短移動距離を求めました。

数字が横方向にならぶゴールの配置では、最短移動距離が最大の31になる配置が、2個あります。 一方、真ん中がカラの時計回りの配置では、最短移動距離が最大の30になる配置は、148個になります。

最短移動距離	配置数
	ゴール （横）	ゴール （時計回り）
0 （ゴール）	1	1
1	2	4
2	4	8
3	8	8
4	16	16
5	20	32
6	39	60
7	62	72
8	116	136
9	152	200
10	286	376
11	396	512
12	748	964
13	1024	1296
14	1893	2368
15	2512	3084
16	4485	5482
17	5638	6736
18	9529	11132
19	10878	12208
20	16993	18612
21	17110	18444
22	23952	24968
23	20224	19632
24	24047	22289
25	15578	13600
26	14560	11842
27	6274	4340
28	3910	2398
29	760	472
30	221	148
31	2	------
配置数の合計	181440	181440

注. 配置数が最大の箇所と、移動距離が最大の箇所が赤色になっています。

横方向に数字が並んだゴール配置の場合、最短移動距離の最大は31になります。 その配置は２つしかありませんので、その２つの配置からゴールまでの全行程を調べてみました。

・横方向に並んだゴールの、最短移動距離が最大の31となる配置