一昨日思いついたのだけどもコードを書く時間が作れなくていまやっとできた。 道の幅を1、一番小さい正方形を黄金比gとした場合に、g^nのサイズの正方形のうちでこういうきっちりした並べかたができるのはg^1, g^3, g^4の3通りしかない。そこでその3種類の正方形で与えられた長方形を埋め尽くすタイリングを考えた。 もちろん他の評価関数がないとみっちり最小サイズの正方形を並べるなどで埋め尽くすこと自体はできてしまうので「同じサイズの正方形が並ぶと減点1」という評価関数にした。上の図はまだ計算の途中なので左上に大きな正方形が並んでしまっている。 9x7だとこんな感じ。
帰ってきた妻に見せたら「豚足っぽい」と言われた… ランダムに色を塗るとこんな感じだけど、どうせなら4色選んで同じ色が隣接しないように塗るとかした方がいいなぁ。
関連 ルジンの問題
- こちらは道の太さは0である代わりに、同じサイズの正方形は1個しかない。