In article <uk76p8ngk.fsf@anet.ne.jp> tksotn@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
>等にしかならないことがあります。
>ピースをランダムに並べたときに、配置を見て、何らかの計算を行うことで
>目的形に出来るかどうかを判断する手段があるでしょうか？

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

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

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

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

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