【へやわけ】四方壁のMX値の解決

へやわけにおいて、四方壁のMX値は正方形盤面のみ確定していた (i.e., 黒マスの上限と具体的構成が求められていた)。

今回は、一般のケースについて四方壁のMX値を確定する。

これまでの結果：

黒マス最密充填のはなし - SP1のぱずるにっき (hatenadiary.jp)

参考：

超超へやわけMX - にしなん記録室 (scrapbox.io)

Teal's Mini Heyawake Guide :)) - Google ドキュメント

【へやわけ】角5x48に黒マスが87個しか入らないこと - SP1のぱずるにっき

特殊なケース
一般のケース
- 余裕値が正のケース
- 余裕値が $0$ のケース

特殊なケース

辺の長さが $7$ 以下のとき、ペナルティの議論で得られる上界がMX値にならない場合がある。それらを特殊ケースとして処理する。

ケースS-1：$1\times L$

$L=1$ のときMX値は $1$, $L\geq 2$ のときMX値が $2$ であることが容易にわかる。

ケースS-2：$2\times L$

$2\times 2$ の領域に黒マスが $2$ 個入らないことに注意すると、MX値が $\lceil L/2 \rceil$ であるとわかる。

構成は容易 (略)。

ケースS-3：$3\times L$

$3\times 2$ の領域に黒マスが $3$ 個入らないことに注意すると、MX値が $2\cdot \lceil L/2 \rceil$ であるとわかる。

構成は容易 (略)。

ケースS-4：$4\times L$

$L=1, 2$ のとき、MX値はそれぞれ $2$, $2$ である。

以下 $L\geq 3$ とする。

盤面全体のペナルティ許容値は $3L+1 + 2 \cdot \lceil L/2 \rceil$ である。

盤面を上下 $2$ 行ずつに分け、それぞれに入る黒マスの個数を $C_1$, $C_2$ とおく。

なお $C_1 + C_2$ としてありうる最大が MX 値である。

また最も上の行・最も下の行に入る黒マスの個数を $r_1$, $r_2$ とおく。

このとき Tobo Theorem により、以下の式が成り立つ：

$r_1 \leq L - C_1 +1$
$r_2 \leq L - C_2 +1$

最も上の行・最も下の行に入る黒マスの個数が少ないとペナルティのロスが生まれるが、その値はそれぞれ $\lceil L/2 \rceil -r_1$, $\lceil L/2 \rceil -r_2$ となる。

したがって、上記のペナルティを評価して以下の式を得る：

$4(C_1 + C_2) \leq 5L+3$

この式から MX値の上限が以下のように求まり、また以下に示す構成でこれらがMX値であることがわかる。

$L$	$C_1+C_2$ の上限
$4m$	$5m$
$4m+1$	$5m+2$
$4m+2$	$5m+3$
$4m+3$	$5m+4$

ケースS-5：$5\times L$

$L=1, 2$ のとき、MX値はそれぞれ $2, 3$ である。

以下 $L\geq 3$ とする。

盤面全体のペナルティ許容値は $4L+2 + 2 \cdot \lceil L/2 \rceil$ である。

盤面を上 $2$ 行・中央 $1$ 行・下 $2$ 行と分け、それぞれに入る黒マスの個数を $C_1$, $X$, $C_2$ とおく。

なお $C_1 + C_2 + X$ としてありうる最大が MX 値である。

また最も上の行・最も下の行に入る黒マスの個数を $r_1$, $r_2$ とおく。

このとき Tobo Theorem により、以下の式が成り立つ：

$r_1 \leq L - C_1 +1$
$r_2 \leq L - C_2 +1$

したがって、上記のペナルティを評価して以下の式を得る：

$4(C_1 + C_2 + X) \leq 6L+4 + X$

加えて、$X\leq \lceil L/2 \rceil$ と評価できる。

以上より MX値の上限が以下のように求まり、またこれらは上下壁の $13$ in $5\times 7$ を並べることで構成可能なため、MX値となる。

