# Backtracking



## momba (21. Sep 2010)

Hallo liebe community, 
ich muss ein Programm für den Informatik-GK an meiner Schule programmieren. 

Die Aufgabe lautet : "Gesucht ist eine Zahl - bestehend aus den Ziffern 1-9, bei der die Zahl, die aus den ersten i Ziffern gebildet werden kann, und durch i teilbar ist (i = 1-9)"

Diese Aufgabe soll mit Hilfe eines Backtracking Algorithmus programmiert werden. Als Grundlage haben wir von unserem Lehrer ein Backtracking Programm zum 8-Damen Problem erhalten :


```
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
      }
   }
}
```

Ich bin der totale Trottel, wenn es sich um Java handelt. Für schnelle Hilfe wäre ich sehr dankbar.

MfG momba


----------



## Final_Striker (21. Sep 2010)

Und was war jetzt deine Frage?


----------



## MiDniGG (21. Sep 2010)

Besser: Wie viel zahlst Du? Und, warum steht der Thread nicht in der Jobbörse?!


----------



## javajedi (24. Sep 2010)

Ich mache den Job für nen 100er.


----------



## SlaterB (24. Sep 2010)

ich schreib solche Abkürzungen ja nie, aber: LOL

du hast ein eigenes exakt gleiches Problem
http://www.java-forum.org/spiele-multimedia-programmierung/106154-java-backtracking-spiel-reise.html
(auch mit Vorlage der 8-Damen-Klasse)
welches du selber kaum lösen kannst und andere nach kostenloser Hilfe fragst,
und für jemand anders glaubst du dann a) das machen zu können (?) und b) willst Geld dafür?!

na klasse, mal sehen ob ich dir in dem anderen Thema noch weiterhelfen kann/ will


----------



## Tomate_Salat (24. Sep 2010)

:lol: javajedi == Developer_x 2.0?

- lässt es sich von anderen machen 
- verkauft dann deren Lösung (Erhältlich ab version 2.0.0_alpha)


----------

