16面パズルを作ったのですが、シャッフルすると解けないパターンが出てしまいます

■□□□
□□□□
□□□□
□□□□

■=空きマス

プログラミング初心者です。javascriptの練習にと思い、↑のような16面のパズルを作りました。(正式名称はよくわかりません。マスをずらして絵柄を完成させるアレです)

パズルを始める際にマスの並びをシャッフルする、まではできたのですが、一つ問題があり、シャッフルされたマスの並びで絶対に解けないパターンが発生してしまいます。

16面のパズルの解けないパターンというのは、↓の状態から(2)と(1)を入れ替える事が不可能、というものです。

■(2)(1)(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,14,15

とし、これをシャッフルして

シャッフル後　⇒　14,8,1,7,12,9,3,5,15,2,10,6,4,11,13

のようにランダムな並び順となった配列を作り、それを元に画像を並べていく、というものです。

このシャッフル後の配列をチェックして解けないパターンであればエラーとしたいのですが、どのようなチェックをすれば良いのかがわかりません。数学のカテゴリに質問すべきかとも思いましたが、もしどなたかわかる方いらっしゃいましたら教えて頂けると幸いです。

No.2 ベストアンサー 回答者： buriburi3 回答日時： 2009/02/17 12:19

解けないパターンの識別方法は数学的に証明されています。

「15パスル　パリティ」で検索してください。
ただ、方法論としてはシャッフルするよりスワップする方が簡単だと思います。

この回答へのお礼

回答ありがとうございます。
パリティっていうんですね…
すっきりしました！ありがとうございます！

お礼日時：2009/02/17 12:40

No.1 回答者： yambejp 回答日時： 2009/02/17 11:45

単純なはなし・・・シャッフルしなければいいのでは？

このゲームの主旨は空マスと最多４つの隣接するマスとを
入れ替えるという処理ですね

よって隣接するマスをランダムに選び、入れ替えをおこなえば
すむはずです。（端のマスは例外処理をいれる）
どのくらいでバラバラになるかは微妙ですが、1万回も入れ替えを
行えばよいのでは？

この回答への補足

回答ありがとうございます。
その方法は最初に考えたのですが、数学的な考え方で配列をチェックできないものか、という点がどうしても気になってしまい、質問させて頂きました。やはり数学のカテゴリが専門でしょうか…

補足日時：2009/02/17 11:46