/*********************************/
/* 知識を用いた探索（８パズル） */
/* coded by Y.Suganuma */
/*********************************/
import java.io.*;
import java.util.*;
class Depth
{
int dep, est;
String prev;
Depth (String str, int dep1, int est1)
{
prev = str; // 前の状態
dep = dep1; // 深さ
est = est1; // 評価値
}
}
class Node
{
int dep, est;
String str;
Node (String str1, int dep1, int est1)
{
str = str1; // 状態
dep = dep1; // 深さ
est = est1; // 評価値
}
}
class Comp implements Comparator <Node> {
public int compare (Node n1, Node n2)
{
int sw = 0;
if (n1.est == n2.est) {
if (n1.dep == n2.dep)
sw = n1.str.compareTo(n2.str);
else
sw = n1.dep - n2.dep;
}
else
sw = n1.est - n2.est;
return sw;
}
}
class Search
{
/************************/
/* ノードの評価 */
/* dep : 深さ */
/* str : 状態 */
/* goal : 目標状態 */
/* return : 評価値 */
/************************/
int estimation(int dep, String str, String goal)
{
int i1, i2, i3, i4, k1, k2, pi = dep, sw;
char at[], cg[][] = new char [3][3], cn[][] = new char [3][3];
at = goal.toCharArray();
for (i1 = 0; i1 < 9; i1++) {
k1 = i1 / 3;
k2 = i1 - 3 * k1;
cg[k1][k2] = (char)(at[i1] - '0');
}
at = str.toCharArray();
for (i1 = 0; i1 < 9; i1++) {
k1 = i1 / 3;
k2 = i1 - 3 * k1;
cn[k1][k2] = (char)(at[i1] - '0');
}
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
sw = 1;
for (i3 = 0; i3 < 3 && sw > 0; i3++) {
for (i4 = 0; i4 < 3 && sw > 0; i4++) {
if (cg[i3][i4] == cn[i1][i2]) {
sw = 0;
pi += (Math.abs(i3-i1) + Math.abs(i4-i2));
}
}
}
}
}
if (cn[1][1] != '0')
pi++;
if (cn[0][1] != (cn[0][0]+1)%9)
pi += 2;
if (cn[0][2] != (cn[0][1]+1)%9)
pi += 2;
if (cn[1][2] != (cn[0][2]+1)%9)
pi += 2;
if (cn[2][2] != (cn[1][2]+1)%9)
pi += 2;
if (cn[2][1] != (cn[2][2]+1)%9)
pi += 2;
if (cn[2][0] != (cn[2][1]+1)%9)
pi += 2;
if (cn[1][0] != (cn[2][0]+1)%9)
pi += 2;
if (cn[0][0] != (cn[1][0]+1)%9)
pi += 2;
return pi;
}
/********************************/
/* コマの移動 */
/* 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 intel(String start, String goal)
{
int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1, est;
char at[] = new char [10];
boolean sw;
String str = "", res[] = new String [4];
Node nd;
Comparator<Node> cp = new Comp();
PriorityQueue <Node> p = new PriorityQueue <Node> (1, cp);
TreeMap<String, Depth> m = new TreeMap<String, Depth> ();
est = estimation(dep, start, goal);
m.put(start, new Depth("",dep,est));
p.add(new Node(start, dep, est));
while (!p.isEmpty()) {
nd = p.poll();
str = nd.str;
dep = nd.dep;
node2++;
// ゴール
if (str.compareTo(goal) == 0) {
ct = dep;
break;
}
// ゴールでない
// コマを移動し，同じ状態のものがなければキューに追加
else {
n = move(str, res);
for (i1 = 0; i1 < n; i1++) {
sw = true;
est = estimation(dep+1, res[i1], goal);
if (m.containsKey(res[i1])) {
if (est < m.ceilingEntry(res[i1]).getValue().est)
m.remove(res[i1]);
else
sw = false;
}
if (sw) {
m.put(res[i1], new Depth(str,dep+1,est));
p.add(new Node(res[i1], dep+1, est));
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.intel(start, goal);
System.out.printf("例２\n");
start = "216408753";
ss.intel(start, goal);
}
}