初心者向け 分割充填法の話
・分割充填法とは
単体で処理するのが厳しい大部屋などを、処理しやすい小部屋に分けて考える、という技です。
例えば、3の辺が壁に接している3×6の部屋に8個の黒マスを入れるときを考えてみます。
この8の部屋を下図のように2つに区切ってみましょう。
すると、上の2×3の部屋には黒マスが最大で3個まで、下の3×4の部屋には黒マスが最大で5個まで入ることがわかります。
ということは、黒マスを8個入れるには、どちらの部屋にも最大の個数だけ黒マスを入れる必要があります。
よって、先ほどの大部屋を解くことは下図の部屋を解くことに等しくなります。
ここまで行けたら簡単ですね、上の部屋は開幕テンプレですぐ埋まり、すると下の部屋も5in3*3の即興部屋になるのでわかります。
さて、ここまで読んでみた方は、「なぜそこで区切ったんだ？」という疑問が湧くと思います。
では、他の区切り方でも試してみましょう。
真ん中で区切ってみました。こうすると黒マスは、上の部屋にはMAX4個、下の部屋にはMAX5個入ります。すると4+5>8となるので、上下どちらかの部屋には黒マスがMAXまではいり、もう片方はMAX-1までしか入らないことがわかります。
なので場合わけが必要です。
1:上の部屋に4個、下の部屋に4個のとき
下図のようになるので詰みですね。じゃあ次
2:上の部屋に3個、下の部屋に5個のとき
上図のようになるのでいけます。ということでこれが答えです。
というように、区切り方によっては場合わけが発生してめんどくさいことになります。なので、分割する場所は、うまく選ぶようにしましょう。
といっても、よくわからないと思うので、コツを言うと、空中3*3(空中とは壁に接してない部屋のことを言います)の部屋に分けるより、空中3*4の部屋に分けたほうがいい、とかがあります。なぜならどっちも黒マス配置可能数が5個だからです。同じ個数だけ入るなら、出来るだけ部屋を大きくしたほうが、黒マスの最大値が小さくなって、場合わけが減らせるのでよいです。
そもそも黒マス配置可能数が分からないって人もいると思うので、よく使う例だけ
•角 2*3>>2個
•4の辺が壁に接している2*4>>3
•角、空中 3*4>>5個
•角 4*4>>6個
•5の辺が壁に接している3*5>>6個
・さらに大きい部屋の対処方法
上の例では4in3*3とか、5in3*3とか、見慣れた形が多かったので処理しやすかったですが、これが、さらに処理しにくい形だったらどうなるでしょうか。
これは、このように分割してみましょう。
すると、次のように埋まります。
しかし、5の部屋が単体で処理しにくい形をしています。そういうときは、さらに分割すればいいです。
はい、ここまで行ったらわかると思います。という風に一度区切ってもわからない場合はさらにどんどん区切って行ったらいいです。
他にもコツとして、別の区切り方と伏せて考えるというのもあります。上の9の部屋だと、左右4.5の部屋を入れ替えても良いので次のように決まります。
分割充填法は色々応用方法があって面白いです。
(注意:こっちが勝手に区切っているだけなので、その区切られた境界線による部屋内での3連禁は関係ありません)
さらにこの分割充填法を用いることで、大部屋の中に即興部屋を使った分断菌を使うことができます。
こういう状況を考えてみます。ここで、6の部屋の真ん中に縦の線を引いて、2×4の部屋と2×3の部屋に分けてみます。
すると、左の部屋にはMAX4、右の部屋にはMAX2入るので、下図のようになります。
よって、分断禁より即興部屋の4が確定して、2も確定します。(下図)
疲れたからおしまい
以下分割充填法の練習問題集(難易度順じゃないです)
あと補足すると、なんとなくで選んだので、分割充填じゃなくて、限界線の攻防(っていう手筋がある)をメインに使った問題を含んでるかもしれないです。