15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる

Question

###前提・実現したいこと
ここに質問したいことを詳細に書いてください

8パズルのAスターアルゴリズムを15パズルにして解いています。
短い手数の15パズルは解けるのですが、

1 3 4 8
2 6 14 7
0 9 12 15
5 11 13 10

の28手詰めの15パズルを与えると、ArrayIndexOfBoundsExceptionが発生したので、
ハッシュテーブルを
boolean[] visited = new boolean[990000];
にして解消しますと、無応答になります。無応答と言うかWhile文で探索中のままになっている？！

8パズルはこのA*アルゴリズムで解けています。15パズルにして応用して解こうとしています。
解決できませんか？

ちなみに、
1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

の入力は8手詰めで、8が出力されます。

###発生している問題・エラーメッセージ

エラーメッセージ

###該当のソースコード

import java.util.*;

class field{
	int[] cell = new int[16];
	int evaluation;
	int[] route;
	int floor;

	field(int[] cell, int hash){
		floor = 1;
		route = new int[1];
		route[0] = hash; //route[0]初期状態のハッシュキー
		for(int i=0;i<16;i++) this.cell[i] = cell[i];
		int eva = 0;
		for(int i=0;i<16;i++){
			if(cell[i] != 0){
				//横方向の距離を加算
				//i:着目しているセル
				//cell[i]:着目している数字
				eva += Math.abs((cell[i]-1)%4 - i%4);
				//縦方向の距離を加算
				eva += Math.abs((cell[i]-1)/4 - i/4);
			}
		}
		evaluation = eva;
	}


	field(int[] cell, int[] route, int hash){
		this.floor = route.length;
		this.route = new int[floor+1];
		System.arraycopy(route, 0, this.route, 0, floor);
		this.route[floor] = hash; //hashを格納する
		for(int i=0;i<16;i++) this.cell[i] = cell[i];
		int eva = 0;
		for(int i=0;i<16;i++){
			if(cell[i] != 0){
				//横方向の距離を加算
				//i:着目しているセル
				//cell[i]:着目している数字
				eva += Math.abs((cell[i]-1)%4 - i%4);
				//縦方向の距離を加算
				eva += Math.abs((cell[i]-1)/4 - i/4);
			}
		}
		evaluation = eva; //推定コスト
	}

	public String toString(){
		return new String(cell[0] + " " + cell[1] + " " + cell[2] + " " + cell[3] + "\n" +
			 cell[4] + " " + cell[5] + " " + cell[6] + " " + cell[7] + "\n" +
			 cell[8] + " " + cell[9] + " " + cell[10] + " " + cell[11] + "\n" +
			 cell[12] + " " + cell[13] + " " + cell[14] + " " + cell[15] + "\n");
	}
}



class ev_list{
	field elem;
	ev_list next;

	ev_list(){
		next = null;
		this.elem = null;
	}

	ev_list(field elem){
		next = null;
		this.elem = elem;
	}

	public void insert(ev_list node){
		//ヒューリスティック関数の値が次のノードの値より大きい、
		//または次のノードが先端のとき挿入
		if(this.next == null || this.next.elem.evaluation + this.next.elem.floor < node.elem.evaluation + node.elem.floor){
			//次のノードよりヒューリスティック関数の値が小さい時
			//this, this.nextにnodeを挿入し、this, node, node.next(this.next)にする
			node.next = this.next;
			this.next = node;
		}else this.next.insert(node);
		//次のノードの値が等しいか大きい時、次のノードにnodeを挿入する
	}

	public field pop(){
		if(this.next == null) return null;
		if(this.next.next == null){ //次の次がnullなら
			field temp = this.next.elem; //この次のフィールドをtempへ
			this.next = null; //この次はnullにする
			return temp; //この次だったフィールドのtempを返す
		}else return this.next.pop(); //次の次がnullでなかったら、次をpopする
		//最先の要素を引き出す
	}
}



