１５パズルゲームについて

Question

１５パズルゲームって知ってますか？
あれはどのようにしたらできるものなのか、そのやり方を教えてください。
それとできないパターンもあるものなのですか？

aster · Accepted Answer

＞パソコンのパズルの早さのランキングでは 
＞１０秒台とかもあったんですよ。それも慣れですかね？ 
＞それとも、一番最初の形が最後の形に近かったのでしょうか？ 
＞まあ、おそらくそうですね。

先の回答では、「不可能な配置もあるのですか」という質問に対し主に答えたので、どうすれば、早く解けるのかということに主点がありませんでした。

「空き場所を含めた輪を回すようにして行く」というのは、実は、先のパリティの保存という考え方から出てくるのです。

最終完成状態を仮に、１から１５までの数字が並び、最後に空きが来る配置だとすると、１から１５の数字の整列をしなければならないという課題と、もう一つ、最後の転置で、下段第四段に空きが来るようにしなければならないという，二つの課題を満たしつつ、石の移動を行わねばならないのです。

前の整列パターンを造るということだけを考えていると、うまく整列したと思っていると、最後のところで、空きがうまく、第四段に来なくなることがあります。そうなると、整列が壊れる訳で、もっとたくさん石を動かさなければならないということになります。

「空き場所を含めた輪を回すようにして行く」というのは、数字を整列させて行くのですが、「輪を回す」というのは、右で、石を上に上げれば、空きは下に降りて来て、これを元のパリティに戻すには、石をもう一度上から下に下げないと行けないのですが、左で、そういう操作を行うと、石を整列させるような動かし方で、しかも、空きの位置は元に戻しているという操作になるのです。

空きの位置が、到達配置の空き位置に来るように、輪を回していると、数を整列させるように石を動かしていると、最後の段階で、空き位置がうまく決まって、しかも数の列はうまく整列しているということになるので、問題が早く解けるのです。

「速く解く動かし方」としては、一般的に通用するのは、この方法しかないのです。上で説明したことから、「一般的な方法」と言えば、これしかないのがわかるのです。

基準の形で考えて、同じパリティの「解ける配置」の数は、１５！／２個あるのであり、これは、約６５００億パターンというとてつもない数のはずです。色々な配置で、理論的に、何回の転置で、最短で、到達最終配置に達することができるかは、配置によって異なり、難しすぎるのではっきり分かりませんが、一般には、最短で１００転置とか、数百転置が必要だと考えるのが自然です。

理論的な最短転置数が１００転置の場合、３０秒に１００回も石を動かせる訳はないので、３０秒では、絶対、解けないのです。

最短転置数が１０とか２０の場合、１０秒とか３０秒で解ける可能性があります。しかし、こういう場合は、実は配置をよく眺めると、最終配置パターンからの転置のずれというのが、直観的に洞察できることがあります。

空きを含めた輪を回すというのは、テクニックというより、そういう方法を結局は取らないと、問題は解けないのです。

最短転置数が少ない場合は、最終状態をどう崩すと、こういう配置になるのかが直観的に分かるのであり、その逆の石の動かし方をすればよいということになります。

しかし、こういう直観的洞察で、解き方が分かるのは、最短転置数３０ぐらいまでのはずです。それ以上複雑だと、３６ステップだと思って，実は３６０ステップの場合もあり、こういう場合は、石を理論的に最少数動かすだけで、６分とか１０分とか必要になります（１秒に１個石を動かして、３６０秒つまり６分かかるのです）。

３０秒で解けると言っている人は、最短転置数がせいぜい４０ぐらいまでの特殊なケースだけを解いていることになります。

もし石を自由にならべかえて配置を造り、これを解くようにという場合、理論的に、その半数は、永遠に解けない配置です。パリティが変化しないような配置ヴァリエーションしか選べないようになっている場合、最終状態を崩して、乱れたような状態にするのに、せいぜい１０とか２０、多くて３０，４０ぐらいの石を動かして配置を変えることになります。

こういう風だと、最短転置数も、１０とか２０、多くて３０，４０以下になるのであり、３０秒で解けるということが言えるようになるのですし、実際、この程度の変化だと、どうやって、元の配置を崩したのか、先に述べたように、直観的に見て分かることがあるのです。

最初は分からなくとも、輪を回すように転置させて行っていると、パターンが見えてくるのであり、すると、このパターンの解き方はこれ、という風になり、あっという間に解けます。

コンピュータでも、手動の配置変化でも、せいぜい４０ステップぐらいで解けるような配置の変換しか行っていない可能性が高いのです。３０秒で解けるといっている人は、３０秒で理論的にも解ける問題を解いているので速いのであって、理論的に、５分は絶対必要な配置というのは、出てこないようになっている可能性があります。

また繰り返しになりますが、３０秒で解ける問題は、最短転置数が３０か２０ぐらいのもので、この程度の転置だと、その配置パターンから、元の配置からのずれが分かるのであり、「ずれたパターン」を読み取る力というか、パターンの規則性を記憶すると、速く解けるということになります。

