【へやわけ】川の渡り方その1・基本理論編

みんなで渡ろう

 

はじめに

本記事は 2020 年のパズルアドベントとして書いたものです。

adventar.org

 

川とは

へやわけにおいて「川」とは、幅 1 のへやが並んでいるような場所のことを指します。

f:id:SP1_puzzle:20201125002641p:plain

図1 川です

見た目が川っぽいから川とよびます。たぶん。

部屋の個数が r 個のとき、「r 本の川」とよぶことにします。図 1 だと上が 4 本の川で下が 3 本の川です。

川ではへやの三連禁による黒マスの発生が頻繁に起こり、よって分断が生じやすくなります。

この現象を利用して、数字なしで成立する闇のへやわけが生まれてしましました。

数字がないと手掛かりが全くないように見えますが、最近になってある程度黒マスの挙動が理解されはじめ、少しずつ人間の手に負えるものになってきました。

これから川の基本理論についてまとめます。

 

アース/接地について

 

川の説明に入る前に、意識しておきたいへやわけの概念について復習します。それは「アース (接地)」です。

 

白マスが分断されるとき、黒マスはナナメ伝いにたどって端から端までつながるか、ナナメ伝いにループができることになります。

f:id:SP1_puzzle:20201125002932p:plain

図2 分断の例

その事実に関連して、ある黒マスに注目したときに、ナナメ伝いに盤面端まで到達することを「アースされている」といいます。

端から端までつながってはいけないので、一つの黒マスが二か所以上でアースされてはいけません。

f:id:SP1_puzzle:20201125003001p:plain

図3 灰色のマスについて、上下にアースされていると見れる

なので、すでに一方向にアースされている黒マスについて、他の方向にアースされないように黒マスを配置する必要があります。この議論はへやわけにおいて大事な考え方の一つで、特に川を扱うときに重要になってきます。

 

川における黒マスの伝播

川があると、黒マスが伝播していきます。このことについて詳しく見ておきましょう。

流れに沿った伝播

まずは、川と平行な向きについて。

f:id:SP1_puzzle:20201125003443p:plain

図4 水平伝播の基本

図4 の黒マスについて、へやの三連禁により右上か右下に黒マスが置かれます。

事実としては当たり前ですが、これが川となると、下流にどんどん黒マスが伸びていくことになります。

f:id:SP1_puzzle:20201125003703p:plain

図5 水平な伝播の様子

図は伝播の一例です。

もちろん、川から出てしまうと伝播が止まることに注意しましょう。

 

横切る方向の伝播

次に、川と垂直な向きについて。

f:id:SP1_puzzle:20201125004114p:plain

図6 垂直伝播の基本・その1

図6 の左のように分割線がある状況で、A のマスが黒のとき、2 マス先の B のマスが白になります。なぜなら B が黒マスだと、右図のようにへや三連禁からいきなり分断してしまうためです。

よって、境界線が 3 本になった次の図で、 C が黒だと D も黒になります。また対偶を取ると、D が白だと C も白になります。

f:id:SP1_puzzle:20201125010250p:plain

図7 垂直伝播の基本・その2 分割線の正確な条件に注意

すなわち、川があると黒マス・白マスが垂直方向の 3 マス先に伝播していきます。

f:id:SP1_puzzle:20201125012027p:plain

図8 垂直伝播の基本・その3 一番よく使う形

 

 なお、分割線が欠けるとこの事実は成立しません。ただし、一方が辺なら成立します。

f:id:SP1_puzzle:20201125012521p:plain

図9 垂直伝播の基本・その4 辺ver.

 

合わせると?

先ほど見た通り、川に水平な方向に黒マスが伝播していきますが、それに沿って 3 マス先にコピーが生まれます。

f:id:SP1_puzzle:20201125180115p:plain

図10 コピーが出現する


川をつかったへやわけの問題では、こういった黒マスの伝播によるアースを考えることが肝要です。手掛かりがないため試行錯誤をするにしても、アースのされ方・回避の仕方を意識することで、効率的な探索が可能になります。

また一部のケースでは、探索するまでもなくアースが決まってしまう場合があります。それが次の節の「角の川」です。

 

角の川定理

川が角にあるときどうなるかを、定理の形で述べておきます。

定理

図11 のように、長さ n で 3 本の川が盤面の角に接しているとき、この幅 4 * n の長方形内の黒マスは、この中だけでアースする。なお、川の長さ n によらず成立する。

