[Java] n-Damenproblem (rekursiv)

O

Orniflyer

0
Ich steh gerade aufm Schlauch :wall:

Das n-Damenproblem besagt das auf einem (Schach-)Feld der Größe n*n bis zu n Damen so positioniert werden können das sie sich gegenseitig nicht schlagen können.

Um eine Lösung zu generieren habe ich folgende rekursive Methode geschrieben. Wobei n die feldgröße sowie anzahl der damen beschreibt und das schachfeld als bitfeld, in form eines 2-dim. booleanschen arrays mit dimensionsgrößen n, beschrieben wird. Die Methode dame_erlaubt gibt ihrem namen entsprechend zurück ob eine dame an der stelle x,y erlaubt ist.

Code: 
  public static boolean dame_setzen(int zeile) {

    boolean erlaubt = true;

    for (int i=0; i<n; i++) {
        if (dame_erlaubt(i,zeile) == true) {
          feld[i][zeile] = true;
          if (zeile+1 != n) {          
            dame_setzen(zeile+1);
            if (dame_setzen(zeile+1) == false) feld[i][zeile] = false;
          } else {
            int damenanzahl = 0;
            for (int j=0; j<n; j++) {
              for (int k=0; k<n; k++) {
                if (feld[k][j] == true) damenanzahl++;
              }
            }             
            if (damenanzahl != n) erlaubt = false;
          }
        }
    }
    return erlaubt;
  }
Zwar läuft das alles schön durch, aber gibt erzeugt ein falsches Feld. Für n=8 sieht das Bitfeld danach so aus:

Code: 
   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---+---+---+---+---+---+---+---+---+
 1 | D |   |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 2 |   | D |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   | D |   |   |   |
---+---+---+---+---+---+---+---+---+
 4 |   |   | D |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 5 |   |   |   |   |   | D |   |   |
---+---+---+---+---+---+---+---+---+
 6 |   |   |   | D |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 
Wenn ich es richtig verstehe, nutzt Du ein globales Array. Daher machen mich folgende Zeilen stutzig:
Code: 
if (zeile+1 != n) {          
            dame_setzen(zeile+1);
            if (dame_setzen(zeile+1) == false) feld[i][zeile] = false;
denn beim ersten Aufruf setzt Du quasi eine Dame in diese Zeile - und kannst beim zweiten Aufruf wohl kaum nochmal eine Dame in der selben Zeile platzieren, so dass es immer false ergeben dürfte. Machst aber mit "feld[zeile] = false;" nur die aktuelle Platzierung rückgängig - ergo bleiben die anderen Platzierungen erhalten.

Btw: diese C-like Klammerung finde ich persönlich sehr unübersichtlich. Wenn ich deswegen nichts übersehe ;) , returt die Methode nach "feld[zeile]=false" trotzdem ein erlaubt==true. Zusammen damit, dass nicht jeder Schritt rückgängig gemacht wird, ergibt sich wohl solch eine "komische" Ausgabe.
 
