質問: 15パズルゲームについて 15パズルゲームって知ってますか? あれはどのようにしたらできるものなのか、そのやり方を教えてください。 それとできないパターンもあるものなのですか?
回答: 15ゲームの場合、16個の場所と、15個の石を使います。1から15までの数字を書いた石を使うと、幾つぐらい数字の配置の組み合わせがあるかというと、これは順列の問題ですから、仮に、16番目の場所を空けるとすると、15!個の組み合わせパターンがあることになります。 ところで、この15!個のパターンは、綺麗に半分づつに分かれます。つまり、パリティというパラメータがあって、どちらかをパリティ1とすると、他方はパリティ0となる、二つの異なる配置パターンに分かれるのです。 15!個の組み合わせの半分の15!/2個がパリティ1、残りの15!/2個がパリティ0です。そして、パリティが同じパターン配置のものは、時間さえかければ、かならず、石を動かして、別の配置に移ることができます。しかし、違うパリティの配置は、どういう石を動かしても、絶対に、配置が移ることはありません。 パリティを変える一番簡単な方法は、横に隣り合った石を位置交換することです。1から15まで、順番に並べている場合、最後の14と15の位置を入れ替えると、パリティが変り、もはやどう石を動かしても、これから、入れ替える前の、1から15までが整然と並んでいた配置に戻すことはできません。 途中の7と8でも、4と5でも、11と12でも、1から15まで整然と並んでいる石の隣り合った石を入れかえると、パリティが変化して、絶対に、別のパリティの配置には、石を動かすだけでは到達できません。 同じパリティの配置の移行は、早く済ませようと思えば、ブロック単位で動かすようにすれば、早く終わります。しかし、いずれにしても、パリティが同じ場合は、石を動かしていると、嫌でも、望んだ配置へと移って行きます。焦る必要はないのです。 パリティが違う場合は、どう動かしても、絶対に成功しません。パリティが同じか違うかは、元の配置と、目標にする配置で、1から15までの整列パターンを造ってみるよう試みることです。一方が、1から15までの整列で、他方が、この整列の14と15を入れ替えたような配置になれば、パリティが違っているのです。 何故パリティが違うと入れ替えが成功しないのかです。これは、行列式を、数式で定義するときに、sgnという関数が出てきます。これが、順番の配置のパリティを決める関数なのです。 sgn(1,2,3,4)=1 とすると sgn(1,2,4,3)=0 となります。 隣り合ったものを、入れかえると、パリティは反転します。隣り合ったものを二回入れかると、パリティは反転して反転するので、元に戻ります。つまり: sgn(1,4,2,3)=1 となります。 ここで、隣り合ったものでなく、もっと離れたもの、例えば、3ステップはなれた、最初の配置だと、左の1と右の4を入れ替えるような転置を考えます。この時、パリティはどう変化するかです。 1と4の入れ替えは、次のように、隣り合ったものどうしの入れ替えに還元できます: (1,2,3,4)初期状態 (1,2,4,3)転置一回 (1,4,2,3) (4,1,2,3) (4,2,1,3)転置四回 (4,2,3,1)転置五回 4ステップ離れている場合は、転置五回で、パリティが逆になります。 しかし、これは、3ステップでも、1と4を入れ替えた場合です。単に、4を、3ステップ移動させるという場合は、次のようになります: (1,2,3,4)初期状態 (1,2,4,3)転置一回 (1,4,2,3) (4,1,2,3)転置三回 単に、4を3ステップ移動させる場合も、転置三回で、やはりパリティが逆になります。しかし、15ゲームは、空きの場所がどこにあるかで、別の規定が生じます。 15ゲームに戻すと、任意の配置にある時、ともかく、左上を空き場所、次の右が1、それから右に番号を2,3と付け、一段下がって、左上を、4として、右へ5,6,7という風に、暫定的な数字を与えます。石の実質は変化していないので、この仮に与えた数字で、パリティの変化を見れば、元の数字の石の配置のパリティの変化と一致します。 石を動かす規則は、左右か、または上下に隙間があると、そこに入れるという操作だけしか許されていません。 左右に動かしても、パリティが変化しないのは明らかです。パリティを考えるとき、空いた場所は、この場合は関係がないからです。 すると上下に動かす場合はどうかとなります。上か下に、空いた場所を作り、そこに石を移動させるのです。この移動は、実は、上で考えた、3ステップの単に、一つの数字を移動させるだけの転置に丁度対応するのです。 最初の状態では、上から第一段の左端に空きがありました。この空きに、第二段の石つまり4を上げると、パリティが逆になります。しかし、第一段に空きを造ろうとすると、第一段の石を第二段に下げねばなりません。こうすると、第一段に空きがあるという、初期の空きの配置状態に戻ります。 こういう操作をすると、パリティが逆になる操作を二回行ったことになり、パリティは最初の値に戻ります。 第一段に空きがある状態、ということは、左右の石の移動はパリティに変化しないので、左端が空いている状態を、基本状態にすると、石を移動させても、最後には、基本状態に戻すということにすると、基本状態では、パリティは、常に変化していないということになります。 これは、空きが、第二段から第三段に移った場合、これを第二段に戻すと、またパリティが元になること、あるいは、第三段から第四段に空きを移すと、これを第三段に戻すと、またパリティが元に戻るということで、第一段に空きがあるのが、基本状態とすると、この基本状態に戻すと、どんな移動をその前に行っていても、パリティは変化しないということなのです。 もっと細かい話をしないと、まだ納得できないかも知れませんが、第四段,最下段の右端に空きが来るか、または、第一段左端に空きが来るか、どちらでもよいのですが、「基本状態」を定義すると、石を色々動かした後、最後には、基本状態に戻すとすると、配置順番のパリティは、変化しないということになります。 パリティには二種類があって、そのあいだで基本状態を定義すれば、移行がないということは、最初に述べたように、例えば、最下段の右端に空きを作る基準状態では、あらゆる順列の可能な15!の半分がパリティ1で、半分がパリティ0となり、異なるパリティの並びは、石の移動では、実現できないということになるのです。 単純には、隣り合う石を転置すると、パリティが逆になるので、こういう二つの配置は、どう石を動かしても、移行できないということが、パリティの保存の原理から出てくるのです。 最下段右端に空きがあり、1から順番に右上から数字が並んで、最後が14,15のものと、15,14のものは、パリティが違っているので、絶対、石を動かして移行できない配置なのだということになるのです。 (パリティが同じ配置は、必ず移行できるという証明がありません。あるいは、同じパリティであって、移行可能な場合と不能な場合があるのかも知れません。その場合は、パリティはもっと細かいものがあるのだということになります。しかし、そうではないというのが直観的な見解ですし、パリティが増えると、移行不能な配置ケースが、ものすごく増えてくるということになり、15ゲームの移行成功率は、1/4よりは高いという経験的な結果から、パリティは、二つしかないということが、確からしいということです)。