【へやわけ】川の渡り方その1・基本理論編
みんなで渡ろう
はじめに
本記事は 2020 年のパズルアドベントとして書いたものです。
川とは
へやわけにおいて「川」とは、幅 1 のへやが並んでいるような場所のことを指します。
見た目が川っぽいから川とよびます。たぶん。
部屋の個数が r 個のとき、「r 本の川」とよぶことにします。図 1 だと上が 4 本の川で下が 3 本の川です。
川ではへやの三連禁による黒マスの発生が頻繁に起こり、よって分断が生じやすくなります。
この現象を利用して、数字なしで成立する闇のへやわけが生まれてしまいました。
数字がないと手掛かりが全くないように見えますが、最近になってある程度黒マスの挙動が理解されはじめ、少しずつ人間の手に負えるものになってきました。
これから川の基本理論についてまとめます。
アース/接地について
川の説明に入る前に、意識しておきたいへやわけの概念について復習します。それは「アース (接地)」です。
白マスが分断されるとき、黒マスはナナメ伝いにたどって端から端までつながるか、ナナメ伝いにループができることになります。
その事実に関連して、ある黒マスに注目したときに、ナナメ伝いに盤面端まで到達することを「アースされている」といいます。
端から端までつながってはいけないので、一つの黒マスが二か所以上でアースされてはいけません。
なので、すでに一方向にアースされている黒マスについて、他の方向にアースされないように黒マスを配置する必要があります。この議論はへやわけにおいて大事な考え方の一つで、特に川を扱うときに重要になってきます。
川における黒マスの伝播
川があると、黒マスが伝播していきます。このことについて詳しく見ておきましょう。
流れに沿った伝播
まずは、川と平行な向きについて。
図4 の黒マスについて、へやの三連禁により右上か右下に黒マスが置かれます。
事実としては当たり前ですが、これが川となると、下流にどんどん黒マスが伸びていくことになります。
図は伝播の一例です。
もちろん、川から出てしまうと伝播が止まることに注意しましょう。
横切る方向の伝播
次に、川と垂直な向きについて。
図6 の左のように分割線がある状況で、A のマスが黒のとき、2 マス先の B のマスが白になります。なぜなら B が黒マスだと、右図のようにへや三連禁からいきなり分断してしまうためです。
よって、境界線が 3 本になった次の図で、 C が黒だと D も黒になります。また対偶を取ると、D が白だと C も白になります。
すなわち、川があると黒マス・白マスが垂直方向の 3 マス先に伝播していきます。
なお、分割線が欠けるとこの事実は成立しません。ただし、一方が辺なら成立します。
合わせると？
先ほど見た通り、川に水平な方向に黒マスが伝播していきますが、それに沿って 3 マス先にコピーが生まれます。
川をつかったへやわけの問題では、こういった黒マスの伝播によるアースを考えることが肝要です。手掛かりがないため試行錯誤をするにしても、アースのされ方・回避の仕方を意識することで、効率的な探索が可能になります。
また一部のケースでは、探索するまでもなくアースが決まってしまう場合があります。それが次の節の「角の川」です。
角の川定理
川が角にあるときどうなるかを、定理の形で述べておきます。
定理
図11 のように、長さ n で 3 本の川が盤面の角に接しているとき、この幅 4 * n の長方形内の黒マスは、この中だけでアースする。なお、川の長さ n によらず成立する。
証明
川の長さ n に関する帰納法を用います。
長さ 1 なら既に端と接触しているので、n = 1 だと問題ありません。
長さ n = k で成立しているとして、長さ n = k+1 の場合を考えます。
黒マスが下から 1 番目にあるなら既にアースされています。また 2, 3 番目の場合、右上か右下は黒くなります (川に水平な伝播！)。よって帰納法の仮定からこの場合もアースします。
問題は下から 4 番目の場合。このとき右下が白いと一見アースしなさそうですが...
この場合、下に別の黒マスが発生します。
図15で下から2本目に発生した黒マスは、帰納法の仮定により右側でアースします。よって左下のアースとあわせて分断してしまいます。つまりそもそも盤面として不成立になります。
よってもとのマスの右下は黒くなり、これまた帰納法の仮定によって右側でアースします。
よって示されました。
証明の要点は、
- 川により、黒マスが水平伝播する
- 川が角にある影響で、外に出ようと思っても引きずり込まれてしまう
といったところです。
角の川により強制アースを食らうのは強烈で、たとえば他の場所でアースしている黒マスは川に接することができないことになります。
図18 のように 2 か所で接地するのもハタンです。接地した場所から伸びる黒マスが混線する場合がありますが、その場合もループになって分断します。要は内側の白マスが逃げれないわけですね。
川のひとつ上流にて
川が途切れた場所での挙動についても見ておきます。少し勘違いしやすいので注意です。
まず下から 2, 3 行目の黒マスについては、右側に二択で伝播するので、右でアースすることが分かります。
次に 1 行目について。これはそもそもアースしていますが、右に伝播して別のアースが起こるとは限りません。実際、図 21 のように黒マスが回避されます。3 行目にできた黒マスとつながっていないことに注目してください。
最後に 4 行目について。この場合も川が続いていないため、上の証明のように黒マスが引きずり込まれることはありません。図22 のような分断回避が起きます。
実質的な辺
上の議論をまとめると、図23 において緑の場所に黒マスが来るとアースすることが分かりました。
これはアースの観点で、「実質的な辺」が生まれたとみなせます。
何か議論が進むわけではないですが、問題を解くときにイメージしておくと分かりやすいかもしれません。
続く
本数の多い川や縦横の接続、また自作問題の解説も書く予定でしたが、長くなってきたので今回はここまで。気が向いたらまた更新します。
最後にいくつか話題を。
川の代表的な問題といえば、さやちぃさんの作ったハバネロ問題でしょう。
すでに作者本人が解説を書かれていますが、この問題では今回紹介した角の川の議論が使えます。直接の適用ではなく少し応用は必要ですが、理詰めで解き切ることができるので、ぜひ考えてみてください。
あとは角の川定理の意義について。
記事にしますけど、角の川定理(アースすること)は帰納的に示せるんですよね。これは試行錯誤の手間を完全に消せる意味合いがあって、意義としてとても大きい。
— SP1 (@SP1_winter) 2020年11月23日
証明は帰納法によって行いましたが、ひとつひとつの状態遷移は黒マスの形のパターンにに対応していて、これを全部バラすととんでもない量になります。つまり大量のパターンがこの定理に隠されているのですね。
今回の証明により、もうこれらのパターンを試行錯誤をする必要はありません。安心して手筋利用してくださいね。
