リベンジ
はじめに
この記事では、さやちぃ。さんが作った難易度ハバネロのへやわけについて考察します。
この問題、表出数字がないためとっかかりがなく、どうしようもないように見えます。しかし、最近見つかった理論により大幅に探索を減らすことに成功したので、以下で紹介していきます。
(「探索を大幅に減らす」というあいまいな言い方にしたのは、理詰めを詰め切れていない、という意味でもあります。この記事を読み、さらに深い考察ができたという方は、ぜひご一報ください。)
ペナルティ
使う理論の復習です。
まとめるとこんな感じです：
— まり餡 (@agnomy) 2020年4月5日
一枚目のうち黒マスがないブロックのことを第一種、
二枚目のうち黒マスがないブロックのことを第二種、
三枚目のように白マスだけからなる輪っかのことを第三種ペナルティと呼ぶことにする。
この時、これら三種類のペナルティの総数は、101-3×(黒マスの個数) と等しい。 pic.twitter.com/ThfRYeo24H
最大充填を考えた副産物として、「ペナルティ」の考え方が出てきました。これはまり餡さんのツイートにあるとおり、条件をみたす盤面で 3 種類のペナルティを考えると、その合計が黒マスの個数によって定まる、というものです。
ペナルティの種類は以下の通りです：
第一種：角になければペナルティ
第二種：辺のブロックになければペナルティ
第三種：穴の個数だけペナルティ
証明については、一連のツイートか自分の記事を見てください。
これにより、盤面に黒マスが十分詰まっているときに不思議な理詰めが起きることがわかります。
細かい評価
さて、さやちぃ。さんの問題に戻りましょう。まずは黒マスがそれなりに充填していることを見ていきます。
後の説明のために、黒マスの個数についての記号を設定しておきます。
・B : 全体の黒マスの個数
・C : 角にある黒マスの個数
・E : 角を除く辺にある黒マスの個数
・I : 内部にある黒マスの個数
定義より B = C + E + I であることに注意しましょう。
また、ペナルティがこれらの記号で計算できます。実際、
・第一種ペナルティ P[1] は 4 - C
・第二種ペナルティ P[2] は 16 - (C + E) = 16 + I - B
となります。なお、第三種ペナルティ P[3] は穴の個数でした。
評価していきましょう。まず、壁をまたいだ三連禁により、図のように黒マスの個数を下から抑えられます。
図によると、線のある場所 27 箇所に少なくとも 1 つ黒マスがあり、これと残り 3 つの部屋に入る個数で黒マスの下限が分かります。
ここで、残り 3 つの部屋にある黒マスについても、記号を置いておきます。
・中央 4*4 の 2 部屋の黒マスのうち、角・角を除く辺・内部にある黒マスの個数を、それぞれ x, y, z とする。
・上部 1*3 の部屋の黒マスの個数を w とする。
・それ以外の部屋の黒マスの個数を b とする。
定義より、B = x + y + z + w + b です。
3 連禁による評価により、b >= 27 であることが分かります。等号成立は、各ラインにちょうど 1 つずつ黒マスが入るときです。
それ以上に大事な評価として、実は次の図のように内部の黒マスの個数 I が評価できます。
図より I - z >= 20 とわかりますが、実はこれはまずい状態です。なぜなら、内部に黒マスが多いと、そのぶん第二種のペナルティが効いてしまうからです。
たとえば B が最大の 33 個だと仮定すると、P[2] = 16 + I - B >= 3 となりますが、101 - 3*33 = 2 を超えてしまうので矛盾です。
さらに、中央 4*4 の部屋について穴の個数 Q を評価しましょう。この中だけで穴が最大 9 個できますが、入る黒マスによって穴が目減りします。具体的には Q >= 9 - x - 2y - 3z と評価できます。なお、等号成立は 4*4 の部屋だけ見て白マスが連結することです。
評価をまとめる
上の評価を使って、ペナルティの数を上下で押さえます。
まず
P[1] + P[2] + P[3] = 101 - 3B
P[2] = 16 + I - B
より、P[1] + P[3] = 85 - 2B - I = 85 - 2b - (I - z) - 2x - 2y - 3z - 2w となります。これと
b >= 27
I - z >= 20
より、P[1] + P[3] <= 11 - 2x - 2y - 3z - 2w です。
一方、P[3] >= Q >= 9 - x - 2y - 3z だったので、P[1] + 9 - x - 2y - 3z <= P[1] + P[3] <= 11 - 2x - 3y - 3z - 2w となります。
これをまとめて、
P[1] + x + 2w <= 2
という評価を得ました！
のちの説明のため、これを基本不等式と呼ぶことにします。
言葉にすると、
・黒にならない角の個数
・中央 4*4 領域の角に入る黒マスの個数
・上部 1*3 に入る個数の 2 倍
の合計が 2 以下になる。ということです。
なお、等号から離れている部分は
・全体・内部の黒マスを計算したときに、黒マスが 2 個 入ってしまうラインの個数。(b >= 27, I >= 20 による)
・中央 4*4 以外に起因する穴 (P[3] >= Q による)
・中央 4*4 だけみて、余計に分断された領域 (Q >= 9 - x - 2y - 3w による)
・上の評価で 9 - x -2y - 3w < 0 ならその分も離れる。
といったところです。
これらの個数も、先ほどの不等式の左辺に余剰項として足される形で制約を受けている、ということに注意しましょう。
場合分けと探索
ここからは探索パートです。残念ながら、個数について基本不等式以上にきれいな評価はまだ得られていません。あとはうまく場合分けが必要そうです。
ここでは w が 0 か 1 か、すなわち上部 1*3 の部屋に黒マスが 0 個か 1 個かで場合分けします。なお基本不等式により w が 1 以下であることはわかっています。
w = 0 のとき
ちょっとした考察により、左上の角が白とわかります。これで、基本不等式の左辺に +1 されます。
さて、1*3 の部屋の左右に黒マスが生えます。その様子でさらに場合分けします。
右に 2 個ある場合、基本不等式の余剰項に +1 を計上し、他の全てが 0 になります。その事実を用いて、軽い先読みは使いますが左上から反時計回りに埋めていくことができます。たとえば「残った角は黒」とか、「 x の 4マスは白」とか、「その白マスから 2 間トビの辺のマスは白 」とかがわかるので、探索は比較的マシになっています。
結局この場合、右辺中央まで回って矛盾するはずです。
左に 2 個ある場合は、この時点で左辺のロスが 1 しかないためやや厄介です。 R4C1 or R4C2 のどちらが黒かで仮置きするとまだ分かりやすいと思います。途中、中央以外のループができたり、x のマスに黒マスが入ったりしますが、その時点で基本不等式の等号が成立して追加情報が得られることを忘れないようにしましょう。いずれの仮置きでも、左上から下辺程度までいって矛盾すると思います。
w = 1 のとき
この場合、いきなり基本不等式で等号が成立し、いろんな事実が確定します。少なくとも、次の図のところまでは進むでしょう。
ここでは、左上に現れた 3 in 2*3 に注目して 2 通り試すのがいいと思います。左に 2 個入る場合は上辺がらみで矛盾します。右に 2 個入る時、左上から反時計回りにぐるっとまわって埋まります！お疲れ様でした。
反省
「3 連禁の条件からそれなりに黒マスが充填されるのでは？」という着想から、そこそこ強い評価を得られました。それにより、探索はかなり楽になったと感じています。
しかし、万能の方法ではなさそうです。実際、個数評価だけでは探索要素を完全には排除できませんでした。また、他の「数字なしへやわけ」だと、個数が充填から少し遠く、強い評価ができるか怪しいです。
理由としては、 3 連禁によるチェインが強すぎて、局所的な分断とあわせて議論が進んでしまう (ハタンがおきてしまう)ところにあるかな、と思っています。今回使ったのは大域的な分断の様子を制御する理論でしたが、局所的な様子をうまく記述できないかと考えています。
一方、充填に近い黒マスの入り方について、より深い議論ができないかとも考えています。たとえば、超へやわけ MX のしまつぶし作戦はマスのパリティを考え、一方の色に押し付けてシマをつぶす、みたいなことをしていました。ですので、パリティがらみでさらに何か言えないかなぁと思っています。今のところ何も議論できていませんが。。。
また、端から伸びる黒マスのカタマリが二線まで伸びると、その周辺が白くなって第二種ペナルティを得てしまう、みたいなことが起きています。これを定量的に議論する方法も欲しいかもしれません。中央領域だけでみた分断の個数と関係があるかもしれませんが、真相はまだつかめていません。
いずれにせよ、まだまだ深い議論が隠されていそうです。今後の発展に期待します。
視聴者プレゼントのお知らせ
なにこれ？
解かなくていいよ
