--8パズル、Nパズル問題について--

-8パズル、Nパズル問題-

15パズル問題以外のスライディングパズル問題として 8パズルやNパズル問題でも測定を行った。このページではそれらの結果についてまとめる。

-8パズル問題-

8パズル問題は15パズル問題から、行と列を1つずつ減らした 3x3のパズルである。よって15パズル問題より、探索を簡単に行うことが可能である。ある状態について幅優先探索について測定し、以下に、深さごとの状態の数、及び、その深さまでの合計数を示す。

深さ	状態数	状態数の合計	深さ	状態数	状態数の合計
0	1	1	16	4485	11764
1	2	3	17	5638	17402
2	4	7	18	9529	26931
3	8	15	19	10878	37809
4	16	31	20	16993	54802
5	20	51	21	17110	71912
6	39	90	22	23952	95864
7	62	152	23	20224	116088
8	116	268	24	24047	140135
9	152	420	25	15578	155713
10	286	706	26	14560	170273
11	396	1102	27	6274	176547
12	748	1850	28	3910	180457
13	1024	2874	29	760	181217
14	1893	4767	30	221	181438
15	2512	7279	31	2	181440

最終的な探索した状態数は181440であり、この値は9!/2である。これは、スライディングパズル問題では半分の状態は到達することができないためであり、結果が正しいことが分かる。
8puzzle_探索プログラム

-11パズル問題(3x4パズル)-

11パズル問題は3x4のパズルである。よって8パズル問題よりは探索数が増えるが、 15パズル問題より、探索を簡単に行うことが可能である。ある状態について幅優先探索について測定し、以下に、深さごとの状態の数、及び、その深さまでの合計数を示す。

深さ	状態数	状態数の合計	深さ	状態数	状態数の合計
0	1	1	16	24215	55998
1	2	3	17	41802	97800
2	4	7	18	71167	168967
3	9	16	19	119888	288855
4	20	36	20	198363	487218
5	37	73	21	323206	810424
6	63	136	22	515778	1326202
7	122	258	23	811000	2137202
8	232	490	24	1248011	3385213
9	431	921	25	1885279	5270492
10	781	1702	26	2782396	8052888
11	1392	3094	27	4009722	12062610
12	2494	5588	28	5621354	17683964
13	4442	10030	29	7647872	25331836
14	7854	17884
15	13899	31783

この結果から、幅優先探索では8パズル問題が限界であり、11パズル問題や 15パズル問題を解くためには、状態数が多く厳しいということが分かる。
11puzzle_探索プログラム

戻る