前回に続き、今回もパズル『クロスウォール』についての記事になります。
ルールについては、こちらの投稿をご覧下さい。
『クロスウォール』というパズルを考案しました！
— Solyu🐬 EK科甲優勝おめでとう!! (@MrSolyu) 2023年1月19日
(おそらく初出だと思います)
リプ欄に問題のリンクを載せるので、宜しければ解いてみて下さい(正誤判定も出ます！) pic.twitter.com/Td9GD4eWQz
今回は主な解き筋を紹介する他、練習問題を９問用意しました。
(一部の問題に、原因不明のバグで説明欄に宛先無しのソースが出来ていますが、無視して下さい)
それでは、早速クロスウォールの解き筋を紹介していきましょう。
１ 初級編
まずはここから覚えると良いと思います。
・それぞれの点を通る線は偶数(0,2,4)本。
『全体で１つの輪っか』というルールから分かります。地味ながら重宝する性質で、この性質を使うことで線が引かれるかどうかが分かることが多く有ります。
・面積が1のマスは、外周を除く周囲に線が通る。
面積１はかなり注目度の高い情報です。
・外周に接しているマスの内側度が０なら、そのマスと外周の接する所には線が引かれない。反対に内側度が１なら、線が引かれる。
端は線の引き方が限られるので、何処に線が引かれるかがより重要になります。
なお、端のマスの内側度は0か1になります(そのマスから1マス分移動すれば外周に到達するので、2本以上輪っかの線を横切らない=内側度が2以上にならない)。
・内側度が０の領域は、外周と接する。また、その領域が外周と接する所には線が引かれない。
内容はただの内側度の言い換えですが、何気に重要な性質です。
・全ての線は、一繋がりになっている。
線が一繋がりになっていないと、一つの輪っかになりません。
初級編 練習問題
Q1：線を引かない所に印を付けると……
（線の中間を右クリックで、線の代わりに✕印を付けることができます）
推定難易度：★☆☆☆☆
Q2：内側度０の領域を良く見ると……？
推定難易度：★★☆☆☆
２ 中級編
ここから先は、初見では気付きにくい手筋です。
・内側度がNのマスから内側度がMのマスまで縦横にマスを辿るとき、[N-Mの絶対値]回以上線を横切る。
特に、外周を内側度０のマスと見れば、内側度がNのマスから外周まで縦横にマスを辿るとき、N回以上線を横切る。
例えば、内側度が３の領域Aと内側度が１の領域Bとが辺を共有していたとします。すると、A→B→外周と通ることで、Aから２回で外周に到達できてしまいます。これはおかしいので、AとBとは辺を共有しません。
外周からこのマスに行くまでに２回以上線を横切るので、左の線が確定します(右図)。
右側の線も同様に確定します。
ここまでに２回以上線を横切るので、中央左の線２本が確定します(左図)。
右側の内側度２のマスから左→下(or 下→左)と行くと、内側度０のマスに着きます。
どちらのルートでも２回以上線を横切るので、交差している線４本が確定します(左図)。
最終的に確定する線が、右図となります(✕は内側度０が外周と接するため)。
・輪っかの線が長方形を成すとき、(ほぼ確実に)長方形の頂点のうち少なくとも１つは交差点(=線が４本通る点)になっている。
小ループ禁の例です。長方形の全ての角で９０度曲がると、もとの頂点に戻ってきてしまいます。この為、他に輪っかの線があると、その線を通らないのでルールに反してしまいます(『ほぼ確実に』と言ったのは、他に輪っかの線がない激レアケースが一応あるからです。とはいえ、そのような正解盤面となる問題はほぼ出題されないでしょう)。
・特に、角のマスが面積１内側度１であるとき、そのマスの頂点であって外周上に無い点では(ほぼ確実に)交差点を作る。
角の面積１内側度１は交差点を作れる格子点が１か所しかないので、自ずと交差点になります(『ほぼ確実に』と言ったのは、その１だけを囲む輪っかが正解である問題が一応作れるからです。とはいえ、余りにも面白味に欠けるのでまず出題されないでしょう)。
・数字の入っているマス２つが隣り合っているとき、その２つのマスで面積と内側度の少なくとも片方が違うなら、２つのマスは異なる領域になる(マスの間に線が通る)。
同じ領域では、面積も内側度も同じであるという性質を用いています。
実はより強い事実が言えるのですが、それは上級編で説明します。
・内側度が１以上のマスは８方向で一繋がりになる。
内側度が１以上のマスが８方向で分断されていると、輪っかが分裂してしまいます。
中級編 練習問題
Q3：内側度が大きいマスに注目すると……
推定難易度：★★☆☆☆
Q4：内側度１以上のマスを一繋がりにしよう
推定難易度：★★★☆☆
３ 上級編…２色塗分け定理とその活用
ここから先は、知っておくとかなり便利な手筋です。この手筋が成り立つことの説明には少し数学的な背景が必要なのですが、それは今回の記事では割愛します。
・外周を含めた全ての領域は２色で塗り分けできる(同じ色で塗った領域同士が辺を共有しないように、２色で塗り分けられる)。このとき、外周または内側度が偶数の領域が片方の色に、内側度が奇数の領域がもう一方の色に塗られる。
ここで必要なのは次の定理です。証明は割愛します。
定理：連結な平面グラフが2-面彩色可能である必要十分条件は、そのグラフの任意の頂点から、ちょうど偶数本の辺が出ていることである。
そして、クロスウォールの線は一繋がりの輪っかになっていることから、全ての領域が２色で塗り分けられることが分かります。
一方、内側度とは『外周に到達するまでに最低で何本の輪っかの線を横切るか』で、これは『[外周に到達するまでに通った領域の数]＋１』と言い換えられます(輪っかの線を通るごとに異なる領域に行くことから分かります。＋１は植木算の＋１です)。ここで、隣り合う領域は異なる色に塗られているので、外周に到達するまでの道順を辿ると、色が交互に変わっていくこととなります。これが領域の色と内側度の偶奇性とに対応し、始めに述べた性質が言えます。
さて、このことから分かる性質を一気に紹介しましょう。
・隣り合う２つの領域に対し、内側度の差はちょうど１である。
中級編で初めに述べた性質から、内側度の差は１以下です。ここで、この二つは異なる色分けをされているので、内側度の偶奇は違います。よって、内側度の差は０ではなく１であると分かります。
・隣り合う２つのマスの内側度が同じなら、同じ領域である(つまり、この２つのマスの間には線が通らない)。
上の性質を言い換える(ほぼ対偶)と導けます。何気に凄く強力な性質です。
・内側度がMのマスから内側度がNのマスまで縦横にマスを辿るとき、線を横切る回数は[M-N]と偶奇が一致する。
特に、内側度がNのマスから外周まで縦横にマスを辿るとき、線を横切る回数とNとの偶奇は一致する。
『外周に到達するまでに最低で何本の輪っかの線を横切るか』＝『[外周に到達するまでに通った領域の数]＋１』という性質から導かれます。
・異なる領域の内側度が同じとき、その２つは縦横に隣り合わない(つまり、辺を共有しない)。
先程の性質を適用すれば、この２つの領域は辺を共有しないことが分かります。
さて、以上の性質を纏めましょう。
・隣り合う２つのマスの内側度の差は０か１であり、０なら同じ領域、１なら異なる領域となる。
・隣り合う２つのマスの面積が異なるなら、内側度は１だけ異なる。
・内側度がMのマスから内側度がNのマスまで縦横にマスを辿るとき、線を横切る回数は[M-Nの絶対値]以上であり、更に[M-N]と偶奇が一致する。
外周は、内側度０のマスとして見ることで同様のことが言える。
これが分かれば、きっとあなたもクロスウォール上級者です。
上級編 練習問題
Q5：２色塗分けで考えると……
（マスの中央をタップで、無色→黄色→緑色→無色の順に色付けできます）
推定難易度：★★★☆☆
Q6：内側度の離れたマスが近くにあるときは……
推定難易度：★★★★☆
４ おまけ編
その他、クロスウォールで使われる手筋です。
・曲がり角の交差が確定する構図１：異なる領域の出会い頭衝突
初級編で載せてもいい手筋ですが、順番的にここに載せました。
例えば、下の図で赤と青が異なる領域だと分かっている場合(面積が違うなど)、中央の格子点が交差点になることが確定します。
応用として、交差させないと面積が大きすぎて矛盾するというケースが有ります。
・曲がり角の交差が確定する構図２：小ループ回避
クロスウォールの線は交差点で直進する条件の下で一繋がりになっている必要があり、従って小ループが出来たらどれかの角を交差点にして回避する必要が有ります。
長方形の４隅のうち少なくとも１つは交差点になることもこの応用です。
また、直進する線は必ずその方向に進むので、それを用いて道を決定するケースも有ります。
・内側度が０で、盤面中央寄りにあるマスが絡む構図
内側度０のマスを上手く救出する(=外周まで繋げる)必要が有ります。
・面積２のマスが絡む構図
面積２と２色塗分け定理は非常に相性が良く、幾つかの問題に応用されています。
代表的なものが次の構図です(内側度が1である必要はなく、その場合奇数なら全てのマスの色が同じに、偶数なら逆になります)。
おまけ編 練習問題
Q7：衝突・小ループを回避しよう
推定難易度：★★★☆☆
Q8：中央の内側度０を救出するには……？
推定難易度：★★★★☆
Q9：面積２と２色塗分け定理の応用
推定難易度：★★★★★
ここまでご覧下さり、有難う御座います。皆さんも、是非クロスウォールの世界を楽しんでみて下さい。
