組木パズルをA*と焼きなまし法でプログラムを書いて自作した
作成日: 2023-12-23
今年はパズルにハマった一年でした。
身近に3Dプリンタが設置されたので、なにか面白い印刷物がないかと探すと、Printable Puzzle Projectを見つけました。
権利者に許可を取って、立体パズルの3Dモデルを配布しているサイトです。
これが本当に面白いです。パッキングパズルや知恵の輪的なものなど様々、手を動かす楽しさが詰まっています。
おすすめのパズルの詳細は自分のnoteに譲ります。
このサイトの3Dモデルは、puzzlecadというツールで生成されています。
使ってみると、ずいぶん簡単に3Dモデルを作ってくれます。こうなれば、3Dパズルを自分で作ってみたくなります。
3D組木パズルを生成する
Rustで組木パズルを解くプログラムを書き、山登り法で組木を生成しました。
組木を解く
ランダムに組木を生成して、それが解けるかどうか、何手かかるかを求めます。
解く組木は、立方グリッド上、4x4x4 ポリキューブのものに限りました。一部の組木では回転操作が要求されるのですが、実装が難しすぎるので諦めました。
基本的には愚直な幅優先探索ですが、外れたピースが多い状態ほど優先して探索するA*で実装しました。
焼きなまし法で組木を生成する
組木と言えない単なる積み木から始めて、解くために必要な手数が大きくなるように、山登り法でランダムに組木を改変します。
連結性が途切れないように組み木の1セルを選んで所属を置き換える、を数回繰り返して、新しい組木を作ります。実装した組木ソルバーに投げて、手数がこれまでより必要な組木であるとわかれば、その組木から次の組木を作ります。
完成物
3Dプリンタで印刷するとこんな感じです。眼の前に現れると嬉しいですね。
作った組木を組み上げると、ちゃんと立方体に収まりました。
これから
試しに生成した組木は、4手数しかかからないのですが、組木的な振る舞いをしていて嬉しかったです。
ただ、感動した4x4x4組木(Quickstepなど)は10手数以上かかり、到底及ばない手数なので、より良いパズルのためには探索を頑張る必要があると思います。
回転を認めるソルバーを実装するのはとてもハードなタスクなので、いつかできると嬉しいですね。