スライドパズルを自動で解くプログラムを作ってみた

はじめに

スライドパズル（15パズルなど）を自動で解くプログラムを作成しました。本記事では、その実装について解説します。

コード

以下が今回作成したスライドパズルの自動解決プログラムです。

xx=Z-1;
l=[],d=[...p];
mp=n=>{
	f=d.filter((_,i)=>i%z==n%z);
	((t=n/z|0)-(s=xx/z|0))||(d.splice(xx,1),d.splice(xx=n,0,"x"));
	if(/x/.test(f)){
		f.splice(s,1),f.splice(t,0,"x");
		for(i=n%z;i<Z;i+=z)d[i]=f[i/z|0];
		xx=n
	}
}

if(d[4]==1)[6,0,1,4,3,0,1,2,8].forEach(e=>{mp(e);l.push(e)});
while(d[0]!=1)[6,0,2,8].forEach(e=>{mp(e);l.push(e)});
if(d[3]==2||d[6]==2)[6,3,5,8,6,3,5,8].forEach(e=>{mp(e);l.push(e)});
while(d[1]!=2)[7,1,2,8].forEach(e=>{mp(e);l.push(e)});
while(d[2]!=3&&d[5]!=3)[6,3,5,8].forEach(e=>{mp(e);l.push(e)});
if(d[2]!=3)[6,0,2,5,4,1,0,6,8].forEach(e=>{mp(e);l.push(e)});
if(d[3]!=4||d[6]!=7){
	while(d[3]!=7)[6,3,5,8].forEach(e=>{mp(e);l.push(e)});
	while(d[6]!=4&&d[5]!=4)[7,4,5,8].forEach(e=>{mp(e);l.push(e)});
	if(d[6]==4)[6,3,4,7,8,5,3,6,8].forEach(e=>{mp(e);l.push(e)});
	[7,4,5,8,6,3,5,8].forEach(e=>{mp(e);l.push(e)});
}
while(d[4]!=5&&d[5]!=6)[7,4,5,8].forEach(e=>{mp(e);l.push(e)});

ii=0;
setInterval(()=>{if(ii<l.length)m(l[ii++])},200);

コードの解説

基本的な動作

このコードはスライドパズルを解くために、以下のような手順を踏みます。

1. mp(n) 関数を使用して、指定した位置に対してピースの移動を行う。
2. 事前に決めた手順に沿って移動を繰り返し、パズルを解く。
3. setInterval により一定の時間間隔で動作を実行し、アニメーション的にパズルを解く様子を再現。

主要な変数

• xx: 空白の位置を管理する変数。
• l: 解答手順を記録するリスト。
• d: パズルの状態を表す配列。
• mp(n): 指定された位置 n に対して、空白ピースを移動させる関数。

解法の流れ

1. if(d[4]==1) によって、中央のピースの処理を行う。
2. while(d[0]!=1) で、左上のピースを正しい位置に移動。
3. if(d[3]==2||d[6]==2) で、2のピースを適切な位置に移動。
4. while(d[1]!=2) で、上段のピースを適切に配置。
5. その他の条件を満たすように順次移動を行う。
6. setInterval を使って、計算結果に従いパズルを解いていく。

まとめ

今回の実装では、スライドパズルを効率的に解くために、事前に決められたパターンに基づいてピースを移動させました。シンプルなロジックでありながら、自動的にパズルを解く様子を見ることができるので、興味のある方はぜひ試してみてください。

今後の改善点

• より一般的なパズルサイズ（4×4 など）に対応。
• 最短手数を求めるアルゴリズムの実装。
• Webアプリとしての実装。

今後もスライドパズルの解法について研究していきます！