元祖ワシ的日記

穴の位置にも１６のタイルがあると仮定してください。 ２つのタイルを入れ替える操作を繰り返し、完成形になるまでの繰り返します。 この入れ替えは隣同士でなく、タイルを盤面から取り、物理的に入れ替えることを意味します。 完成系になるように入れ替えて行くやり方はいろいろあるのですが、ある盤面からある盤面に変換する入れ替えの回数が偶数であるか奇数であるかは最初の盤面の配置で決まります。 すなわち、どのように入れ替えて言っても、完成形になるまでの手数の数は偶数であるか奇数であるかが決まっているのです。これは偶置換と奇置換といって代数学では有名な定理です。 タイルをスライドさせるというのは１６とその隣のタイルを入れ替えるということと考えられます。 ところで、最初に１６が右下にあると仮定すると奇数回の移動では１６のタイルは右下にはやってくることがありません。必ず偶数回の移動をしなければなりません。 したがって、ある盤面から完成形に移動する入れ替えの回数が奇数ならば、どうやっても完成形に持っていくことはできません。 これは例えば１と２が入れ替わっただけの１６パズルを解こうと努力をしてみるとわかります。どんなに頑張っても解くことができません。 では、逆に入れ替え回数が偶数ならば解けるのかと言えば、これは真です。（証明は実際にアルゴリズムを提示しないとだめですが） したがって、よりスマートな解法としては 「解けないと判定できたら任意の２つのタイルを入れ替える」 これで必ず解ける１６パズルが完成します。