# Java Backtracking Spiel-Reise



## javajedi (21. Sep 2010)

Hi,
ich muss für die Schule ein Backtracking Programm schreiben, dass das Spiel ,,Reise" (kürzesten Weg von A nach B suchen) implementiert.

Bis jetzt habe ich zwar ein Programm, dieses funktioniert aber nur mit der Klasse ,,Graph". Siehe hier:


```
public class Graph
  {

     private  List myGraph;            //Liste von GraphNodes;


     public Graph()
     {
        myGraph = new List();
     }

     public void insertNode (String pName)
     {
       GraphNode node = new GraphNode(pName);
       myGraph.insertBehind(node);
     }

       public List nodes ()
     {
       return myGraph;
     }
     
     public void connectNodes (String pName1, String pName2, double pWeight)
     {
       GraphNode node1 = searchNode(pName1);
       GraphNode node2 = searchNode(pName2);

       Edge edge1 = new Edge (node1, pWeight);
       node2.insertEdge(edge1);
                   //Einfügen von edge1 in die Kantenliste von GraphNode node2

       Edge edge2 = new Edge (node2, pWeight);
       node1.insertEdge(edge2);
                  //Einfügen von edge2 in die Kantenliste von GraphNode node1
     }


     public GraphNode searchNode (String pName)
     {
           if(myGraph.isEmpty()== false)
          {
             myGraph.toFirst();

             while(!(((GraphNode)myGraph.getItem()).name().equals(pName)))
             {
               myGraph.next();
               if(myGraph.isBehind()==true)
               {
                 return null;
               }

             }
             return (GraphNode)myGraph.getItem();

          }
          return null;
     }



      public boolean track(GraphNode pStart, GraphNode pGoal)
  {
    List yourList = pStart.edges();
    boolean a = false;
    if(!yourList.isEmpty())
    {
      yourList.toFirst();
      while(!yourList.isBehind())
      {
        if(pGoal.name().equals(((Edge)yourList.getItem()).neighbour().name()))
        {
          return true;
        }
        else
        {
         if( (((Edge) yourList.getItem()).neighbour()).isMarked()==false)
         {
           (((Edge) yourList.getItem()).neighbour()).mark();

           a = track( ((Edge)yourList.getItem()).neighbour(),pGoal);
         }
           if (a==true)
         {
             return true;
         }
        }
        yourList.next();
      }
      return false;
    }
    return false;
  }

  }
```



Ich soll es aber wie bei unserem 8-Damen Programm machen, was wir bekommen haben. Siehe hier:


```
public class Search 
{
   private int dim = 8;
   private MainWindow mainWindow; // Fenster fuer Ausgabe
   private boolean[][] belegt; // gibt an, ob auf Feld x,y eine Dame steht


   public Search( MainWindow win )
   {
      mainWindow = win;
      // Thread starten
   }
    

   // Hauptfunktion des Threads

   public void sucheNext()   // Muss unbedingt public sein !!!
   {
      erfolgreich = false;
      belegt = new boolean[dim][dim]; // Arrays initialisieren
      for (int x=0; x<dim; x++)
      {
         for (int y=0; y<dim; y++)
              belegt[x][y] = false;
      }
      recSearch(0);       // Suche starten
   }

   // rekursive Suche Backtracking
   private boolean erfolgreich = false;
    
   private void recSearch(int spalte)
   {
      int zeile = -1;
      while (zeile < dim-1 && !erfolgreich)
      //weitere wahl möglich und noch nicht erfolgreich
      {
         zeile++;
         if (isFieldOk (spalte, zeile))
         //wahl annehmbar
         {
            setQueen (spalte, zeile);
            //lösungsversuch aufzeichnen
            if (spalte < dim-1)
            //weitere wahl möglich
            {
               recSearch (spalte + 1);
               //rekursiver aufruf auf tieferer stufe: trial
               if (!erfolgreich)
               // kein erfolg auf tieferer stufe: error
                  clearQueen (spalte, zeile);
                  //rücknahme des lösungsversuches
            }
            else
            //keine weitere wahl möglich, also lösung gefunden
            {
               erfolgreich = true;
            }

         }
      }
   }

   // Test, ob auf Feld x,y eine Dame platziert werden darf
   boolean isFieldOk(int x, int y)
   {
      int zaehler = 0;
      while (zaehler<=x)
      {
         if (belegt[x][zaehler] || belegt[zaehler][y])
           return false;   // Bedrohung senkrecht bzw. waagerecht
         if (y-(x-zaehler)>=0 && y-(x-zaehler)<dim)
           if (belegt[zaehler][y-(x-zaehler)])
             return false; // Bedrohung diagonal von links oben
         if  (y+(x-zaehler)<dim && y+(x-zaehler)>=0)
           if (belegt[zaehler][y+(x-zaehler)])
             return false; // Bedrohung diagonal von links unten
         zaehler++;
      }
      return true; // keine Bedrohung gefunden, Feld erlaubt
   }

   // Dame auf Feld setzen und Array anpassen
   void setQueen( int x, int y )
   {
      if (!belegt[x][y])
      {
         belegt[x][y] = true;
         mainWindow.setQueen(x ,y); // Grafik-Ausgabe
      }
   }

   // Dame von Feld entfernen und Array anpassen
   void clearQueen(int x, int y)
   {
      if (belegt[x][y])
      {
         belegt[x][y] = false;
         mainWindow.clearQueen(x ,y); // Grafik-Ausgabe
      }
   }
}
```


