久しぶりの15ゲームです。
実は、自分で作ったゲームなのに、たまにしかクリアできない、という状況に陥っていました。
で、自分の能力不足と思い込んでいたのですが、Wikipediaを見返すと、どうもクリア不可能な配置って言うのがあるんですね。これは、、ゲームとしてはイタダケないです。。クリアできないゲームなんて、イライラするだけで使いたくなんかありません。
で、更に調べると、クリアできるかをチェックする方法があるコトがわかりました。
スライドパズルの配置の判定方法
http://homepage2.nifty.com/TOMOMI/text/14-15.pdf
これは、数学ですね。。何故、これで判定できるのかを理解するのは、後日に回すとして、アルゴリズムだけ、頂こうと思います。
アルゴリズム
並び替えたコマの数字を下の順で並べます。
並んだ数字を、1~15に並べ替える。で、並べ替えるために動かしたコマの移動量（コマを跨いだ数）を合算する。
コマの移動量の合計が、偶数ならクリア可、奇数ならクリア不可、
・・・、となるそうです。
実装
チェック関数を作ります。
private boolean checkNumLine()
コマの数値を、決められた順に並べ替えます。
// チェック用数列の作成
int[] idxForCheck = {3, 2, 1, 0, 4, 5, 6, 7, 11, 10, 9, 8, 12, 13, 14, 15};
ArrayList<Integer> checkLine = new ArrayList<Integer>(15);
for( int i = 0; i < 16; i++ ) {
if( pieces.get(idxForCheck[i]).numIdx != 15 )
checkLine.add(pieces.get(idxForCheck[i]).numIdx);
}
checkLineを0~14に並べ変えた時の移動数を算出します。
int moveCount = 0;
for( int i = 0; i < 15; i++ ) {
for( int j = i; j < 15; j++ ) {
if( checkLine.get(j) == i ) {
checkLine.remove(j);
checkLine.add(i, i);
moveCount += j - i;
}
}
}
移動量が、偶数か奇数かを戻します。
// 移動数が偶数なら、クリア可能
return ( moveCount % 2 == 0 ) ? true : false;
で、これをシャッフル関数で呼び出します。
private void shufflePieces(){
Collections.shuffle(pieces);
for( int i = 0; i < 16; i++ ) {
pieces.get(i).setPosIdx(i);
if( pieces.get(i).numIdx == 15 )
emptyPosIdx = i;
}
// クリア可能な配列か、チェック
if( !checkNumLine() )
shufflePieces();
}
解決しないコトなんか、あるんでしょうか…。少し不安ですが、テストしてる感じでは、大丈夫そうです。
しかも、毎回クリアできる！最高です。
こうなると、タイマーを付けたくなりますね。。
ソースコードはこちらで公開しています。
https://github.com/et79/Game15