非共円ポリオミノについて

2023年3月30日 12:16

黒マスがひとつながりになるように配置するペンシルパズルには、「黒マスを2x2のカタマリにしてはいけない」という制約を持つものがあります。2x2禁などと呼ばれ、ぬりかべやTapaなど多くのパズルが該当します。また、1x4禁というものもあります(Aqre)。
この記事では、「共円禁」についての考察をまとめます。ペンシルパズルにおいては、現時点ではあまり見られない制約ではあります。

共円とポリオミノ

この記事では、4つの黒マスの中心が同一円周上にあるか、同一直線上にあるとき、「黒マスが共円である」ということにします。
また、どの4マスも共円になっていない黒マスのカタマリを「非共円ポリオミノ」と呼びます。逆に、ある4マスを選ぶと共円になってしまうものを「共円ポリオミノ」と呼びます。
ポリオミノは連結である必要があることに注意してください。

問1
非共円ポリオミノの取りうる最大の面積はいくつか？もしくは、無制限に大きな非共円ポリオミノを構成できるか？

答はすぐ下に載せます。
例として、ペントミノ12種（FLINPTUVWXYZ）のうち、共円ポリオミノはLIPUVWXYの8種で、非共円ポリオミノはFNTZの4種です。
共円（ボードゲーム）については、以下の記事を参照ください。

非共円ポリオミノ

非共円ポリオミノ(並び雑&抜けあるかも) pic.twitter.com/iTHP8RjgV3
— takmu (@takmu53) March 28, 2023

答1
非共円ポリオミノは有限個であり、その最大の面積は9です。

これら以外に存在しないことを証明するには、以下の画像のような検証を行えばよいです。（なお、上の一覧がすべて非共円ポリオミノであることの証明は、個別に示せばよいため、略します）

面積7では、I,Oテトロミノ（1x4,2x2の長方形）もしくはU,V,Wペントミノを部分的に含むものを除くと、この2種だけが残ります。

面積8以上については、面積7のものに1マスずつ黒マスを追加していくことを考えれば、上図に限られることが分かります。
面積6以下についても全列挙を行えばよいです。

また、検証方法から、以下が分かります。

「I,OテトロミノもしくはU,V,Wペントミノを部分的に含むポリオミノ」と、「傾き2で4連続している部分（上の8,9,10の図の、10についている4つのxのことです）を含むポリオミノ」をポリオミノ全体から除けば、非共円ポリオミノだけが残る。

共円（ボードゲーム）を、「2手目以降は、新しい石は既にある石の隣に置かなくてはならない」という追加ルールで行う場合、
・遅くとも10手目で必ず共円になる
・共円指摘においては、I,OテトロミノもしくはU,V,Wペントミノ、そして傾き2の一直線を探せば十分である
と言い換えることもできます。共円の面白味がかなり失われてしまいましたね。

非共線ポリオミノ

制約を緩め、どの4マスも共線（同一直線上）になっていない黒マスのカタマリを「非共線ポリオミノ」と呼ぶことにします。

問2
非共線ポリオミノの取りうる最大の面積はいくつか？もしくは、無制限に大きな非共線ポリオミノを構成できるか？

これについてもすぐ下に答を載せます。
共円はOKですが、1x4長方形はダメ、斜め一直線も、間に白マスを挟んでいてもダメです。同じ列に最大で3マスしか黒マスが入りません。

面積16以上のもので、13x13盤面に収まるものを全探索すると、非共線ポリオミノは存在しません(semiexp, コードは省略)。
面積16で長辺14以上のものは存在しない（同じ列に最大で3マスしか黒マスが入らないため、短辺6以上が必要で、面積16では足りない。証明は
fffによる。）ため、

答2
非共円ポリオミノは有限個であり、その最大の面積は15です。

全列挙はちょっと大変そうですね…

さらに条件を緩めた場合

「たて、よこ、斜め45度の8方向に4つが同一直線上に並んではいけない」だけでは、以下のように無制限に拡大できます。

また、「傾き2も禁止」「傾き3も禁止」した場合（当然「傾き1/2, 1/3」も禁止）は、やはり面積15が最大です。
なぜなら、例えば「傾き3/2」を禁止する必要はありません。もし「傾き3/2」にのみ違反するポリオミノが存在するとき…

この4点を全て覆う必要があり、面積16に達してしまいます。
「傾き4」やそれ以上も同様です。

したがって、以下が成り立ちます。

「縦」「横」「斜め（傾き1）」「傾き2」「傾き3」の同一直線上に黒マスが4つ存在するポリオミノをポリオミノ全体から除けば、非共線ポリオミノだけが残る。

その他の問題

上記の文から「傾き3」を消しても正しい文になるでしょうか。多分大丈夫そう。証明も、全列挙すればできそうです。
また、短辺7のものが存在するかどうかも未解決ですが、これも無さそうな気がします。
この記事では「共円禁」「共線禁」を扱いましたが、4を5に変えたり、等間隔といった概念を導入したりすることで、様々な問題を考えることが出来ます。ぎりぎり有限個になる制約を考えてみてはいかがでしょうか。

出典

この記事は、2023/3/28のツイートを発端とし、Puzsq Meetsで2023/3/29に行われた議論を、にしなんとかがまとめ・加筆したものです。

この記事が気に入ったらサポートをしてみませんか？