STAR FORMING REGION を SCIPで その１

パズル

MINEさんの

STAR FORMING REGION の解出しを手伝った。

正五角形をつなぎ合わせたパーツを枠におさめるパズル。

正五角形、２個、３個、４個でできるポリ五角形、全種類。

と星。

ポリオミノと違い、どうしても隙間ができるが、辺と辺を合わせて置くことを考えると、そこそこの秩序？（キメキメ度？）で置かれていく。そして、枠に詰めようとすると、ギュッとしてその度合いが高くなるのだった。

置き方にどんなんがあるか、プログラムで調べる！

大きな流れで、

①正五角形の置かれる位置の候補を出す。

②正五角形やパーツが重ならないように置いて行き、詰めあがりの置き方を求める。

ということを行う。

今回もSCIPという整数計画ソルバーを使って解いた。

置き場所の位置のxy座標が整数ではないが（笑）。

正五角形の候補は、全部書き出すとこんな感じ。

盤面は大きいのと小さいのがあり、その大きい方。

正五角形の置く場所候補を絞り込んだのでこんな感じで、もっと増やすと真っ黒になるくらい。

次の記事で計算の仕方を軽く説明する。

つづく

更新状況