|
import java.applet.Applet;
import java.awt.*;
public class New extends Applet
{
boolean found = false;
int ninepos,rowpos,colpos=0;
List H,A;
TextField t1,t2;
char chkeep[];
int parents[][];
int pcount = 0;
int inlist[];
int collist[];
int colcount;
String goal="";
String heap[];
int hcount;
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);
H = new List(12,false); add(H);
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;
heap= new String[5000];
hcount=1;
}
public boolean action(Event e, Object o)
{
heap[1]=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)
{
System.out.println("in handle " + parent + " " + 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)
{
if (s==null) {System.out.println(hcount);return 0;}
//System.out.println("Hstring" + 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)
{
hcount++;
heap[hcount] = s;
System.out.println("Hval is " + heuristic(s) + " " + s + " " + hcount);
if (hcount>1)
{
boolean done = false;
int val =hcount;
while (!done )
{
if (heuristic(heap[val]) > heuristic(heap[val/2]))
{
String temp = heap[val];
heap[val] = heap[val/2];
heap[val/2]=temp;
val = val/2;
}
else done = true;
if (val < 2 ) done = true;
} // end of while
System.out.println("top of heap is" + heap[1]+ " " + heuristic(heap[1]));
} //end of if count > 1
} // end of addHeap
String removeHeap()
{
String returnValue = heap[1];
if (hcount==1)
{ hcount=0;
H.addItem(returnValue);
return returnValue;
}
System.out.println("in remHeap"+ " " + heuristic(returnValue));
H.addItem(returnValue);
heap[1]=heap[hcount];
hcount--;
int max = hcount;
boolean exit = false;
int bigChild=0;
int val = 1;
String rightChild = "000000000";
String leftChild =heap[val*2];
if (max> 1) rightChild = heap[val*2+1];
if (heuristic(leftChild) > heuristic(rightChild))
bigChild = heuristic(leftChild);
else bigChild = heuristic(rightChild);
while (!exit)
{
if (bigChild > heuristic(heap[val]))
{
if (bigChild == heuristic(leftChild))
{
String temp = heap[val];
heap[val]=heap[val*2];
heap[val*2]=temp;
}
else
{
String temp = heap[val];
heap[val]=heap[val*2+1];
heap[val*2+1]=temp;
}
val = val*2;
}
else exit = true;
if (val*2 <= hcount)
{
leftChild =heap[val*2];
if (val*2+1 <= max) rightChild = heap[val*2+1];
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
|