$L$	$C_1+C_2+X$ の上限
$8m$	$13m+1$
$8m+1$	$13m+2$
$8m+2$	$13m+4$
$8m+3$	$13m+6$
$8m+4$	$13m+7$
$8m+5$	$13m+9$
$8m+6$	$13m+10$
$8m+7$	$13m+12$

くりかえし：

ベースケースは省略。

ケースS-6：$6\times L$

$L=1, 2$ のとき、MX値はそれぞれ $2, 3$ である。

以下 $L\geq 3$ とする。

盤面全体のペナルティ許容値は、$L$ が奇数のとき $6L+2$, $L$ が偶数のとき $6L+1$ である。

よってMX値の上界は $2L$ である。

また以下のように構成できるため、MX値そのものとなる。

ケースS-7：$7\times L$

$L=1, 2, 3, 4$ のとき、MX値はそれぞれ $2, 4, 8, 9$ である。

以下 $L\geq 5$ とする。

盤面全体のペナルティ許容値は $6L+2 + 2 \cdot \lceil L/2 \rceil$ である。

盤面を上 $2$ 行・中央 $3$ 行・下 $2$ 行と分け、それぞれに入る黒マスの個数を $C_1$, $X$, $C_2$ とおく。

なお $C_1 + C_2 + X$ としてありうる最大が MX 値である。

また最も上の行・最も下の行に入る黒マスの個数を $r_1$, $r_2$ とおく。

このとき Tobo Theorem により、以下の式が成り立つ：

$r_1 \leq L - C_1 +1$
$r_2 \leq L - C_2 +1$

したがって、上記のペナルティを評価して以下の式を得る：

$4(C_1 + C_2 + X) \leq 8L+4 + X$

加えて、$X$ は以下のように評価できる：

$L=4k$ のとき、$X\leq 5k$
$L=4k+1$ のとき、$X\leq 5k+1$
$L=4k+2$ のとき、$X\leq 5k+2$
$L=4k+3$ のとき、$X\leq 5k+4$

以上より MX値の上限が求まる。ほとんどのケースでその上限がMX値そのものとなるが、$L=16m$ の場合のみ実現できずひとつ減る。以下でそのことを示す。

なお、構成は上下壁の $37$ in $7\times 15$ を並べることで可能である。

$L$	$8L+4+X$ の上界	MX値
$16m$	$148m+4$	$\mathbf{37m}$
$16m+1$	$148m+13$	$37m+3$
$16m+2$	$148m+22$	$37m+5$
$16m+3$	$148m+32$	$37m+8$
$16m+4$	$148m+41$	$37m+10$
$16m+5$	$148m+50$	$37m+12$
$16m+6$	$148m+59$	$37m+14$
$16m+7$	$148m+69$	$37m+17$
$16m+8$	$148m+78$	$37m+19$
$16m+9$	$148m+87$	$37m+21$
$16m+10$	$148m+96$	$37m+24$
$16m+11$	$148m+106$	$37m+26$
$16m+12$	$148m+115$	$37m+28$
$16m+13$	$148m+124$	$37m+31$
$16m+14$	$148m+133$	$37m+33$
$16m+15$	$148m+143$	$37m+35$

くりかえし：

ベースケース：

ケースS-7'：$7\times L$ で $L=16m$ のとき

$37m+1$ 個の黒マスが入らないことを示す。

これは上で示したMX値の上限の評価における等号のケースだが、これが成り立つには $X = 20m$ で、かつ上辺・下辺以外でペナルティのロスが起きてはいけない。

このとき、中央 $3$ 行を $2$ 列ずつで分割すると、その両端のうちどちらかは $3$ 個入らないといけないとわかる (空中 $3\times 4$ に黒マスが $6$ 個入らないため、両端以外で $20m-5$ 個までしか入らない)。

すると、 $3$ 個入れる方で辺にペナルティのロスが起こってしまう。

したがって等号は成立しない。

$37m$ 個入れる構成は上記の通り。

一般のケース

ここからは一般の盤面 $m\times n$ について考える。

なお、上で幅が小さい場合は解決したため、$ m $, $n$ はともに $8$ 以上としてよい。