Wenn ihr mir helfen könntet wäre ich euch sehr verbunden.

mfg


----------



## SlaterB (21. Sep 2010)

deinem Programm fehlt eine main-Methode mit einem Test-Graphen
addNode(A);
addNode(B);
addNode(C);
addNode(D);
verbindeNode(A,B,20);
verbindeNode(B,C,40);
usw.
wie testet du überhaupt dein Programm? jeder andere kann es im Moment jedenfalls nicht

ganz grob sieht deine track()-Methode nach Rekursion und dann doch sicher nach Backtracking aus, was gibt es sonst?
beschreibe in Worten was sie macht, inwiefern denkst du dass das den 8-Damen wiederspricht?

---
nebenbei:
hier ist fast zeitgleich dasselbe 8-Damen-Programm mit einer anderen Aufgabe gepostet, große Klasse? 
http://www.java-forum.org/hausaufgaben/106155-backtracking.html


----------



## javajedi (24. Sep 2010)

Hi,
erstmal vielen dank für deine antwort.

Im grunde ist der Graph ja auch Backtracking, aber da wir die Klasse Graph noch nicht hatten, nur die LK Leute, darf ich nur ,,einfache" Methoden verwenden, wie beim 8 Damen Problem.

Ich kann euch ja mal das ganze Programm (Reise) reinstellen.

File-Upload.net - Edge.java

File-Upload.net - Element.java

File-Upload.net - Graph.java

File-Upload.net - GraphGUI.java

File-Upload.net - GraphNode.java

File-Upload.net - List.java


Hier das 8 Damen Problem:

File-Upload.net - Search.java

File-Upload.net - AchtDamen.java

File-Upload.net - MainWindow.java


----------



## SlaterB (24. Sep 2010)

wenn überhaupt, musst du ein Zip aller Dateien erstellen, sonst lädt das ja niemand herunter,
bevor ich mir die Mühe mache hätte ich aber gerne erst noch Erklärungen, Antworten zu meinen Fragen

mit 'ich weiß von nix, bitte das Programm so (um- oder neu-)schreiben dass es die Aufgabe korrekt erfüllt' bin ich nicht motiviert


edit:
ich sehe jetzt was du mit 'nicht Graph' meinst, wobei ich bezweifle, dass eine solche schöne Unterstützungsklasse verboten ist,
alternativ musst du Arrays anlegen oder Listen der verknüpften Elemente, und die dann durchlaufen,

das wäre natürlich schon heftige Umbau-Arbeit, hast du genau nachgefragt ob eine derart saubere passende Graph-Klasse verboten ist?


----------

