|
import java.applet.Applet;
import java.awt.*;
public class New extends Applet
{
boolean found = false;
int ninepos,rowpos,colpos=0;
List Q,H,P,A;
TextField t1,t2;
char chkeep[];
int parents[][];
int pcount = 0;
int inlist[];
int collist[];
int colcount;
String goal="";
public void init()
{
Label lab1 = new Label("enter start"); add(lab1);
t1 = new TextField(50); add(t1);
Label lab2 = new Label("enter goal"); add(lab2);
t2 = new TextField(50); add(t2);
Q = new List(12,false); add(Q);
H = new List(12,false); add(H);
P = new List(12,false); add(P);
A = new List(12,false); add(A);
parents = new int[50000][2];
inlist = new int[178361];
for (int x = 0; x < 178361; x++)
inlist[x] = -1;
collist = new int[500];
colcount = 0;
}
public boolean action(Event e, Object o)
{
Q.addItem(t1.getText());
goal = t2.getText();
while (!found)
{
expand(removeHeap());
}
return true;
}
public void expand(String s)
{
for (int x=0;x<9;x++)
if (s.charAt(x)=='9') ninepos = x;
rowpos = ninepos / 3;
colpos = ninepos % 3;
if (rowpos>0)
{
char ch[]=s.toCharArray();
char tmp = ch[ninepos];
ch[ninepos] = ch[ninepos-3];
ch[ninepos-3] = tmp;
String stmp = String.copyValueOf(ch);
handleNewNode(s,stmp);
}
if (rowpos<2)
{
char ch[]=s.toCharArray();
char tmp = ch[ninepos];
ch[ninepos] = ch[ninepos+3];
ch[ninepos+3] = tmp;
String stmp = String.copyValueOf(ch);
handleNewNode(s,stmp);
}
if (colpos>0)
{
char ch[]=s.toCharArray();
char tmp = ch[ninepos];
ch[ninepos] = ch[ninepos-1];
ch[ninepos-1] = tmp;
String stmp = String.copyValueOf(ch);
handleNewNode(s,stmp);
}
if (colpos<2)
{
char ch[]=s.toCharArray();
char tmp = ch[ninepos];
ch[ninepos] = ch[ninepos+1];
ch[ninepos+1] = tmp;
String stmp = String.copyValueOf(ch);
handleNewNode(s,stmp);
}
} // end of expand methos
void handleNewNode(String parent, String child)
{
if (notInList2(child)) addHeap(child);
P.addItem(parent + " " + child);
pcount++;
parents[pcount][0] = Integer.parseInt(parent);
parents[pcount][1] = Integer.parseInt(child);
if (t2.getText().equals(child))
{
found = true;
findPath(child);
}
}
boolean notInList(String t)
{
boolean f = true;
for(int x=0; x<H.getItemCount();x++)
{
if (t.equals(H.getItem(x)))
f = false;
}
return f;
}
boolean notInList2(String t)
{
int hashval = Integer.parseInt(t) % 178361;
if (inlist[hashval] < 0)
{
inlist[hashval]= Integer.parseInt(t);
return true;
}
else
{
if (inlist[hashval] == Integer.parseInt(t))
return false;
else
{
for (int x = 0; x < colcount; x++)
if (Integer.parseInt(t)== collist[colcount])
return false;
collist[colcount] = Integer.parseInt(t);
// System.out.println(hashval + "." + t + " " + inlist[hashval]+ " " + inlist[hashval] % 178361 + " "+ collist[colcount] + " " + colcount);
colcount++;
return true;
}
}
}
void findPath(String s)
{
A.addItem(s + " " + String.valueOf(pcount));
while (!s.equals(t1.getText()))
{
while (parents[pcount][1]!=Integer.parseInt(s))
pcount--;
s = String.valueOf(parents[pcount][0]);
A.addItem(s + " " + String.valueOf(pcount));
}
}
int heuristic(String s)
{
int val = 0;
for (int x=0;x<9;x++)
if (goal.charAt(x)==s.charAt(x))
val = val+1;
return val;
}
void addHeap(String s)
{
Q.addItem(s);
System.out.println("Hval is " + heuristic(s) + " " + s);
if (Q.getItemCount()>1)
{
boolean done = false;
int val =Q.getItemCount();
while (!done )
{
if (heuristic(Q.getItem(val-1)) > heuristic(Q.getItem(val/2-1)))
{
String temp = Q.getItem(val-1);
Q.replaceItem(Q.getItem(val/2-1),val-1);
Q.replaceItem(temp,val/2-1);
val = val/2;
}
else done = true;
if (val < 2 ) done = true;
} // end of while
} //end of if count > 1
} // end of addHeap
String removeHeap()
{
int max = Q.getItemCount();
String returnValue = (Q.getItem(0));
if (max==1) return returnValue;
System.out.println("in remHeap" + returnValue + " " + heuristic(returnValue));
H.addItem(returnValue);
Q.replaceItem(Q.getItem(max-1),0);
Q.remove(max-1);
max = max-1;
boolean exit = false;
int bigChild=0;
int val = 1;
String rightChild = "000000000";
String leftChild =Q.getItem(val*2-1);
if (max> 2) rightChild = Q.getItem(val*2);
if (heuristic(leftChild) > heuristic(rightChild))
bigChild = heuristic(leftChild);
else bigChild = heuristic(rightChild);
while (!exit)
{
if (bigChild > heuristic(Q.getItem(val-1)))
{
if (bigChild == heuristic(leftChild))
{
String temp = Q.getItem(val-1);
Q.replaceItem(Q.getItem(val*2-1),val-1);
Q.replaceItem(temp,val*2-1);
}
else
{
String temp = Q.getItem(val-1);
Q.replaceItem(Q.getItem(val*2),val-1);
Q.replaceItem(temp,val*2);
}
val = val*2;
}
else exit = true;
if (val*2 <= Q.getItemCount())
{
leftChild =Q.getItem(val*2-1);
if (val*2 != max) rightChild = Q.getItem(val*2);
else rightChild = "000000000";
if (heuristic(leftChild) > heuristic(rightChild))
bigChild = heuristic(leftChild);
else bigChild = heuristic(rightChild);
}
else exit = true;
} // end of while
return returnValue;
} // end of removeHeap
}// end of class
|