速く解けるテクニックは、最短転置数の少ないパターンを、どれだけ覚えているかによると言えます。輪を回す方法で、最短転置数の少ないパターンへと進めて行き、ある段階で、「解けるパターン」になっているとパターン読みよりができると、それで問題は解けたことになります。

puni2 · Answer

No.4：
>パソコンでも「戻るか戻らないか判らない」と言う形にする事も出来ますので。
おっしゃるとおりです。ただ，今まで出会ったこのゲームのソフトでは，そのような（上級者向けの）機能がついているものはなく，完成状態からコマを空所に動かす操作を何回もランダムに繰り返して，初期状態にするというものばかりだったので，ついそれを前提として書いてしまいました。
1～15の数字を最初からランダムに配置したうえで，「さあ，できるかどうか分からないけれど，とにかくやってみな」というほうが慣れた人には面白そうですね。

お礼：
>わっかを意識してやるというほうほうは前から知っていて、 
>できるんですが、それでは早さに限界があるんじゃないでしょうか？ 
>私も早いときは３０秒でできますし、
なーんだ。それを早くおっしゃってくださいよ。てっきりなかなか解けずに困ってらっしゃるものだと思いました。
それでは私の回答も意味がありませんでしたね。
私は残念ながらこの方法しか知りません。というか，ゲームの構造からいって，この操作を基本にせざるをえないのではないかと思いますが…。
この方法でも，慣れれば30秒もかからないような気がします。
ただ，本物のパズル（パソコンソフトでなくておもちゃ屋で売っているほう，という意味）の場合，受け皿が浅いものが多いので，あまり勢いよく操作すると駒が飛んで行ってしまいます。
私が昔持っていたものは，駒の側面に溝が付いていて互いに噛み合うようになっていました。これは飛び出さないかわりに，14と15を入れ替えたりはできません。

aster · Answer

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

ymmasayan · Answer

既に結論は出ているようですが、思い出深いので余談を。

私が子供の頃よくやりましたが、「１５ゲーム」と言う名前でした。
「１５パズルゲーム」という名前は始めて聞きました。

応用編のようなものとして「岩窟王・・・」というのが有りました。
詳しい事は忘れましたが、大きさ・形の違う駒を「１５ゲーム」の要領で
動かすものです。「１５ゲーム」よりはるかに難しかった事だけ覚えています。

＞（パソコン上のゲームならバラバラにはならないので，必ず元に戻りますね。） 

No.3で述べられていますが、パソコン上なら「必ず元に戻せるようにバラバラに
する事が出来る」と言う意味に理解しました。
パソコンでも「戻るか戻らないか判らない」と言う形にする事も出来ますので。

puni2 · Answer

以前，同じような質問があり，そちらで詳しく答えましたので，よかったらご覧ください。
自分流の方法では，コマを動かすときに，単に「空所に移す」と考えず，「空所を含むわっかを回す」ととらえるのがミソだと思っています。

できないパターンは，既出の「14と15の入れ換え」が有名ですが，これに限らず，
「ある状態から，隣り合っている2枚のコマだけを入れ換えた状態に持っていく」ことはできません。
全てのコマをケースから出してバラバラにして，それをまたケースにデタラメに入れたとき，最初のパターンに戻せるものと，戻らないもの（14と15が入れ替わった形になら戻せる）とがあることになります。
（パソコン上のゲームならバラバラにはならないので，必ず元に戻りますね。）

なお，その後出た本の中に，このパズルが取り上げられているのを見付けました。
14と15が入れ替わっているとなぜ元に戻せないのか，の証明も載っています。
高木貞治著『数学小話』岩波現代文庫，2002年4月発行，900円
（この本自体はもともと戦前に出たものですが，新たにこの文庫に収められました）

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?q=220430

osamuy · Answer

1から13まで揃っていて、14と15が入れ代わったものは、不可能パターンだと、マーチン・ガードナーあたりの本で読んだ事があるような。

gakutensoku · Answer

> それとできないパターンもあるものなのですか？

有名な不可能パターンに、14と15を入れ替えたものがあります。

|01|02|03|04|
|05|06|07|08|
|09|10|11|12|
|13|15|14|XX|

の状態から14と15を入れ替えるというものです。

この問題が解けたら賞金を出すといってこのパズルを売り出し、
大儲けをした人の話を聞いたことがあります。

解き方については詳しくは分かりません。
以下のサイトが参考になるでしょうか。

参考URL：http://www.ic-net.or.jp/home/takaken/so/15pz/

１５パズルゲームについて

No.4：

既に結論は出ているようですが、思い出深いので余談を。

以前，同じような質問があり，そちらで詳しく答えましたので，よかったらご覧ください。

1から13まで揃っていて、14と15が入れ代わったものは、不可能パターンだと、マーチン・ガードナーあたりの本で読んだ事があるような。

> それとできないパターンもあるものなのですか？

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング