2012年03月15日

スライドパズルのゴール可能な配置と不可能な配置

スライドパズルのゴール可能な配置と不可能な配置について調べた結果のまとめ

slide3x3_goal.png

3x3のゴールが上記の場合、以下のように縦か横で隣接する数字を1組入れ替えるると、ゴールの配置にすることは不可能です。
slide3x3_imp.png
また、上記はすべて、7と8が入れ替わった配置にすることができます。

さらに、上記のような縦か横で隣接する数字を1組入れ替えた配置で、さらに縦か横で隣接する数字を1組、計2組入れ替えるとゴール可能になります。
slide3x3_pos.png

前回のゴール可能か不可能の判断プログラムで参考にした以下の解説から考えると
14-15パズルは何故解けないか?(Jan 1996)   pdf file

ゴール可能の配置から、1組の入れ替えでは移動距離の和が奇数となり、2組の入れ替えでは移動距離の和が 奇数+奇数 = 偶数 となり、1組の入れ替えはゴール不可能、2組の入れ替えはゴール可能になることが分かります。

まとめると、
・ゴール可能な配置からスライドで移動させたどの配置でも、縦か横に隣接する1組の数字を入れ替えるとゴール不可能になります。
・ゴール不可能な配置からスライドで移動させたどの配置でも、縦か横に隣接する1組の数字を入れ替えるとゴール可能になります。
・上記の2つは、3x3だけでなく、2x3、4x4、2x5などの長方形型(?)のスライドパズル全てで成り立ちます。

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

スライドパズルの配置チェックプログラム

昨日の配置のゴール可能、不可能を判定するプログラムを、3x3の全ての配置パターンで確認したときに使用したサンプルプログラムと結果
配置チェックプログラムの動作確認

posted by jun1 at 00:40| Comment(0) | TrackBack(0) | ソフト
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/54446349

この記事へのトラックバック