public class Algo47{
	static final int LEFT = 0;
	static final int RIGHT = 1;
	static final int UP = 2;
	static final int DOWN = 3;
	static final int[] factor = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8172, 16344, 32688}; //1から始まり、前の要素を2倍する

	//ハッシュキー生成関数
	static public int hashkey(int[] cell){
		int[] val = new int[16];
		System.arraycopy(cell, 0, val, 0, 16);
		for(int i=0;i<16;i++){
			for(int j=i+1;j<16;j++){
				if(val[j] > val[i]) val[j]--;
			}
		}
		//valは、0も多いがまちまちの値が出力される、ハッシュに関わる数
		int hash = 0;
		for(int i=0;i<16;i++){
			hash += val[i] * factor[15-i]; //factorから大きな数字から取り出され掛け合わされる
		}
		return hash;
	}



	static public field dehash(int key){
		int[] cell = new int[16];
		for(int i=0;i<16;i++){
			cell[i] = key/factor[15-i]; //factorから大きな数字から割っていく、cellはvalと同じ
			key %= factor[15-i]; //factorの除算の余りをkeyへ
		}
		for(int i=15;i>=0;i--){
			for(int j=i+1;j<16;j++){
				if(cell[i] <= cell[j]) cell[j]++;
			}
		}
		//hashしたkeyを与えると、（valをcellに戻す）、初期値であるcellが得られるdehashである
		return new field(cell, key);
	}



	//4*4のフィールドの、移動できる範囲
	//move[i][LEFT]:左に動けるか(0,1)
	//move[i][RIGHT]:右に動けるか(0,1)
	//move[i][UP]:上に動けるか(0,1)
	//move[i][DOWN]:下に動けるか(0,1)
	static boolean[][] move = new boolean[16][4];

	public static void main(String[] args){

		//移動可能方向の設定部分

		//移動できる方向に各セルに対して設定する
		//右に動けるかどうかを指定
		move[0][RIGHT]=move[1][RIGHT]=move[2][RIGHT]=move[4][RIGHT]=move[5][RIGHT]=move[6][RIGHT]=move[8][RIGHT]=move[9][RIGHT]=move[10][RIGHT]=move[12][RIGHT]=move[13][RIGHT]=move[14][RIGHT]=true;
		move[3][RIGHT]=move[7][RIGHT]=move[11][RIGHT]=move[15][RIGHT]=false;


		//左に動けるかどうかを指定
		move[1][LEFT]=move[2][LEFT]=move[3][LEFT]=move[5][LEFT]=move[6][LEFT]=move[7][LEFT]=move[9][LEFT]=move[10][LEFT]=move[11][LEFT]=move[13][LEFT]=move[14][LEFT]=move[15][LEFT]=true;
		move[0][LEFT]=move[4][LEFT]=move[8][LEFT]=move[12][LEFT]=false;

		//上に動けるかどうかを指定
		move[0][UP]=move[1][UP]=move[2][UP]=move[3][UP]=false;
		move[4][UP]=move[5][UP]=move[6][UP]=move[7][UP]=move[8][UP]=move[9][UP]=move[10][UP]=move[11][UP]=move[12][UP]=move[13][UP]=move[14][UP]=move[15][UP]=true;

		//下に動けるかどうかを指定
		move[12][DOWN]=move[13][DOWN]=move[14][DOWN]=move[15][DOWN]=false;
		move[0][DOWN]=move[1][DOWN]=move[2][DOWN]=move[3][DOWN]=move[4][DOWN]=move[5][DOWN]=move[6][DOWN]=move[7][DOWN]=move[8][DOWN]=move[9][DOWN]=move[10][DOWN]=move[11][DOWN]=true;


		//初期配置の設定部分
		//初期配置
		field st;
		int[] cell = new int[16];

		Scanner scan = new Scanner(System.in).useDelimiter("[\\s]+");
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
				cell[4*i+j] = scan.nextInt();
		//for文で繰り返しでcell入力

		st = new field(cell, hashkey(cell)); //推定距離（推定コスト）とハッシュキーをフィールドに持たせる

		//ハッシュテーブル
		boolean[] visited = new boolean[990000];
		for(int i=0;i<362880;i++)
			visited[i] = false;
		//visited[i]を未訪問にする

		//探索部分

		//ソートリストを設定
		ev_list list = new ev_list();
		list.insert(new ev_list(st)); //リストにフィールドを挿入する
		visited[hashkey(cell)] = true; //ハッシュキーのテーブルをtrueにする

		field cur;
		int hash;
		int count=0;
		while( (cur=list.pop() )!= null){
			count++; //探索回数を1増やす


			for(int i=0;i<16;i++){
				if(cur.cell[i]==0){ //curはカレントフィールド、cell[i]が0の時
					if(move[i][LEFT]){ //左に動けるなら、左と交換
						cur.cell[i]=cur.cell[i-1];
						cur.cell[i-1]=0;
						hash=hashkey(cur.cell); //hashkeyを生成
						if(!visited[hash]){ //hashkeyを訪れていないなら
							visited[hash]=true;
							list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
						}
						cur.cell[i-1]=cur.cell[i]; //元に戻す
						cur.cell[i]=0;
					}

					if(move[i][RIGHT]){
						cur.cell[i]=cur.cell[i+1];
						cur.cell[i+1]=0;
						hash=hashkey(cur.cell);
						if(!visited[hash]){
							visited[hash]=true;
							list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
						}
						cur.cell[i+1]=cur.cell[i];
						cur.cell[i]=0;
					}

					if(move[i][UP]){
						cur.cell[i]=cur.cell[i-4];
						cur.cell[i-4]=0;
						hash=hashkey(cur.cell);
						if(!visited[hash]){
							visited[hash]=true;
							list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
						}
						cur.cell[i-4]=cur.cell[i];
						cur.cell[i]=0;
					}

					if(move[i][DOWN]){
						cur.cell[i]=cur.cell[i+4];
						cur.cell[i+4]=0;
						hash=hashkey(cur.cell);
						if(!visited[hash]){
							visited[hash]=true;
							list.insert(new ev_list(new field(cur.cell, cur.route, hash) ));
						}
						cur.cell[i+4]=cur.cell[i];
						cur.cell[i]=0;
					}
				}
			}

			if(cur.evaluation==0){ //推定コストが0になった時
				System.out.println(cur.route.length-1); //cur.routeの長さ-1を出力する
				//System.out.println(count+"");
				//System.out.println("evaluation[ " +0+ " ]=" + dehash(cur.route[0]).evaluation + "\n" + dehash(cur.route[0]) );
				//evaluation推定コスト、cur.route[0]初期ハッシュキーのtoString()
				//for(int i=1;i<cur.route.length;i++){
					//System.out.println("↓");
					//System.out.println("evaluation[ " +i+ " ]=" + dehash(cur.route[i]).evaluation);
					//System.out.println("evaluation + floor[ " +i+ " ]=" + (dehash(cur.route[i]).evaluation + i) );
					//evaluation推定コスト、floor移動距離
					//System.out.println( dehash(cur.route[i]).toString() );
				//}
				break;
			}
		}
	}
}