盤面全体でのペナルティ許容値は、ループが $ (m - 1)(n-1) $ , 辺で $2 (\lceil m/2 \rceil + \lceil n/2 \rceil) $ である。偶奇で場合分けすると以下の通り：

$ m $, $n$ がともに奇数のとき、許容値は $mn+3$
$ m $, $n$ の片方が奇数・もう片方が偶数のとき、許容値は $mn+2$
$ m $, $n$ がともに偶数のとき、許容値は $mn+1$

なお $ m $, $n$ がともに奇数のとき、外周でロスなく置くとループが発生するため、ペナルティ $1$ ロスが確定することに注意。

ペナルティいっぱいまで黒マスを詰めたときの残りを余裕値とよぶ。$\mod 6$ で場合分けして余裕値を求めると、以下のようになる：

色付きのところがロスが許されないケースである。なお緑のところは余裕値 $1$ だが、上で述べた奇数・奇数の外周ロスパターンに該当することに注意。

余裕値が正のケース

上記の表で余裕がある場合、外周でロスなく詰めたのち空中の部屋の構成を用いることで、四方壁でも構成可能である。

偶奇で場合分けして確認しておく。

ケースA-1：奇数・奇数で余裕値 $2$ 以上

外周にロスなく詰めると、ループでの消費が $1$ あった上で空中に領域が残る。

奇数・奇数の空中領域で余裕が $1$ 以上あるときは黒マスの配置が可能なことが知られている。

ケースA-2：$\mod 6$ で $(5, 5)$

この場合、外周にロスなく詰めると、空中領域は打ち上げ花火以外詰められなくなってしまう。

なので外周で $1$ ロスを許容して汎用的な構成をする。

具体的には、以下のように規則的に構成するとよい。下のケースB-2に近い構成となる(詳細略)：

ケースA-3：$\mod 6$ で $(1, 1)$

この場合も、外周にロスなく詰めると、空中領域は打ち上げ花火以外詰められなくなってしまう。

なので外周で $1$ ロスを許容して汎用的な構成をする。

具体的には、以下のように規則的に構成するとよい。下のケースB-3に近い構成となる(詳細略)：

ケースB-1：偶数・奇数で余裕値 $2$ 以上

奇数辺にロスなく詰め、偶数辺には以下の図のように埋める。

空中の領域に、A面だけ(市松模様に塗って片側の色だけ)の黒マス構成を入れるとよい。

余裕値が $1$ の時は少しやっかい。具体的には $\mod 6$ で $(1, 2), (5, 4)$, およびその入れ替え。対称性から先の二つを解決する。

ケースB-2：$\mod 6$ で $(1, 2)$

以下 $(r, c)$ マスとは上から $r$ 行目・左から $c$ 列目のマスのこととする。

まず奇数辺をロスなく詰め、偶数辺は右に寄せて詰める。

そして、$(2, 3)$ マス, $(m - 1, 3)$ マスを黒にして、空中 $r+c$ が奇数のマスを一旦黒くする。

ここからしまつぶしをして構成する。

まず $5$ 行目の黒マスを先に左から消す。このとき、黒マスのナナメの連結は残す。

次に $5$ 列目を下から、$8$ 列目を上から ($7$ 行目から)、と消していき、これを $n-6$ 列目まで行う。ここも黒マスのナナメの連結は残す。

その後、$(8, n-3)$, $(11, n-4)$, ... $(m-5, n-3)$ と消していって、最後に $(m-4, n-4)$ を消す。

以上で、最後に消したところのみの $1$ ロスで構成できた。

ケースB-3：$\mod 6$ で $(5, 4)$

上のケースとほぼ同じ構成が使える。変えるのは最後のみ。

列で消すのを $n-8$ 列目までで止め、残りは $(8, n-5)$, $(8, n-3)$, $(11, n-6)$, $(11, n-4)$, ..., $(m-6, n-6), $(m - 6, n - 4)$ と消して、後は $(m - 4, n-4)$, $(m-3, n-5)$ を消す。

以上で、最後に消したところのみの $1$ ロスで構成できた。