まとめてなかったので。
問題
n × n のマス目について、マスのいくつかを黒く塗る。このとき、
・黒マスはタテヨコに隣接しない (隣接禁)
・白マスはひとつながりになる (黒マスによる分断禁)
ようにする。この条件のもと黒マスを最大何個まで増やせるか?
背景
いわゆる「黒マスの最密充填問題」です。この問題は、たとえばへやわけを考えると自然に出てくる疑問でしょう。
へやわけにおける黒マスの最密充填については、すでに先人によって解決済みです。
超へやわけ MX というサイトで公開されていました (現在はアーカイブから閲覧できます)。
大雑把に作戦を振り返ると、分断禁を無視して詰めるだけ詰めたところから、黒マスでできたシマをつぶしていく、というものでした。
ただしこれは辺を考慮しない「空中のへや」についての結果であり、辺がある場合にはまだ完全な解決がされていません。これは「しまつぶし」作戦が辺がある場合に機能しないという問題があるためです。
新たな上限
最近になって、黒マスの個数の評価について新たな知見が得られたので、まとめます。
言及があったのはこちら:
何もない状態では100個の白マスが180本の辺を介してつながっている状態、と考えます。
— jkr_2255(すんぶ) (@jkr_2255) 2019年2月3日
黒マスを34個入れると、残り66マスに対して辺は64本以下(角4つの黒マスで8本、辺に12個の黒マスで36本、中の黒マス18個で72本を消費)となるので、つながりません。
https://t.co/1dcdPoxlXL
— utime (@utime1204) 2020年3月8日
多分これと本質的には同じことをしている(けど読んでない)
頂点に入る黒マス数の最大は4,頂点または辺に入る黒マス数の最大は16。
白マスの中心を頂点、隣り合う白マスを結んだものを辺とするグラフを考える。黒マスが1つ増えるたび辺が4(or3or2)、頂点が1減り、
これらをまとめます。
盤面の双対グラフを考えます。すなわちマスを頂点、隣接関係を辺とするグラフを考えます。問題をグラフの言葉に翻訳すると次の通りです:
グラフを連結に保ったまま頂点を除去したい。ただし最初の時点で隣り合う頂点を両方取り除くことはできない。取り除ける最大個数は?
取り除くにあたり、X = E - V + 1 という値を設定します。E は辺の本数、V は頂点の個数です。さて、グラフが連結ならばこの値は 0 以上です (木の場合が最小)。また角・辺・内側の頂点を取り除くごとに、B はそれぞれ -1, -2, -3 されます。すなわち B が 0 以上なまま何個減らせるか考えることで、上限が得られます。
さて、取り除く頂点について角・辺のものは少ないので、内側の頂点の -3 を基準に考えます。すると、角・辺の頂点を取り除くごとにそれぞれ +2, +1 のボーナスが得られると思えます。よって盤面に応じて取りうるボーナスの最大値 MB がわかれば、黒マスの上限が (X+MB)/3 と計算できます。
また、X はいわゆる「平面グラフの穴の個数」を表しています (オイラー標数でググろう)。MB を計算する中でループができるならそのぶん X の許容値が減ってしまうので、考慮する必要があります。
個々のケース
n = 1, 2, 3の場合は最大個数 1, 1, 4 であることが簡単に検証できます。以下 n は 4 以上とします。
MB を具体的に計算します。
・n が奇数のとき
外周に 1つ飛ばしで黒マスを置くのが (ループを考慮しないなら) MB 最大となります。実際にはループができるので MB として 1 つ損しますが、外周を動かしても 1 以上減るので、最善 (のひとつ) であることは変わりありません。この場合 MB = 2n+1 です。
・n が偶数のとき
角のマスはとなりの 2 マスとくっつけて評価するとするとよいです。この L 字 に 黒マスが 1 個しか置けません。これを使って、外周全体で MB = 2n が最善となります。角すべてに置くと最善です。
これで上限が計算できます。n × n のマス目で X = (n-1)^2 なので (穴の個数)、上限は
・n が奇数のとき (n^2 + 2) / 3
・n が偶数のとき (n^2 + 1) / 3
となります (n は 4 以上)。なお、実際には余りが出るかもしれません。
構成
実はこの上限がかなり強く、そのまま構成できそうなことが分かっています。以下、分かっている構成を上げておきます。なお 3 で割っている都合上 mod 3 で挙動 が変わるので、さらに場合分けします。
・2, 4 mod 6 のとき
上限は (n^2 -1) / 3 です。ループや角・辺のロスの余裕が 2 あります。このケースは次のように 6 ずつ増やして構成できます。(超へやわけ MX の構成を参考にしました。)
・0 mod 6 のとき
上限は n^2 / 3 です。ループや角・辺のロスの余裕が 1 あります。このケースは次のように構成できます。
・3 mod 6 のとき
上限は n^2 / 3 です。ループや角・辺のロスの余裕が 3 あります。このケースは外周をフルに埋めて空中 (6n + 5) × (6n + 5) を作ればよいです。具体的構成は超へやわけ MX を参考にしてください。
・1, 5 mod 6 のとき
上限は (n^2 +2) / 3 です。ループや角・辺のロスの余裕が 1 あります。このケースの一般的な構成はまだ未解決ですが、n が 19 以下ですでに構成しており、肯定的に解決されそうです。
できるに1票 pic.twitter.com/e1fb8niMPG
— utime (@utime1204) 2020年4月5日
209in25x25 とりあえず打ち上げ花火系列の周囲に10マスなら構成できる(応用がいまいち効かない詰め方だ…) pic.twitter.com/NKFf14u5w4
— にしなんとか (@chebunanntoka) 2020年4月5日
【追記】
にしなんとかさんが一般の構成を見つけたようです!
1 mod 6 完全な理解です pic.twitter.com/n8LS6uK5qN
— にしなんとか (@chebunanntoka) 2020年4月5日
5 mod 6 も完全に理解した pic.twitter.com/kJ0a8qzyOP
— にしなんとか (@chebunanntoka) 2020年4月5日
これで正方形の場合に完全解決しました!
結論
結果をまとめると、n × n の盤面での黒マス最密の個数は
・0 mod 3 のとき n^2 / 3 個
・2, 4 mod 6 のとき (n^2 - 1) / 3 個
・1, 5 mod 6 のとき (n^2 +2) / 3 個
となります。
さらなる話題
さらなる展開をいくつか書いておきます。
・まずは 1, 5 mod 6 のケースの解決
・長方形の場合の解決
これはすぐに解決できそう。偶数ケースは似たような構成、奇数でどうなるか?
・最密充填での解の個数
最密充填にどれほど自由度があるか?へやわけの問題に応用できるか?全列挙できそうだが果たして。
・辺が一部のケース
周りに仮の頂点を置くことで解決できそう。上限が一致しないケースが出るかもしれない (cf. にしなんとかさんが調べていた、辺 5*n ケースがどうか?)。
・一般グラフへの応用
黒マスの配置は「強独立集合」ともいえる (補グラフが連結という条件を付与)。一般のグラフで最大強独立集合がどうなるか?似たような評価ができるのかどうか。