組木パズルをA*と山登り法でプログラムを書いて自作した

作成日: 2023-12-23
今年はパズルにハマった一年でした。
身近に3Dプリンタが設置されたので、なにか面白い印刷物がないかと探すと、Printable Puzzle Projectを見つけました。
権利者に許可を取って、立体パズルの3Dモデルを配布しているサイトです。
これが本当に面白いです。パッキングパズルや知恵の輪的なものなど様々、手を動かす楽しさが詰まっています。
おすすめのパズルの詳細は自分のnoteに譲ります。
このサイトの3Dモデルは、puzzlecadというツールで生成されています。
notion image
使ってみると、ずいぶん簡単に3Dモデルを作ってくれます。こうなれば、3Dパズルを自分で作ってみたくなります。

3D組木パズルを生成する

Rustで組木パズルを解くプログラムを書き、山登り法で組木を生成しました。
notion image

組木を解く

ランダムに組木を生成して、それが解けるかどうか、何手かかるかを求めます。
解く組木は、立方グリッド上、4x4x4 ポリキューブのものに限りました。一部の組木では回転操作が要求されるのですが、実装が難しすぎるので諦めました。
基本的には愚直な幅優先探索ですが、外れたピースが多い状態ほど優先して探索するA*で実装しました。

山登り法で組木を生成する

notion image
組木と言えない単なる積み木から始めて、解くために必要な手数が大きくなるように、山登り法でランダムに組木を改変します。
連結性が途切れないように組み木の1セルを選んで所属を置き換える、を数回繰り返して、新しい組木を作ります。実装した組木ソルバーに投げて、手数がこれまでより必要な組木であるとわかれば、その組木から次の組木を作ります。

完成物

notion image
3Dプリンタで印刷するとこんな感じです。眼の前に現れると嬉しいですね。
notion image
作った組木を組み上げると、ちゃんと立方体に収まりました。

これから

試しに生成した組木は、4手数しかかからないのですが、組木的な振る舞いをしていて嬉しかったです。
ただ、感動した4x4x4組木(Quickstepなど)は10手数以上かかり、到底及ばない手数なので、より良いパズルのためには探索を頑張る必要があると思います。
回転を認めるソルバーを実装するのはとてもハードなタスクなので、いつかできると嬉しいですね。