１５パズルで数学しよう！ 〜２〜

パズル成立判定の考え方（★）

　このセクションは、ちょっとだけ難しい話になります。
　なるべく数学の専門用語は使わないようにしますが、どうしても触れなければならない部分も出てきます。順を追ってわかりやすく説明してみますので、どうかお付き合いください。

図1.3 逆１５パズル

　具体的な判定方法を説明する前に、まず逆１５パズルというものを紹介します。
　右の図を見てください。
　見ての通り、通常の１５パズルの完成図と、左右が逆になっています（だから逆１５パズルというわけです）。
　もしこの状態からパズルをはじめたら、この１５パズルは完成すると思いますか？
　答えは、ＮＯです。
　１４−１５パズルと同じく、これも、どう頑張っても完成させることは出来ません。

　では、１４−１５パズルとこの逆１５パズル、一体どういう関係があるのでしょう。
　それを説明する前に、１４−１５パズルの形からはじめる１５パズルのJavaアプレットをこちらに用意しましたので、Javaアプレットをご使用の方はそのウィンドウを開いておいてください。そうでない方は、お手元の１５パズルを１４−１５パズルの形（図1.2 参照）にならべておいてください。
　用意が出来ましたら、そこから逆１５パズルを作ってください！
　
　いかがですか？　できたでしょう！
　手元のJavaアプレットでない１５パズルをお持ちの方は、他の完成できなかった形からはじめてみて、この逆１５パズルの形に出来るかどうか試してみてください。必ず出来ると思います。だって、どの形も１４−１５パズルの形になったはずなんですから。

　ここで、一つの考え（予想）が浮かびませんか？　つまり、
『完成できない１５パズルの初期配置が見つかったら、その左右対称にしたものは完成できる！』
　ということです。
　因みに、もしこの予想が正しいとすると、全ての初期配置（１４−１５パズルの形を含む）の中で、完成させられる１５パズルは全体の半分だということが分かります。
　
　結論から言いますと、実はこの予想は正しいのです。
　１５パズルの持つこの性質を、専門用語でパリティ（parity／偶奇性）と言います。
　みなさんの中にも、パリティチェックという言葉を聞いたことのある人がいらっしゃるかもしれません。そのパリティと同じです。
　そしてまさに、パリティチェックをすることで１５パズルの完成できるかどうかの判定が出来るのです！

具体的なパズル完成判定方法！（★）

　このセクションは、前のセクションより更に少し難しくなります。
　でもやはり数学の色は濃く出さないようにしますし、今回は実際の判定方法を実践を交えて紹介しますので、頑張って読んでみてください。

　まずはとにかく、手を動かすことからはじめましょう。　図1.1 をもう一度見てください。例として、この図を使って説明します。
　
　一番左上の数字は［４］です。そこから右に見ていって、１行見たら次の行の一番左に移ってまた右に見て、最後まで各々の数字を見ていってください。
　その中に、４より小さい数字はいくつありましたか？
　［３］、［２］、［１］の順に、３つありましたね。
　
　同じことを、今度は［４］の隣の［13］でやってみてください。つまり、そこから右にずーっと数字を見ていって、１３より小さい数字を数えていってください。
　［８］、［３］、［12］、［６］、［９］、［５］、［２］、［１］、［11］、［７］、［10］の順に、合計１１個ありましたね。
　
　これと同じことを、ずーっと最後までやってみてください。
　注意点は、その数字よりも右（下）の数字だけを見て、その数字より左（上）にある数字は見てはいけない、ということです。そしてその数字よりも小さい数字がいくつあるかを全て数えてください。
　全部数えたらそれを足してみましょう。この場合、こうなるはずです。
　　３＋11＋６＋10＋２＋８＋３＋４＋２＋１＋３＋０＋０＋１＋０ ＝ 54
　これは、偶数ですね。
　では同じことを、１４−１５パズルでも試してみてください、といっても、これはすぐに分かりますね。
　［14］と［15］が入れ替わっているだけなので、この部分だけが影響して、その数は １ となり、これは奇数です。
　
　では次に、更に同じことを逆１５パズルでもやってみましょう。　ここで注意しなければならないことは、これは空マスが一番右下には無いということです。
　しかし一番下の行において、３回の移動で空マスを右下に持っていくことが出来るので、この場合は問題なくそのまま数えていっても構いません。　でも普通は、この数え方は空マスが一番右下にある時の方法だと覚えておいてください。
　で、具体的に計算しますと、 ２１ となります。
　
　ここで、専門用語をもう一つ。今数え上げたこの数のことを転倒数(inversion number)と言います。
　即ち、図1.1 の配置の転倒数は５４、１４−１５パズルの転倒数は１、逆１５パズルの転倒数は２１、というわけです。

　勘のいい方なら、もう気付かれたかもしれませんね。そうです。
　この転倒数が、偶数ならば完成できる、奇数ならば出来ないということです！
　そしてこれがパリティ（偶奇性）という言葉の意味であり、この転倒数を数えることがパリティチェックなのです。

図1.4 １５パズル（完成図）

　一応、右の完成図を見て、パリティチェックをしてみてください。結果は明らかですが、転倒数は０、即ち偶数になってますね。

　ところで、先程「完成できる配置の左右逆のものは完成できない」と言ったのを覚えておいででしょうか。
　これもこのパリティから説明が出来ます。　と言っても、かなり数学的な話になりますので、ここではその理由の概要だけ話します。
　転倒数が偶数の配置なら、左右を逆にした配置は、転倒数は奇数になります。奇数だったら偶数になります。つまり、パリティが入れ替わるのです。
　以上(笑)

　なお、ここでは結果だけに触れましたが、その証明をきちんとやっていません。
　次回は、その証明に挑戦してみたいと思います。
　ただしこれは、かなり数学的知識を必要とするものになると思いますので、興味のある方だけで結構です。興味の無い方は、読み飛ばしてくださっても構いません。

To be continued...