f:id:SP1_puzzle:20201125180435p:plain

図11 角の3本川

証明

川の長さ n に関する帰納法を用います。

長さ 1 なら既に端と接触しているので、n = 1 だと問題ありません。

長さ n = k で成立しているとして、長さ n = k+1 の場合を考えます。

黒マスが下から 1 番目にあるなら既にアースされています。また 2, 3 番目の場合、右上か右下は黒くなります (川に水平な伝播!)。よって帰納法の仮定からこの場合もアースします。

f:id:SP1_puzzle:20201125180554p:plain

図12 2本目からの水平伝播

f:id:SP1_puzzle:20201125180635p:plain

図13 3本目からの水平伝播

問題は下から 4 番目の場合。このとき右下が白いと一見アースしなさそうですが...

f:id:SP1_puzzle:20201125180826p:plain

図14 4本目から伝播しないと?

この場合、下に別の黒マスが発生します。

f:id:SP1_puzzle:20201125180913p:plain

図15 詰み!

図15で下から2本目に発生した黒マスは、帰納法の仮定により右側でアースします。よって左下のアースとあわせて分断してしまいます。つまりそもそも盤面として不成立になります。

よってもとのマスの右下は黒くなり、これまた帰納法の仮定によって右側でアースします。

f:id:SP1_puzzle:20201125181215p:plain

図16 下から4行目にあっても、結局川に引きずり込まれる

よって示されました。

 

証明の要点は、

  • 川により、黒マスが水平伝播する
  • 川が角にある影響で、外に出ようと思っても引きずり込まれてしまう

といったところです。

 

角の川により強制アースを食らうのは強烈で、たとえば他の場所でアースしている黒マスは川に接することができないことになります。

f:id:SP1_puzzle:20201213141603p:plain

図17 これはハタン!

図18 のように 2 か所で接地するのもハタンです。接地した場所から伸びる黒マスが混線する場合がありますが、その場合もループになって分断します。要は内側の白マスが逃げれないわけですね。

f:id:SP1_puzzle:20201213141931p:plain

図18 これもハタン!

 

川のひとつ上流にて

川が途切れた場所での挙動についても見ておきます。少し勘違いしやすいので注意です。

f:id:SP1_puzzle:20201213142239p:plain

図19 ここについて

まず下から 2, 3 行目の黒マスについては、右側に二択で伝播するので、右でアースすることが分かります。

f:id:SP1_puzzle:20201213142453p:plain

図20 3 行目の黒の様子。2 行目も同じ。

次に 1 行目について。これはそもそもアースしていますが、右に伝播して別のアースが起こるとは限りません。実際、図 21 のように黒マスが回避されます。3 行目にできた黒マスとつながっていないことに注目してください。

f:id:SP1_puzzle:20201213143054p:plain

図21 1 行目の分断回避の様子。手筋ともいえる。

最後に 4 行目について。この場合も川が続いていないため、上の証明のように黒マスが引きずり込まれることはありません。図22 のような分断回避が起きます。

f:id:SP1_puzzle:20201213143543p:plain

図22 4 行目の分断回避の様子。

 

 

実質的な辺

上の議論をまとめると、図23 において緑の場所に黒マスが来るとアースすることが分かりました。

これはアースの観点で、「実質的な辺」が生まれたとみなせます。

f:id:SP1_puzzle:20201213144408p:plain

図23 実質的な辺のイメージ

何か議論が進むわけではないですが、問題を解くときにイメージしておくと分かりやすいかもしれません。

 

続く

本数の多い川や縦横の接続、また自作問題の解説も書く予定でしたが、長くなってきたので今回はここまで。気が向いたらまた更新します。

 

 

最後にいくつか話題を。

川の代表的な問題といえば、さやちぃさんの作ったハバネロ問題でしょう。

note.com

すでに作者本人が解説を書かれていますが、この問題では今回紹介した角の川の議論が使えます。直接の適用ではなく少し応用は必要ですが、理詰めで解き切ることができるので、ぜひ考えてみてください。

 

あとは角の川定理の意義について。

 

証明は帰納法によって行いましたが、ひとつひとつの状態遷移は黒マスの形のパターンにに対応していて、これを全部バラすととんでもない量になります。つまり大量のパターンがこの定理に隠されているのですね。

今回の証明により、もうこれらのパターンを試行錯誤をする必要はありません。安心して手筋利用してくださいね。