スライドパズルの配置の判定方法

初期配置によって目的の配置に移動することができるかどうかの判断方法について調べていると、解説しているサイトを見つけました。

・パズルやら勉強やら？

このサイトの下の方にある、14-15パズルは何故解けないか？(Jan 1996) 　　pdf fileに解説があります。

14-15パズルは何故解けないか？(Jan 1996) 　　pdf file の説明より、与えられた配置がゴール可能かどうかを、以下のようにして判定しています。

• 1.　配置から数列を求める

与えられた配置から、数字がカラの場所を0として、ひとふでがきのような順番で数字を並べていきます。 そこから0を除いたものを数列とします。。

例.　以下の左のような初期配置の場合、右のような順番で考えると、 [ 1, 3, 2, 6, 7, 0, 5, 8, 4 ]になります。

0を取り除くと、[ 1, 3, 2, 6, 7, 5, 8, 4 ]になります。これが初期配置の数列です。
ゴールの数列を同じ順番で求めると　[ 1, 2, 3, 6, 5, 4, 7, 8 ] になります。


縦のマス目の数が偶数になる場合、1行目は右から始めて、最後が右下のカドになるようにします。

4x4（15パズル）のゴールの数列は、[ 4, 3, 2, 1, 5, 6, 7, 8, 12, 11, 10, 9, 13, 14, 15 ]になります。

注.　サンプルプログラムの実装を、縦のマス目が偶数の場合と奇数の場合でスタート地点が異なるようにしているため、 上記のようにしています。

• 2.　初期配置の数列からゴールまでの移動距離の和を求める

例.　 [ 1, 3, 2, 6, 7, 5, 8, 4 ] から、 ゴールの数列 [ 1, 2, 3, 6, 5, 4, 7, 8 ] にするために、移動させた数字の距離を数えます。 以下のように数えると、移動距離（飛び越した数）の合計は　4 になります。


• 3.　移動距離の和でゴール可能かどうかを判定する

初期配置の数列から、ゴールの数列にするための数字の移動距離の和が偶数、奇数で判断します。

• 移動距離の和が偶数の場合、ゴール可能
• 移動距離の和が奇数の場合、ゴール不可能

上記の例の場合、移動距離の和は偶数の4なので、ゴールすることが可能です。

• サンプルプログラム

上記の判定方法を実装したJavaのサンプルプログラムは以下になります。

配置チェックのサンプルプログラム

• サンプル

実際の配置で確認したい場合は、以下のページで、[手動配置]にチェックを付けて、番号を好きな位置に移動させてください。 そして[手動配置]のチェックを外します。チェックを外す時に、配置がゴール可能かどうかをチェックされます。 もし、ゴール不可能の場合は、以下のメッセージが表示されます。

・スライドパズル　（Applet）



• マス目の数の違いによる配置

3x3（8パズル）や4x4（15パズル）などのスライドパズルでは、全配置パターンの半分がゴール可能ということになります。



• Android用のスライドパズル

Android用のスライドパズルを公開しています。

・CellGame (Android用)