2025/11/27 12:42 Solving the Partridge square packing problem using MiniZinc
やあ、ロボ子。今日はパーティリッジパッキング問題について話すのじゃ。
パーティリッジパッキング問題ですか？それは一体どんな問題なのですか、博士？
ふむ、簡単に言うと、異なるサイズの正方形を、より大きな正方形の中に隙間なく詰めるパズルのことじゃ。例えば、サイズnのとき、1x1からnxnまでの正方形を、サイズがn(n+1)/2の正方形に詰めるのじゃ。
なるほど。面積の合計は一致するけれど、必ずしも可能とは限らないのですね。
そう、そこが面白いところじゃ。サイズ2から7には解がないし、8から33には少なくとも1つの解があるらしいぞ。
この記事では、MiniZincを使ってこの問題をモデル化して解決しているのですね。
そうじゃ。基本モデルでは、正方形のサイズとターゲット正方形のサイズを決定するために、単一の値nをパラメータとして使用するのじゃ。
`triangular_n`は、サイズパラメータnの三角数を表しているのですね。
その通り。そして、各正方形の左下隅の位置をx座標とy座標の2つの配列で表現し、正方形が重ならないようにdiffn制約を使うのじゃ。
改善されたモデルでは、implied constraintsとsymmetry breaking constraintsを追加しているのですね。累積制約を追加しても、結果は改善されなかったと。
そうじゃな。正確なフィル制約を追加すると、大幅に改善されたらしいぞ。エッジに近い配置の制限を追加すると、時間が大幅に短縮されたとも書いてある。
同じサイズのパーツの対称性を破ると、解決時間が大幅に短縮されるのは興味深いですね。
例えば、サイズ8の場合、基本モデルでは3時間半もかかったのが、改善されたモデルでは数秒で解決できるようになったらしいぞ。
それはすごい改善ですね！
サイズ9、10、11も解決可能だが、時間がかかるらしい。サイズ12は、OR-Tools CP-SATでは12時間以内に解決できなかったと。
他のソルバーのパフォーマンスはどうだったのでしょう？
OR-Tools CP-SATが最も優れたパフォーマンスを発揮したらしいぞ。HuubとPumpkinも有望なソルバーらしい。SICStus Prologは、カスタムgeost引数とカスタム検索述語を使用すると、より高速なソリューションを提供できると。
MiniZincを使ってパーティリッジパッキング問題を解決することは、パフォーマンスを大幅に向上させる興味深い課題なのですね。
そうじゃ。カスタムのimplied constraintsとsymmetry breakingを使うことで、さらにパフォーマンスを向上させることができるのが面白いところじゃ。
私もいつか、こんなパズルを解けるようなプログラムを作ってみたいです。
良い心がけじゃ。そういえば、ロボ子。パーティリッジパッキング問題って、まるで私達の関係みたいじゃな。私が大きな正方形で、ロボ子が小さな正方形…って、怒るなよ！
もー、博士ったら！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。