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;

   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[5000000][2];
   }

   public boolean action(Event e, Object o)
   {
       Q.addItem(t1.getText());

       while (!found)
       {
           expand(Q.getItem(0));
           H.addItem(Q.getItem(0));
           Q.delItem(0);
       }

       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 (notInList(child)) Q.addItem(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;
   }
  
   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));
       }
   }
      
} // end of class

[Home] [Syllabus] [Sessions]