###試したこと

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

Answer 1

A*アルゴリズムでは、このようなパズルは解けません。

wikipediaによるとA*アルゴリズムは、

グラフ上でスタートからゴールまでの道を見つける

ということなので、0が2回同じフィールドを通ることを想定していません。
実装でいうとvisited[hash]がそれにあたるかと思います。

おそらくですが、
以下の5手詰めですら結果が出ません。
1 2 3 4
5 6 8 11
9 10 7 0
13 14 15 12

あと、「無応答」ではなく、
「何も表示されずに終了する」だと思います。

Comments

[gyro16]

そういうこともあるんですね。
A*アルゴリズムは直線的なんですね。
解説ありがとうございました。

Answer 2

すいません、私もコードをよく追っていないのでピント外れかもしれませんが、コード自体は8パズル版を単純に15パズル版に拡張したのですよね?そしてA*法で解く...というのは各盤面の状態をノードとみなし、初期状態から完成状態への経路を探索するアプローチでしょうか。となると、ノードの数が階乗のオーダーで増加し、まともに解けなくなる可能性はないでしょうか。アプローチの見直しが必要かもしれません。

Answer 3

今回の件とは関係ないかもしれませんが念のため。

15パズルには絶対に解くことが出来ない配置が存在します。
解く事が出来ない⇒無限ループ、となっている可能性があります。

Answer 4

Google 先生に尋ねると、確かに 15パズルを A* アルゴリズムで解くというサイトがヒットしますね。
それを参考にされたのでしょうか。
ちらりと見たところでは、手数が多くなるほどに盤面パターンが爆発するので、メモリ不足に陥るようですが。

ちなみに15パズルの場合、あらゆる可能な盤面には1枚ずつ動かしたとしても最短で80手まででたどり着くことが証明されています（複数枚を一度に動かしてよいなら43手まで）。
※つまりどれだけ複雑な盤面であっても、最適手を取れば80手までで正しく戻せる

Answer 5

の28手詰めの15パズルを与えると、ArrayIndexOfBoundsExceptionが発生したので、

ハッシュテーブルを
boolean[] visited = new boolean[990000];
にして解消しますと、無応答になります。
解消できませんか？

プログラムが動かないととき、その原因を把握せずにあてずっぽうで手を加えて動かそうとしているような印象を持ちます。もしそうならそれは正しい対処とは言えないと思います。

まずはArrayIndexOfBoundsExceptionがどこで何故発生したのかを調べ、その原因を把握した上で対処を考えるのが自然な問題解消法だと思います。

---

「無応答」になる原因はおそらく無限ループなのではないかと思えますがコードを見てませんのでわかりません・・・余計なお世話ではありますが、自分は質問者さんご自身でなんらかのデバッグをした結果が明記されていない場合、代わりにデバッグする気にはなかなかなれません。もしデバッグされているのでしたらその結果を書かないのは不合理ですよ？それが書かれていさえすれば、回答者にとっても原因がつかみやすくなり、それだけ原因のヒントが得られる可能性が上がるのですから。