横型探索（８パズル）

/*********************************/
/* 横型探索（８パズル）          */
/*           coded by Y.Suganuma */
/*********************************/
import java.io.*;
import java.util.*;

class Depth
{
	int dep;
	String prev;
	Depth (String str, int dep1)
	{
		prev = str;   // 前の状態
		dep  = dep1;   // 深さ
	}
}

class Pair
{
	String str;
	int dep;
	Pair (String str1, int dep1)
	{
		str = str1;   // 状態
		dep = dep1;   // 深さ
	}
}

class Search
{
	/********************************/
	/* コマの移動                   */
	/*      str : 現在の状態        */
	/*      res : 移動後の状態      */
	/*      return : 移動後の状態数 */
	/********************************/
	int move(String str, String res[])
	{
		int k, n = 0;
		String str1;
		char c[] = new char [2];

		k = str.indexOf('0');
		switch(k) {
			case 0:
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 1:
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 2:
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 3:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 4:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 5:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+3,k+4).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 6:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 7:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k+1,k+2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
			case 8:
				c      = str.substring(k-3,k-2).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				c      = str.substring(k-1,k).toCharArray();
				str1   = str.replace('0', '9');
				str1   = str1.replace(c[0],'0');
				str1   = str1.replace('9', c[0]);
				res[n] = str1;
				n++;
				break;
		}

		return n;
	}

	/*************************/
	/* 横型探索（８パズル）  */
	/*      start : 初期状態 */
	/*      goal : 目標状態  */
	/*************************/
	void width(String start, String goal)
	{
		int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1;
		char at[] = new char [10];
		String str = "", res[] = new String [4];
		Pair pair;
		ArrayDeque <Pair> q = new ArrayDeque <Pair> ();
		TreeMap<String, Depth> m = new TreeMap<String, Depth> ();

		m.put(start, new Depth("",dep));
		q.add(new Pair(start, dep));
		while (!q.isEmpty()) {
			pair = q.pollFirst();
			str  = pair.str;
			dep  = pair.dep;
			node2++;
					// ゴール
			if (str.compareTo(goal) == 0) {
				ct = dep;
				break;
			}
					// ゴールでない
					// コマを移動し，同じ状態のものがなければキューに追加
			else {
				n = move(str, res);
				for (i1 = 0; i1 < n; i1++) {
					if (!m.containsKey(res[i1])) {
						m.put(res[i1], new Depth(str,dep+1));
						q.add(new Pair(res[i1], dep+1));
						node1++;
					}
				}
			}
		}
					// 結果の出力
		System.out.printf("   展開とチェック： %d %d，　最短距離： %d\n", node1, node2, ct);
		while (str.length() > 0) {
			at = str.toCharArray();
			System.out.printf("\n      %c %c %c\n", at[0], at[1], at[2]);
			System.out.printf("      %c %c %c\n", at[3], at[4], at[5]);
			System.out.printf("      %c %c %c\n", at[6], at[7], at[8]);
			str = m.ceilingEntry(str).getValue().prev;
		}
	}
}

public class Test
{
	public static void main (String[] args)
	{
		String goal = "123804765";
		Search ss = new Search();

		System.out.printf("例１\n");
		String start = "283164705";
		ss.width(start, goal);

		System.out.printf("例２\n");
		start = "216408753";
		ss.width(start, goal);
	}
}