16パズル

[OOTANI TAKASHI]

16パズルというのがありますよね。
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
を目的形とすると、ピースをばらばらにして適当に詰めたのでは、
スライドさせても場合によっては目的形にならず、
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14
等にしかならないことがあります。
ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
目的形に出来るかどうかを判断する手段があるでしょうか？

昔16パズルのプログラムを作ったときは、目的形からランダムにスライドを
数百回行って初期形を作りました。配置から判断できれば、乱数で一旦配置し、
目的形にならないと判断された場合は14番目と15番目のピースを入れ替えれば
よいので初期形作りがスムーズに出来ます。

--
tks...@anet.ne.jp

[Shinji KONO]

河野真治 @ 琉球大学情報工学です。

In article <uk76p8...@anet.ne.jp>, OOTANI TAKASHI <tks...@anet.ne.jp> writes
> ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
> 目的形に出来るかどうかを判断する手段があるでしょうか？

良く覚えてないけど、parity の問題だったと思うので、結構簡単
に計算できると思います。空白の位置をそろえて、偶数番目の偶数
の個数とかを数えればいいんじゃないでしょうか?

> 昔16パズルのプログラムを作ったときは、目的形からランダムにスライドを
> 数百回行って初期形を作りました。配置から判断できれば、乱数で一旦配置し、
> 目的形にならないと判断された場合は14番目と15番目のピースを入れ替えれば
> よいので初期形作りがスムーズに出来ます。

難しさの制御は出来ないね。

---
Shinji KONO @ Information Engineering, University of the Ryukyus,
河野真治 @ 琉球大学工学部情報工学科,

[to...@lbm.go.jp]

In article <uk76p8...@anet.ne.jp> tks...@anet.ne.jp writes:
>16パズルというのがありますよね。
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 14 15
>を目的形とすると、ピースをばらばらにして適当に詰めたのでは、
>スライドさせても場合によっては目的形にならず、
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 15 14
>等にしかならないことがあります。
>ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
>目的形に出来るかどうかを判断する手段があるでしょうか？

とりあえず「スライド」という操作では、
「穴」を元の位置に戻す限りは偶置換にしかなりませんよね。

《証明》
「スライド」の１操作は、「穴」と動かすピースとの置換である。
「穴」を元の位置に戻すまでの「スライド」回数は
どう頑張っても偶数回だから、全体としては偶置換である。

従って、目的形と奇置換の関係にある配置からは
到達不能であることが明らかです。
ランダムに並べた場合、半分の確率で、そういう配置になるハズです。

逆に、目的形と偶置換の関係にある全ての配置から
到達可能であるかどうかは、私には解明できていません。

戸田 孝＠滋賀県立琵琶湖博物館
to...@lbm.go.jp

[Shinji KONO]

河野真治 @ 琉球大学情報工学です。

In article <bnmvlh$aem$1...@bluegill.lbm.go.jp>, to...@lbm.go.jp writes
> 逆に、目的形と偶置換の関係にある全ての配置から
> 到達可能であるかどうかは、私には解明できていません。

経験的にはできますね。

[Tanaka-Qtaro-Yasuhiro]

田中久太郎です。

OOTANI TAKASHIさんの<uk76p8...@anet.ne.jp>から
>16パズルというのがありますよね。
＜省略＞
>ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
>目的形に出来るかどうかを判断する手段があるでしょうか？

まさにそういう話が、
ブルーバックス「不変量とはなにか」(ISBN4-06-257393-8)
という本の第３章に書いてあります。

--
Tanaka-Qtaro-Yasuhiro mailto:ta...@ca2.so-net.ne.jp

[to...@lbm.go.jp]

In article <bnmvlh$aem$1...@bluegill.lbm.go.jp> to...@lbm.go.jp writes:
>従って、目的形と奇置換の関係にある配置からは
>到達不能であることが明らかです。
>逆に、目的形と偶置換の関係にある全ての配置から
>到達可能であるかどうかは、私には解明できていません。
到達可能を証明するには、「こうすれば必ず解ける」
（但し、最適解とは限らない）という方法を１つ示せば良いわけです。
で、ちょっと考えてみたら、そういう解法が、何とか作れました。
しかも、これは16ピースに限らず、
辺の長さが共に２ピース以上である任意の長方形の盤面に通用します。
（それにしても、文字たけで説明するのが大変だ……）

【基本方針】

スペースの都合で方針変更を余儀なくされない限り、
上の段から順に、各段の中は左から順に目的のピースを入れていく。
既に目的位置に入ったピースは、可能な限り動かさない。
即ち、盤面を上から順に、以下のように並ぶ構造に常になるようにする。
・０段以上の「既に全ピースが目的位置に入った段」
・必ず１段の「左から０個以上のピースが目的位置に入っていて、
　その右はどのピースが何処にあるか判らない段」（以下「作業中の段」と呼ぶ）、
・０段以上の「どのピースが何処にあるか全く判らない段」
　（以下「未着手の段」と呼ぶ）
そして、「作業中の段」では、既にピースが目的位置に入っている範囲の右隣が、
次に目的位置に入れるべきピース（以下「着目ピース」と呼ぶ）の目的位置である。

【初期方針】
（「未着手の段」が２段になるまで）

「作業中の段」のうち「着目ピース」の目的位置を含めて
それより右側（以下「作業中の範囲」と呼ぶ）および「未着手の段」については、
「着目ピース」以外のどのピースが何処にあるかを全く制御しないものとする。
この場合、「未着手の段」が２段以上ある限り、「穴」も「着目ピース」も
「未着手の段」の中を自由に移動させることができるし、
「作業中の範囲」に２ピース分以上の幅があれば、
「作業中の範囲」の中まで含めて自由に移動させることができる。
即ち、「作業中の範囲」に２ピース分以上の幅がある限り、
「着目ピース」を目的位置へ持って来ることは容易である。

「作業中の範囲」の幅が２ピースになったら、
「着目ピース」を目的位置ではなく、
その右隣（＝「作業中の段」の右端）に置いて待機させておく。
本来の目的位置は「穴」とはせず、手近なピースで埋めておく。
この状態で、次の「着目ピース」
（＝「作業中の段」の右端を目的位置とするピース）は
「未着手の段」の中を自由に移動できるから、
目的位置（＝「作業中の段」の右端）の下隣へ移動させる。
（“手近なピース”が“次の「着目ピース」”だと困るので、
　「穴」を埋める際に、そうならないようにする）

この段階で、「穴」は「未着手の段」の何処かにあるハズだが、
これを「作業中の段」の下隣の段の右端の左隣へ持ってくることは容易である。
そうすると、「作業中の段」の右端から２ピース分の範囲と
その下隣の段の右端から２ピース分の範囲とを併せた
４ピース分のスペースに居る３ピースを自由に回せる状態になる。
そこで、左回りに１つ回すと、２つの「着目ピース」が同時に目的位置に入り、
「作業中の段」の配列作業が完了する。

【残り２段になって以降】
（最後の３ピースになるまで）

「未着手の段」が２段の状態で「作業中の段」の配列作業が完了したら、
その２段を併せて、次の「作業中の段」として扱い、
「未着手の段」は存在しなくなるものと考える。
「作業中の範囲」も２段分の幅があり、「穴」は常にその中にある。
「着目ピース」は常に２個である。

まず、「作業中の範囲」の中をグルグル回して、
「着目ピース」が上下に並ぶようにする。
これは「穴」が左右何れにあるかを問わなければ必ず可能である。

「穴」が「着目ピース」より右にある場合には、
「着目ピース」の右隣に「穴」が来るよう、
必要なら「穴」の存在する段に居るピースを右へ寄せてから、
「着目ピース」と「穴」とを含む２段×２ピース分のスペースで
３ピースを回せば、「着目ピース」が元の位置の右隣で上下に並んで
その左側に「穴」がある状態にできるので、そのようにする。
即ち、以下では「穴」は「着目ピース」より左にある。

このとき、「着目ピース」が目的位置とは上下が入れ替わった配置であれば、
「着目ピース」の位置を右端、その目的位置を左端とする範囲
（その中に「穴」があるハズ）をグルグル回すことによって、
「着目ピース」を２つ同時に目的位置へ入れることができる。

「着目ピース」が目的位置と上下が同じ配置で右端以外の場所に居る場合には、
まず、「穴」がある段の方の「着目ピース」（以下「Ａ」と呼ぶ）を左へ寄せて、
「Ａ」が居た位置を「穴」とする。
次に、他方の「着目ピース」（以下「Ｂ」と呼ぶ）と右隣の２ピースの
併せて３ピースを、「穴」を含めた４ピース分のスペースで回して、
「Ｂ」が元の位置の右隣に居て、「穴」が「Ａ」の元の位置に来るようにする。
続いて、「Ｂ」の元の位置に来たピースと左隣の２ピースの
併せて３ピース（これには「Ａ」が含まれる）を、
「穴」を含めた４ピース分のスペースで回して、
「Ａ」が「Ｂ」の左隣（＝「Ｂ」の元の位置）に居て、
「穴」が「Ａ」の元の位置に来るようにする。
更に、「Ａ」「Ｂ」と「穴」を含む４ピース分のスペースで
３つのピースを回して、「Ａ」「Ｂ」が元の位置の右隣で縦に並ぶようにする。
このとき、２つの「着目ピース」の上下は逆転し、
かつ「穴」は移動した「着目ピース」より左にあるから、
あとは上述と同様である。

「着目ピース」が目的位置と上下が同じ配置で右端に居る場合で、
残りピースが５個以上ある場合、
即ち「作業中の範囲」に３ピース分以上の幅がある場合には、
必要なら「穴」のある段のピースを左へ寄せて
「穴」が右端の左隣または更にその左隣に来るようにしてから、
右端から３ピース分の幅×２段の６ピース分のスペースで５つのピースを回して、
「着目ピース」の一方が、他方の居た位置に来て、
その左隣が「穴」になるようにする。
「穴」の左隣は、他方の「着目ピース」となる。
次に、右端の２つのピース（「着目ピース」の一方が含まれる）と
その左隣との４ピース分のスペースにある３ピースを回して、
その中の「着目ピース」が元の位置に来て、
「穴」は元通り、左へ寄せた方の「着目ピース」の右隣へ来るようにする。
この状況は、右端に残った方の「着目ピース」を「Ｂ」、
左へ寄せた方の「着目ピース」を「Ａ」と考えれば、
「着目ピース」が本来の位置の左隣にあった場合の
上述の手順の途中経過と同じになるから、以下は同様である。

【最後の３ピース】

最後には３ピースが２段×２ピース分のスペースに残る。
その中でグルグル回せることを考えると、
本質的には２通りの可能性しか無い。
３ピース全てを目的位置に入れられる場合と、
それとは逆順に並んでいて入れられない場合である。
入れられない場合は、「穴」の位置を合わせれば
目的形とは奇置換の関係になるから、
目的形と偶置換の関係にある初期配置から到達することは無い。
即ち、目的形と偶置換の関係にある初期配置から以上の手順を踏めば、
必ず「３ピース全てを目的位置に入れられる場合」に到達する。

従って、「目的形と偶置換の関係にある初期配置」からは
必ず目的形に到達可能である。

戸田 孝＠滋賀県立琵琶湖博物館
to...@lbm.go.jp

[OOTANI TAKASHI]

ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
>> ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
>> 目的形に出来るかどうかを判断する手段があるでしょうか？
>
> 良く覚えてないけど、parity の問題だったと思うので、結構簡単
> に計算できると思います。空白の位置をそろえて、偶数番目の偶数
> の個数とかを数えればいいんじゃないでしょうか?

同じ個数でも出来る・出来ないの両方のパターンがあるので、これではだめです。
単純に奇数番目偶数番目だと縦と横に対して対象じゃないので、
盤面を市松模様に塗って、目的形での色と同じ色のますにあるピースの
数を数えてみましたが、これもだめ。

田中さんご紹介の本を見てみます。
--
tks...@anet.ne.jp

[OOTANI TAKASHI]

OOTANI TAKASHI <tks...@anet.ne.jp> writes:
> ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
>>> ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
>>> 目的形に出来るかどうかを判断する手段があるでしょうか？

> 田中さんご紹介の本を見てみます。

(該当の章だけ)読みました。直接的な答えは書いてなかったですが。

空白が最後にあるとして、x[1]～x[15]に1～15の数字が入っているとします。
これを先頭から単純ソートしてそのときの交換回数が偶数ならOK。
で、いけそうです。

田中さんありがとうございました。
--
tks...@anet.ne.jp