へやをわけたい

この記事は[ペンパアドベント2018](https://adventar.org/calendars/3414)の23日目の記事です。

パズル党東京支部の ゆずっこ と言います。
駒場祭や五月祭で冊子をもらいに来ている方はお久しぶりです。そうでない方は初めまして。
今日は好きなパズルの1つである へやわけ について語ろうと思います。

「へやわけを、解きた～い！」
皆さん、心の奥底でこうは思っていませんか？
この記事はそんなあなたにぴったり！
「あまり解いたことがない」「正直取っつきづらい」と思っている方もこの記事でレベルアップを目指しましょう！

#この記事の対象
以下の事柄にひとつでも当てはまった方は是非読み進めてみてください。
・「へやわけを解きたい」という根源的な欲求を持っている
・へやわけの「らくらく」を解いたことがある
・へやわけの「たいへん」「アゼン」を解こうとしたことがある

#導入
それではまず肩慣らしに一問解いてみましょう。難易度は「らくらく」想定です。
#####問1.
![toi1.png](https://qiita-image-store.s3.amazonaws.com/0/321533/dcb607f2-1ead-15f1-280f-979c7d0eabfe.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/ail52a4k94g90i2i5400vu0000vv0f00vv002g12g13543g21132)

解けましたか？
今度はこちらを解いてみましょう。へやも数字も大きく、難しそうに見えますね。難易度は「たいへん」～「アゼン」想定です。
#####問2.
![toi2.png](https://qiita-image-store.s3.amazonaws.com/0/321533/f5e04768-746b-09c2-d43e-1894cb0e284d.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/ail4a8kh90g1020g1000u00000vv0f00vv002g27g37g225)

一部の方は解いているうちに気付いたと思いますが、この2問、解法や解答が全く同じなのです！
ある考え方を使うと問2が問1に早変わりするのです！

#本論
あるへやに入る黒マスの最大値は部屋の縦と横の大きさで決まる (計算が出来る) という定理があります。
<details><summary>計算方法はこちら</summary>
・1 × n の場合
   n = 奇数のとき (n+1) / 2
   n = 偶数のとき n / 2
・3 × n の場合
   3 × (4k-1) のとき 5k
   3 × (4k)   のとき 5k
   3 × (4k+1) のとき 5k+2
   3 × (4k+2) のとき 5k+3
・その他 (n × m) の場合
(2^k-1) × (2^k-1) のとき (nm+n+m) / 3
その他の 奇数 × 奇数 のとき (nm+n+m) / 3 未満の最大の整数
偶数 × 偶数、偶数 × 奇数のとき (nm+n+m-2) / 3 を超えない最大の整数
.
([超へやわけMX](http://www.geocities.co.jp/HeartLand-Poplar/2112/heyawake_mx/)からの引用です)
</details>
(詳しい証明などは[超へやわけMX](http://www.geocities.co.jp/HeartLand-Poplar/2112/heyawake_mx/) を見てみてください) ([リンク切れの場合はこちら](https://web.archive.org/web/20181106095427/http://www.geocities.co.jp/HeartLand-Poplar/2112/heyawake_mx/))

この定理を少し拡張してみましょう。
[へやわけのルール](https://www.nikoli.co.jp/ja/puzzles/heyawake/)から、へやの境目の役割は領域の区分とルール3(これ以降3連禁と言います)のためだけに存在すると言えます。
3連禁が起きないような状況であるなら、領域に黒マスの数を対応づける役割だけとなります。
つまり、**3連禁のない任意の領域に対し、入る黒マスの最大個数はへやの場合と同様に議論できる**、と拡張できるのです。

一番単純な例は[即興部屋](https://web.archive.org/web/20071206122237/http://www.kamome.or.jp/nyanbaz/heyaroom/heyadas/h-sa.html#sokkyoubeya)と呼ばれる手筋です。
簡単に言うとへやをいくつか結合して、手筋として解きやすい3×2の3だったり2×2の2というような[n in 2×n](https://web.archive.org/web/20071206122237/http://www.kamome.or.jp/nyanbaz/heyaroom/heyadas/h-x.html#nin2*n)の形として見ることです。へやを結合するときに数字も足すことを忘れないようにしましょう。
いくつか例題を解いてみましょう。
#####問3.
![toi3.png](https://qiita-image-store.s3.amazonaws.com/0/321533/5007aea0-3164-6576-f21f-20cfe989f144.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/90agl152a4l5aakl9avv00vv0000vv001se011121g124g31422h1g)
#####問4.
![toi4.png](https://qiita-image-store.s3.amazonaws.com/0/321533/b2df4797-9b30-70d8-73a8-2df5ae3ebdd3.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/dgr5mbcip5ib4kh92i0f3040su00v00vs0s0k5g31g113242h)
#####問5.
![toi5.png](https://qiita-image-store.s3.amazonaws.com/0/321533/82339e63-e6b6-eeff-e9d7-8dfe8e1d0c0e.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/qll9ail5aqllbbin50g0o07g00pj001vo81v1g3g14h1l1g22g1)

即興部屋の感覚はつかめたでしょうか？

もう一つの例は[分割充填法](https://web.archive.org/web/20071206122237/http://www.kamome.or.jp/nyanbaz/heyaroom/heyadas/h-ha.html#bunkatsujutenhou)と呼ばれる手筋です。簡単に言うと大きなへやをいくつかに区切って数字も配分する、という考え方です。そこまで難しくありません。へやの一部が埋まったときにこのような考え方をしているはずです。区切るときには手筋として解きやすい形に区切ることがコツです。
またいくつか例題を解いてみましょう。
#####問6.
![toi6.png](https://qiita-image-store.s3.amazonaws.com/0/321533/461022a1-0a02-8f36-01e5-eb7b55661dcf.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/g152a4k98ih9ij76ecfv0000000ffv00c000h727h5g5h)
#####問7.
![toi7.png](https://qiita-image-store.s3.amazonaws.com/0/321533/9b6e72e5-c36f-5c8d-4edc-07f4f3f7e37b.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/qjl5ad4q9kj96id4g900o0vg00000e0000vgh2282g31721)
#####問8.
![toi8.png](https://qiita-image-store.s3.amazonaws.com/0/321533/eba4e73b-87fd-542a-305a-c4570c14c12c.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/0m584080g1002gd0q1vjvv000000vvvv0000h1h1g88g227g)
分割充填法の感覚はつかめたでしょうか？
先の即興部屋とこれを用いることで問2が問1に早変わりするのです。ぜひやってみてください。

#応用
今度は即興部屋を拡張して、分割充填法も混ぜて、「どのように結合、分割してもよいが、考えやすい形にする」という手筋にしてみましょう。別にn in 2×nでなくても考えやすい形はいくらでもありますからね。
例題をいくつか出しますので、へやをつなげたり文字通りへやをわけたりする感覚を身につけてみてください。
#####問9.
![toi9.png](https://qiita-image-store.s3.amazonaws.com/0/321533/b42b1663-1d8b-6b12-a06a-d90bb6bf1b0f.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/82g52a4k99ii54a8g0o07u00007g0u0000vvg31555515g)
#####問10.
![toi10.png](https://qiita-image-store.s3.amazonaws.com/0/321533/0c1c06fb-5e14-2299-7608-85f1d39ab174.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/h12244182g30i14a8k00g0fv00fvfv00fo00g3625g4g542g)
#####問11.
![toi11.png](https://qiita-image-store.s3.amazonaws.com/0/321533/a99b23f5-de8f-2feb-31e3-e11e3982a980.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/01jf6ecsppnjb6mdcgvv0e0000ve0300700v42g541l3h2g)

どうでしょう、身につきましたか？
これから問題を解く上でこの考え方を意識してみてください。「アゼン」が「おてがる」くらいにはなるかもしれませんよ。

#余談
[アドベントカレンダーの19日目](https://note.mu/tigereye_puzzle/n/n1dacd7a15348)にも、領域を統合して充填をする話をタイガーアイさんが書いてますね。黒マスを詰め込みたいというのはやはり根源的な欲求なのでしょうか。

冗談はさておき、へやわけのルールで一番"へやわけらしい"ものといえば3連禁ですよね。3連禁は黒マスを生み出す魔法のルールです。
黒マスを生み出す、ということはすなわち数字がないところに数字が生まれる、ということです。問5で使いましたね。
3連禁を駆使すると例えばこのようなことが出来てしまうのです。
#####問12.
![toi12.png](https://qiita-image-store.s3.amazonaws.com/0/321533/9db8ea46-0a36-b20d-6c2e-537ea6f29dff.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/07ljb6mec4o9jj1624vv8787ngs000vvs73og1g10212g0k2h0g2g2110)

#####問13.
![toi13.png](https://qiita-image-store.s3.amazonaws.com/0/321533/8c29cc5f-3831-998b-8b43-5b92d6cacbcf.png)
[ぱずぷれのリンクはこちら](http://pzv.jp/p.html?heyawake/10/10/2olhb2u5sbomhd2q50u0001g0000uoo7001v2g184211g322g3)

**仮定せずに**これらが解けたあなたはもう立派にへやを切って貼る考え方が身についたことでしょう。これからのへやわけライフ、存分に楽しんでください。

最後までお読みいただき、ありがとうございました。
[ペンパアドベント2018](https://adventar.org/calendars/3414)、23日目、[ゆずっこ](https://twitter.com/pawakun)がお送りしました。


追記：解き方が分からない場合はDMなどで聞いてください。できる限り対応します。