こんにちは、ゲッソーというものです！
NFの1日目も木曜日にせまってきて、いよいよ忙しくなってきました。いろいろ用意しているのでみなさんぜひきてください！
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
みなさんは数字なしへやわけという闇パズルを知っていますか？
普段ニコリでへやわけを解いている方は見たことがないかも知れませんが表出数字が一つもないへやわけのことを指します。
例えば、こんな問題
puzzlinkはこちら
？？？？？？？？？
はじめて数字なしへやわけを見た人は上の問題をまともに解こうとしたら30分以上かかるとおもいます。それぐらい闇の深いパズルです。
昔はこのような数字なしへやわけについては全探索するしかないという感じだったのですが、最近になって川とよばれる角に細い部屋が連続した部分がある場合に役立つ定理が編み出されてきました!
このあたりの定理の解説はSP1さんという方が既に書いておられるのですが、それをさらに具体的に証明も加えて解説していきたいと思います！
SP1さんの記事はこちら
川とは
下図のような配置の部屋のことを言います。今回の記事では角に接している3列のものを川と言います
定理1:
川の角に対してこのような覆いかぶさる配置(2 in 2*2のような配置など)が来ると必ず分断禁が発生する
証明1:
川の黒マス配置を考えると以下の3通りしかないことがわかり、分断禁を回避しようとすると、図2の薄灰色マスの配置(黒マスの繋がりを分ける配置)が必要になる。すると、覆いかぶさる配置(2 in 2*2)がまた現れてしまう。その新しい黒マス分断を回避しようとすると、また新しい覆いかぶさる配置があらわれて、結局黒マス分断は回避できないので、この配置を置いた時点で破綻する。
定理2:
図の赤マスと青マスは川(左上)を通じて繋がることができない
証明2:
まず直接繋ごうとすると、定理1の禁止系が出てきて破綻する。
よって黒マスの左上は黒マスになる。そして、この先ほど埋めた黒マスが必ず壁に接することを示す。
この黒マスの繋がりを回避するには証明1のような灰色の配置が必要であるが、その配置では、定理1の禁止系がでてきて破綻する。よって、この黒マスは必ず壁と接するので、赤と青のマスは川を通じて接することはない。
定理3:
下の配置は破綻している
証明3:
このように4列目に黒マスを置くと、黄色マスと緑マスが必ず分断するので詰み
よって4列目は全て白マスになるが、すると、2,3列目に黒マスがギザギザに現れて、必ず分断される。よって詰み
定理4:
下の川を囲む長方形に付いて考えた時、長方形に接する黒マスは川の外部(川から1マス以上離れたところ)から壁に接してはいけない。たとえば左下の図は詰み
つまり赤線部に接する黒マスは川の外部で壁に接してはいけない
証明4:川の右側に黒マスが接する場合は、定理3からわかる(下図)
川の下に接する場合は1、2、3列目の黒マスで接する場合があるが、
1列目は明らか(左上図)
2列目は右上図のようになるが、定理2より4列目には黒マスが置けないので、証明1で使用した灰色マスの配置が使えず必ず分断して破綻する。-★
3列目は2列目に黒マスを置く(左下図)と、★とおなじように破綻することがわかる。なので黒マスを4列目におく(右下図)必要があるが、定理2より破綻する。
よって下図の赤線部に接する黒マスは川の外部で壁に接してはいけない。
定理5:
左図のように、川に接する黒マス同士がつながってはいけない。さらにここでいう川は同じ黒マスじゃなくてもかまわない、つまり、右図も破綻する。
証明5:
定理2より明らか(定理4が川内部では必ず分断するということを表していると考えるとわかりやすいと思います)
ということで川へやわけの定理の解説でした。いままで川へやわけがあまりわからなかったという人も定理2を経由してだいぶわかりやすくなったと思います。
この記事をみたあとだと一番最初にはったヤバい問題も仮定なしで解くことができます！
最初の問題の解説
左が定理で決まるマス、右がその後普通に埋めてわかるマスです
定理5より下図まで決まる。これを進めて右図になる
つぎに定理1の禁止形、定理4の分断に注意すると次のようにきまる
また定理5の川同士の接続に注意して
あとは定理1の禁止形に気をつけてうめていくと
解けました。やばいなあ
ということで川へやわけの解説でした。もしこのような問題をニコリ編集部に送ってしまうと、ブラックリストみたいなものにのる可能性があるのでに送ったりはしないようにしてください。(まあさすがにないやろうけど)
一番下までみてね
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
宣伝！
3/26-3/28のNFに京都大学パズル同好会は企画として、部員が作った大量のパズルをこのブログに3日間連続であげたり、Zoom上で新歓などをします！興味のある方はぜひきてください！
