パッキングパズル理詰め手法1「パリティ」

length

メカニカルパズルはペンシルパズルと比較して理詰めで解けるものはあまり多くない。
特にポリオミノ系のパッキングパズルはピースセレクションや解数などに注目されることが多く、理詰めを念頭に置いて設計されていないものが多い。

しかし、いくつかのパズルでは理詰め的な考察によって解決に近づくことがある。この記事ではその手法の一つの解説をしていくことにする。
なお、この記事には既存のパズルの解答に関わる要素が多く登場する。

パリティ

最初に、ある有名な問題を考える。「欠けたチェス盤の問題」等と呼ばれるものだ。

欠けたチェス盤の問題

問題:8×8のチェス盤から対角の2単位を除いた62単位の盤面がある。ドミノ31個をこの領域に収めることはできるか？

『欠損チェス盤にドミノ・L型トロミノ・I型トロミノを敷き詰めたい』から引用

これは問題設定だけ見ればパッキングパズルそのものであるが、解が存在するとは限らないという(パズルとしては)特殊な状況になっている。そのような問題でも通用するような手法が存在するのであればそれは理詰めと呼ぶにふさわしいものであろう。

解:盤面を市松模様に塗り分ける(既に塗られているが)と30単位が白、32単位が黒に塗られる。一方、ドミノは隣り合った白黒各1単位を埋めるように配置されるので31個配置できたとすると白は31単位、黒も31単位だったことになる。これは矛盾である。

このように盤面を市松模様に塗り分け、各々の色の単位数に着目する解法をパリティ(あるいは単に市松など)と呼ぶ。

以降、パリティを用いた理詰めについて考えるが、その前にこのパリティ手法を少しだけ改編することにする。というのも、実はほとんどの場合塗り分けた色のうちの片方にのみ注目すればよいからだ。

解(改編):ドミノを配置すると1単位分の白の領域を占有するので31ピース収めるためには31単位分の猶予が存在しないといけないが、白の領域は30単位しかない。

このように少しだけだがスッキリと書ける。以降はこの書き方を主とする。

Tテトロミノ

もう1問「解けないパズル」を紹介する。パリティを扱う問題でドミノの次によく使われるのはTテトロミノであろう。

問題:10×10の盤面にTテトロミノ25個を収めることはできないことを示せ。

これはドミノを使う場合とは少しだけ様子が異なる。市松上での置き方が一意に定まらないからだ。

解:市松に塗ると50単位の白領域ができる。Tテトロミノを配置すると白領域のうちの1単位か3単位、いずれも奇数単位を占有し、したがって全てのピースを配置すると奇数×25、すなわち奇数単位の白領域を占有することがわかる。しかし、盤面の単位数とピースの総単位数が等しいのですべての白領域が占有されることがわかり、50は偶数なのでこれは矛盾である。

特に、盤面が隙間なく埋まることが重要であることに注意されたい。

パリティで「解ける」パズル

これまでの例で解が存在しないパッキングのような問題におけるパリティの扱い方を見た。次に解が存在する通常のパッキングパズルにおける応用例を見る。

F+11(仮題)

まず、パリティがどのように使われるかを端的に示した例題を用意した。気になる方は解を見る前に自分で考えていただきたい。

問題:Fペンタキューブ1個とダイキューブ11個を3×3×3に収めよ。

解:角が黒になるように市松に塗り分けると13単位の白領域ができる。各々のダイキューブはそのうちの1単位を占めるのですべて置いたとき残る白領域は2単位である。Fペンタキューブの置き方は底に敷くように置くか中央に置くかの実質2通り存在するが、底に置くと3単位分の白領域を占めてしまうため不適。したがってFペンタキューブは中央に置かれる(こちらは2単位分の白領域を占める)。あとはダイキューブを適当に詰めればよい。

つまり、特定のピース(の組)の置き方が複数考えられ、パリティによってそれらを区別することができればそのうちのいずれかに置き方を絞ることができるのである。
このような「即座に排除される仮置き」はペンシルパズルでも広く見られるものであろう。例えば、ループ系統のパズルの偶奇手筋(パリティだけに)のように。

パリティデビル

もう1問、このような方法で解に近づくことができるものを紹介する。小田原充宏氏の「パリティデビル」である。先述の例ほど極端ではないがこれも同様の手法を用いることを意識して考えられたものである。

問題:ポリキューブXUtnxyzd(画像)の8ピースを4×4×2に収めよ。

『第３回　パリティデビル』から引用

さて、出鼻を挫くようで申し訳ないが、このパズルは単純にパリティを適用するだけで解にたどり着くことは(おそらく)できない。
しかし、パリティによってこのパズルの重要な性質を知ることができ、それによって解を調べる手間を削減できる。

解の方針:市松に塗ると16単位が白となる。隙間が生じることはないのですべての白領域が埋まる。ここで、ペンタキューブでないピースの置き方を考えると必ずtnzyは偶数、txdは奇数単位の白領域を占める。したがって残ったペンタキューブは奇数単位の白領域を占めるような置き方しかできない。ここで、Uペンタキューブの凹みにXペンタキューブを嵌めるような置き方を考えるとどのように置いても4または6、いずれも偶数単位の白領域を占めることがわかる。したがって、解となる置き方ではX,Uがかみ合わさることはない。(後略)

通常パッキングパズルでは邪魔なピースを使いやすいピースで処理するような置き方から試すことが多いと思われるのでそのような方法が正しくないことを知るのは大きな進展である。
なお、ツールで調べたところ、XUが偶数単位を占める置き方は11通り、奇数単位を占める置き方は8通りであったので、単純計算で半分以上の手間が省けたと言える。

参考文献


この記事が気に入ったらサポートをしてみませんか？