So, habe das mal übersichtlicher geklammert :)
Code: 
public static boolean dame_setzen(int zeile) 
{
    boolean erlaubt = true;

    for (int i=0; i<n; i++) 
    {
        if (dame_erlaubt(i,zeile) == true) 
        {
          feld[i][zeile] = true;
          if (zeile+1 != n) 
          {          
            if (dame_setzen(zeile+1) == false) feld[i][zeile] = false;
          } else 
          {
            int damenanzahl = 0;
            for (int j=0; j<n; j++) 
            {
              for (int k=0; k<n; k++) 
              {
                if (feld[k][j] == true) damenanzahl++;
              }
            }             
            if (damenanzahl != n) erlaubt = false;
          }
        }
    }
    return erlaubt;
}
Nun: von der Logik her setzt Du eine Dame hier:
Code: 
if (dame_erlaubt(i,zeile) == true) 
        {
          feld[i][zeile] = true;
danach wird geprüft, ob eine Dame in der nächsten Zeile gesetzt werden kann. Falls es nicht geht, müsste die Platzierung in der aktuellen Zeile auch falsch sein. Sie wird entfernt:
Code: 
 if (dame_setzen(zeile+1) == false) feld[i][zeile] = false;
Das ganze wird für die ganzen Spalten in der aktuellen Zeile probiert - allerdings wird trotzdem ein true zurückgegeben, auch wenn man wegen der aktuellen Konfiguration letzendlich keine Dame in der aktuellen Zeile positionieren konnte.

Setzt doch mal den Defaultwert für erlaubt=false und ändere ihn zu true erst dann, wenn alles "ok" ist.
 
Danke :rolleyes:
Es läuft jetzt:

Code: 
   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---+---+---+---+---+---+---+---+---+
 1 | D |   |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   | D |   |
---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   | D |   |   |   |
---+---+---+---+---+---+---+---+---+
 4 |   |   |   |   |   |   |   | D |
---+---+---+---+---+---+---+---+---+
 5 |   | D |   |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 6 |   |   |   | D |   |   |   |   |
---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   | D |   |   |
---+---+---+---+---+---+---+---+---+
 8 |   |   | D |   |   |   |   |   |
---+---+---+---+---+---+---+---+---+
Allerdings verstehe ich beim besten Willen nicht woran es gelegen hat, der code schaut jetzt so aus:

Code: 
  public static boolean dame_setzen(int zeile) {

    boolean erlaubt = false;

    for (int i=0; i<n; i++) {
        if (dame_erlaubt(i,zeile) == true) {
          feld[i][zeile] = true;
          if (zeile+1 != n) {          
            if (dame_setzen(zeile+1) == false) {
              feld[i][zeile] = false;
            } else {
              erlaubt = true;
            }
          } else {
            int damenanzahl = 0;
            for (int j=0; j<n; j++) {
              for (int k=0; k<n; k++) {
                if (feld[k][j] == true) damenanzahl++;
              }
            }             
            if (damenanzahl == n) erlaubt = true;
          }
        }
    }
    return erlaubt;
  }

Rein sinngemäß ist es das Selbe ... >.<
Wenn jemand den "Punkt" findet wodurch es nun funktioniert so soll er's mir bitte zeigen. Ich würd schon gern wissen welchen Fehler ich drin hatte.
 
Code

Hallo Orniflyer,
könntest du mir den kompletten Code zusenden?
Finde deine Lösung im Gegensatz zu meiner sehr einfach.
Ich komme leider mit nicht weiter

Vielen Dank im Voraus

Alexander
 
Zuletzt bearbeitet:
Frage

Noch eine Lösung zum DamenProblem:
/**
* @author Sebastian Schmitt
*
* Das Programm errechnet, wie auf einem nxn Schachfeld n Damen aufgestellt werden<br>
* koennen, so dass sie sich nicht gegenseitig schlagen.
*/

package Aufgabe03;

public class Schachspiel {

/**
* @param args
* Kommandozeilenparameter
*/
public static void main(String[] args) {
int n = 24; // nxn Schachfeld, n Damen
int[] a = new int[n];
setzeDame(a, 0);
}

/**
*
* @param a
* array
* @param n
* zeile
*/
static void setzeDame(int[] a, int n) {// n= jeweilige Zeile

if (n == a.length) { // wenn n den Wert a.length erhällt, sind alle
int z = 1; // Damen korrekt gesetzt!
for (int x : a)
System.out.println("in reihe " + z++ + ", pos:" + (x + 1));
System.exit(-1);
}

else {
for (int i = 0; i < a.length; i++) {// durchlauft alle felder einer
// Zeile
if (n == 0) { // fuer die erste Zeile
a[0] = n;
setzeDame(a, n + 1);
}
int x = 0;
for (int j = 0; j < n; j++) { // durchlauft alle Zeilen
// kleiner als aktuelle Zeile
if (a[j] != i) // alle zeilen vorher muessen andere Werte haben
if (a[j] != i + (n - j)) // diagonale pruefen, rechts
if (a[j] != i - (n - j))// diagonale pruefen, links
x++; // wenn alles zutrifft, erhoehe x
}
if (x == n) {// wenn x fuer alle zeilen erhoeht wurde, setze
a[n] = i; // Dame und mach weiter in nächster Zeile
setzeDame(a, n + 1);
/*
* sollte dieser rekursive Aufruf nicht zum Ergebniss führen,
* wird die schleife (mit j) weitergeführt ...
*/
}
}
}
}
}
Aber was ich nicht verstehe ist, welche Funktion System.exit(-1) hat?
Wenn ich es lösche, bekomme ich alle Ergebnisse aufgelistet, und nur das letzte ist richtig.

Danke
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben