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

【基本方針】

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

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

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

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

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

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

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

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

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

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

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

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

【最後の３ピース】

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

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

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