黒マス最密充填のはなし

まとめてなかったので。

 

問題

n × n のマス目について、マスのいくつかを黒く塗る。このとき、

・黒マスはタテヨコに隣接しない (隣接禁)

・白マスはひとつながりになる (黒マスによる分断禁)

ようにする。この条件のもと黒マスを最大何個まで増やせるか?

 

背景

いわゆる「黒マスの最密充填問題」です。この問題は、たとえばへやわけを考えると自然に出てくる疑問でしょう。

 

へやわけにおける黒マスの最密充填については、すでに先人によって解決済みです。

web.archive.org

 

へやわけ MX というサイトで公開されていました (現在はアーカイブから閲覧できます)。

大雑把に作戦を振り返ると、分断禁を無視して詰めるだけ詰めたところから、黒マスでできたシマをつぶしていく、というものでした。

ただしこれは辺を考慮しない「空中のへや」についての結果であり、辺がある場合にはまだ完全な解決がされていません。これは「しまつぶし」作戦が辺がある場合に機能しないという問題があるためです。

 

新たな上限

最近になって、黒マスの個数の評価について新たな知見が得られたので、まとめます。

言及があったのはこちら:

 

 

これらをまとめます。

 

盤面の双対グラフを考えます。すなわちマスを頂点、隣接関係を辺とするグラフを考えます。問題をグラフの言葉に翻訳すると次の通りです:

グラフを連結に保ったまま頂点を除去したい。ただし最初の時点で隣り合う頂点を両方取り除くことはできない。取り除ける最大個数は?

 

取り除くにあたり、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 の構成を参考にしました。)

f:id:SP1_puzzle:20200405183330p:plain

f:id:SP1_puzzle:20200405183343p:plain

f:id:SP1_puzzle:20200405183358p:plain

f:id:SP1_puzzle:20200405183414p:plain

 

・0 mod 6 のとき

上限は n^2 / 3 です。ループや角・辺のロスの余裕が 1 あります。このケースは次のように構成できます。

f:id:SP1_puzzle:20200405183540p:plain

f:id:SP1_puzzle:20200405183553p:plain

 

・3 mod 6 のとき

上限は n^2 / 3 です。ループや角・辺のロスの余裕が 3 あります。このケースは外周をフルに埋めて空中 (6n + 5) × (6n + 5) を作ればよいです。具体的構成は超へやわけ MX を参考にしてください。

 

・1, 5 mod 6 のとき

上限は (n^2 +2) / 3 です。ループや角・辺のロスの余裕が 1 あります。このケースの一般的な構成はまだ未解決ですが、n が 19 以下ですでに構成しており、肯定的に解決されそうです。

 

【追記】

にしなんとかさんが一般の構成を見つけたようです! 

 

 

これで正方形の場合に完全解決しました!

 

結論

結果をまとめると、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 ケースがどうか?)。

 

・一般グラフへの応用

黒マスの配置は「強独立集合」ともいえる (補グラフが連結という条件を付与)。一般のグラフで最大強独立集合がどうなるか?似たような評価ができるのかどうか。