Help us understand the problem. What is going on with this article?

へやをわけたい

More than 1 year has passed since last update.

この記事はペンパアドベント2018の23日目の記事です。

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

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

この記事の対象

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

導入

それではまず肩慣らしに一問解いてみましょう。難易度は「らくらく」想定です。

問1.

toi1.png
ぱずぷれのリンクはこちら

解けましたか?
今度はこちらを解いてみましょう。へやも数字も大きく、難しそうに見えますね。難易度は「たいへん」~「アゼン」想定です。

問2.

toi2.png
ぱずぷれのリンクはこちら

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

本論

あるへやに入る黒マスの最大値は部屋の縦と横の大きさで決まる (計算が出来る) という定理があります。

計算方法はこちら
・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からの引用です)

(詳しい証明などは超へやわけMX を見てみてください) (リンク切れの場合はこちら)

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

一番単純な例は即興部屋と呼ばれる手筋です。
簡単に言うとへやをいくつか結合して、手筋として解きやすい3×2の3だったり2×2の2というようなn in 2×nの形として見ることです。へやを結合するときに数字も足すことを忘れないようにしましょう。
いくつか例題を解いてみましょう。

問3.

toi3.png
ぱずぷれのリンクはこちら

問4.

toi4.png
ぱずぷれのリンクはこちら

問5.

toi5.png
ぱずぷれのリンクはこちら

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

もう一つの例は分割充填法と呼ばれる手筋です。簡単に言うと大きなへやをいくつかに区切って数字も配分する、という考え方です。そこまで難しくありません。へやの一部が埋まったときにこのような考え方をしているはずです。区切るときには手筋として解きやすい形に区切ることがコツです。
またいくつか例題を解いてみましょう。

問6.

toi6.png
ぱずぷれのリンクはこちら

問7.

toi7.png
ぱずぷれのリンクはこちら

問8.

toi8.png
ぱずぷれのリンクはこちら
分割充填法の感覚はつかめたでしょうか?
先の即興部屋とこれを用いることで問2が問1に早変わりするのです。ぜひやってみてください。

応用

今度は即興部屋を拡張して、分割充填法も混ぜて、「どのように結合、分割してもよいが、考えやすい形にする」という手筋にしてみましょう。別にn in 2×nでなくても考えやすい形はいくらでもありますからね。
例題をいくつか出しますので、へやをつなげたり文字通りへやをわけたりする感覚を身につけてみてください。

問9.

toi9.png
ぱずぷれのリンクはこちら

問10.

toi10.png
ぱずぷれのリンクはこちら

問11.

toi11.png
ぱずぷれのリンクはこちら

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

余談

アドベントカレンダーの19日目にも、領域を統合して充填をする話をタイガーアイさんが書いてますね。黒マスを詰め込みたいというのはやはり根源的な欲求なのでしょうか。

冗談はさておき、へやわけのルールで一番"へやわけらしい"ものといえば3連禁ですよね。3連禁は黒マスを生み出す魔法のルールです。
黒マスを生み出す、ということはすなわち数字がないところに数字が生まれる、ということです。問5で使いましたね。
3連禁を駆使すると例えばこのようなことが出来てしまうのです。

問12.

toi12.png
ぱずぷれのリンクはこちら

問13.

toi13.png
ぱずぷれのリンクはこちら

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

最後までお読みいただき、ありがとうございました。
ペンパアドベント2018、23日目、ゆずっこがお送りしました。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away