rekursiver Methodenaufruf

[johannesK]

In meiner Aufgabe soll das N-Damenproblem (Damenproblem ? Wikipedia) spaltenweise gelöst (aufgebaut werden). Die position der Damen wird in einem int[] gespeichert.

Mein Problem ist der rekursive Aufruf der methode extend(oldBoard), die ein übergebenes board der grösse n x m mit m damen auf ein n x n board mit n damen erweitern soll.

Die Klasse Board:

public class Board {
  private final int[] board;
  private final int numberOfRows;

  public Board(int numberOfRows) {
    this(0, numberOfRows);
  }

  private Board(int numberOfColumns, int numberOfRows) {
    this.board = new int[numberOfColumns];
    this.numberOfRows = numberOfRows;
  }

  public boolean hasConflict() {
    //prüft ob in der aktuellen Belegung eine Dame eine andere bedroht
  }

  public Board newColumn(int rowPosOfQueen) {
    // fügt dem board eine neue Spalte mit einer dame an Position
    // rowPosOfQueen hinzu
    int oldLength = board.length;
    Board newBoard = new Board(oldLength + 1, numberOfRows);
    System.arraycopy(board, 0, newBoard.board, 0, oldLength);
    newBoard.board[oldLength] = rowPosOfQueen;
    return newBoard;
}

Die Klasse Queensproblem:

public class QueensProblem {
 private final int n;
 boolean conflict;

  private Board extend(Board oldBoard) {
    // erweitert das übergebene Board um eine spalte und prüft
    // ob in der neuen Belegung eine Dame eine andere bedroht. Falls
    // nicht soll durch rekuriven aufruf ein board der grösse n x n entstehen.
    // falls keine Lösung gefunden wird, soll ein leeres brett zurückgegeben 
    // werden.

    if(oldBoard.getNumberOfColumns() == n) {
      return oldBoard;
    }
    
    else { 
      int i = 0;  
      boolean solutionFound = false;
      Board extendedBoard = new Board(1); 
      while (i < n && solutionFound == false) {
        extendedBoard = oldBoard.newColumn(i);
        System.out.println(oldBoard);
        System.out.println(extendedBoard);
        boolean test = extendedBoard.hasConflict();
        if (test == true) {
          i++;
          solutionFound = false;    
        } else if (test == false && extendedBoard.getNumberOfColumns() == n) {
            solutionFound = true;  
        }
        else {
          return extend(extendedBoard);    
        }
      }
      if (i == n && solutionFound == false) {
        Board empty = new Board(n);
        return empty;   
      }
      else {
        return extendedBoard;  
      }

    } 
  }

}

Mein Programm erzeugt zb für n = 3 folgende ausgabe (" x " = damen, " . " = leeres feld) :

x
.
.

x
.
.

x x
. .
. .

x
.
.

x .
. x
. .

x
.
.

x .
. .
. x

x .
. .
. x

x . x
. . .
. x .

x .
. .
. x

x . .
. . x
. x .

x .
. .
. x

x . .
. . .
. x x


Natürlich sollte mein Programm jetzt beginnen, die erste dame nun ein feld nach unten zu setzen und dann wieder versuchen das feld aufzubauen so dass keine konflikte vorliegen (und bei 3x3 zu dem ergebnis kommen das es keine lösung gibt).

Vielen Dank für die Hilfe

Johannes

 

[Empire Phoenix]

Gut und wo ist jetzt die Frage?

 

[johannesK]

Gut und wo ist jetzt die Frage?

Die Frage ist wo mein Fehler liegt. Das Programm hat so ja nicht alle möglichen Belegungen durchgestestet.

Was muss ich umstellen damit nun (im Beispiel die dame der ersten spalte als nächstes eine zeile tiefer gesetzt wird und der rest der belegungen danach getestet wird) weiter getestet wird.

 

[SlaterB]

womit fängt das ganze an, was wird initial übergeben? wer ruft das auf?
wenn null als Startwert kommt gibts eine NPE,
wahrscheinlich wird mit new Board(1) gestartet, dann ist die erste Spalte mit der Dame ganz oben die feste Ausgangsposition,
die Rekursion arbeitet nur an neuen zweiten Spalten wie ja klar zu sehen ist,
eine Lösung wäre mit einem Board mit 0 Spalten anzufangen


------

in Zeile 19
> Board extendedBoard = new Board(1);
kannst du dir die Objekterzeugung übrigens sparen, es wird sowieso nur ein abgeleitetes Board verwendet,
schreibe
Board extendedBoard;
oder = null;

 

[johannesK]

womit fängt das ganze an, was wird initial übergeben? wer ruft das auf?

Das ganze wird folgendermassen gestartet

public Board solve() {
  return extend(new Board(n));         // n wird zuvor eingelesen (grösse des schachbretts n x n )
}

es wird also mit einem schachbrett mit n zeilen und 0 spalten begonnen und nun soll jeweils eine spalte hinzugefügt werden und getestet werden ob durch die dame in der neuen spalte ein konflikt etsteht und wenn nicht, dann soll die nächste spalte hinzugefügt werden usw......

und die erste dame soll eben keine feste ausgangsposition besitzen sondern wenn das hinzufügen weiterer spalten fehlschlägt, soll die dame in der ersten spalte in die nächste zeile rücken usw ...

 

[SlaterB]

nun, dann sehe ich es nicht direkt, dann zu den Standardmitteln:
du gibst ja schon ne Menge aus, aber das kann doch locker-locker-lockerleicht auf noch mehr Informationen ausgeweitet werden,
schreibe vor jeder Schleife etwa a la
System.out.println("vor Schleife, bisherige Spalten .."); (Spaltenanzahl zur Unterscheidung der Rekursionstiefe, aus deinen anderen Ausgaben natürlich auch zu erkennen)

zu Beginn jedes Schleifendurchlaufs steht
System.out.println("in Schleife, bisherige Spalten .., i = .. ");

nach jedem Rekursionsaufruf schreibst du
System.out.println("bin wieder in der Schleife zum Board mit Anzahl Spalten .., aktuelles i ist .., test war .., solutionFound ist daher .. ");

usw. so dass man überall erkennen kann, welche Methode in welcher Schleife steckt und wann aufhört oder auch nicht und einfach alles

 

[johannesK]

folgendes habe ich jetzt eingefügt:

  private Board extend(Board oldBoard) {
    System.out.println("Beginn der Methode extend() "); 
    if(oldBoard.getNumberOfColumns() == n) {
      return oldBoard;
    }
    
    else { 
      int i = 0;  
      boolean solutionFound = false;
      Board extendedBoard = null; 
      while (i < n && solutionFound == false) {
        System.out.println("in Schleife i =  " + i);
        extendedBoard = oldBoard.newColumn(i);
        System.out.println("Das übergebene board (oldBoard) : ");
        System.out.println(oldBoard);
        System.out.println("das extendedBoard : ");
        System.out.println(extendedBoard);
        boolean test = extendedBoard.hasConflict();
        System.out.println("konflikt in der belegung : " + extendedBoard.hasConflict());
        if (test == true) {
          i++;
          solutionFound = false;    
        } else if (test == false && extendedBoard.getNumberOfColumns() == n) {
            solutionFound = true;  
            
        }
        else {
          System.out.println("BEGINN   rekursiver Aufruf");
          return extend(extendedBoard);
        }
        System.out.println("ENDE   rekursiver Aufruf");
        System.out.println("solutionFound ist = " + solutionFound);
      }
      if (i == n && solutionFound == false) {
        Board empty = new Board(n);
        return empty;   
      }
      else {
        return extendedBoard;  
      }

    }
  
  }

}

Damit erhalte ich für n = 3 folgede ausgabe :

Programm wird ausgeführt ...
NDamen> 3
Beginn der Methode extend()

in Schleife i = 0

Das übergebene board (oldBoard) :



das extendedBoard :

*
.
.



konflikt in der belegung : false

BEGINN rekursiver Aufruf

Beginn der Methode extend()

in Schleife i = 0

Das übergebene board (oldBoard) :

*
.
.



das extendedBoard :

* *
. .
. .



konflikt in der belegung : true

ENDE rekursiver Aufruf

solutionFound ist = false

in Schleife i = 1

Das übergebene board (oldBoard) :

*
.
.



das extendedBoard :

* .
. *
. .



konflikt in der belegung : true

ENDE rekursiver Aufruf

solutionFound ist = false

in Schleife i = 2

Das übergebene board (oldBoard) :

*
.
.



das extendedBoard :

* .
. .
. *



konflikt in der belegung : false

BEGINN rekursiver Aufruf

Beginn der Methode extend()

in Schleife i = 0

Das übergebene board (oldBoard) :

* .
. .
. *



das extendedBoard :

* . *
. . .
. * .



konflikt in der belegung : true

ENDE rekursiver Aufruf

solutionFound ist = false

in Schleife i = 1

Das übergebene board (oldBoard) :

* .
. .
. *



das extendedBoard :

* . .
. . *
. * .



konflikt in der belegung : true

ENDE rekursiver Aufruf

solutionFound ist = false

in Schleife i = 2

Das übergebene board (oldBoard) :

* .
. .
. *



das extendedBoard :

* . .
. . .
. * *



konflikt in der belegung : true

ENDE rekursiver Aufruf

solutionFound ist = false




Programm beendet

 

[Empire Phoenix]

Gut aber das ergebniss ist richtig

So wie ich das sehe (vonner ausgabe nicht im code)
testet es nur sinnvolle lösungen, spriche s wird nie 3 damen in einer zeile testen, da die rekursion bereits bei 2 en vor der plazirung der dritten aufgrund von konflict zurück geht.


Im prinzip macht er soweit wie ich das denke
-> Testen von 1-n der dame x ob stellung ohne konflikt gefunden.
-> falls gefunden mit der dame x+1 weitermachen
-> falls keine stellung ohne konflikt gefunden zurück zur dame x-1
-> falls bei dame 0 und alle Stellungen von Dame 0 probiert "keine Lösung" ausgeben.
-> falls bei dame xn=max und stellung gefunden, alles als "Lösung" ausgeben.

 

[SlaterB]

schreibst du das alles nur für mich und hast selber keine Beachtung dafür?
na dann bringt das wohl nix..

aufgefallen ist mir nun noch Zeile 29:
> return extend(extendedBoard);
wenn es einmal keinen Konflikt gibt und deshalb die Rekursion gewagt wird dann ist für die aktuelle Stufe in jedem Fall absolutes Ende,
Zeile 31 dahinter
> System.out.println("ENDE rekursiver Aufruf");
ist der blanke Hohn, diese Meldung kann bei Rekusion nicht kommen, nur immer dann wenn es einen Konflikt gibt und deswegen gerade KEINEN rekursiven Aufruf!


return extend(extendedBoard);
muss jedenfalls anders werden, nach dem rekursiven Aufruf soll es in der aktuellen Stufe sicher weitergehen

 

[johannesK]

Gut aber das ergebniss ist richtig
....
-> falls keine stellung ohne konflikt gefunden zurück zur dame x-1
....

Das macht er leider gerade nicht. Der Algorithmus sollte nun nachdem die letzte Stellung folgende war:

X . .
. . .
. X X

als nächstes die dame in der ersten Spalte nach unten rücken :

.
X
.

dann neu versuchen zu lösen ....

. X
X .
. . (keine Lösung)

. .
X X
. . (keine Lösung)

. .
X .
. X (keine Lösung)

als nächstes die dame in der ersten Spalte Wieder eins nach unten rücken :

.
.
X

dann neu versuchen zu lösen ....

. X
. .
X . (Lösung)

>> gehe zur nächsten Spalte

. X X
. . .
X . . (keine Lösung)


. X .
. . X
X . . ( keine Lösung)

. X .
. . .
X . X ( keine Lösung)


>>> für n = 3 existiert keine Lösung


So sollte das Programm ablaufen!! Nur leider beendet mein Algorithmus wenn er keine Lösung findet anstatt die Dame der ersten spalte eine zeile nach unten zu setzen.

 

[SlaterB]

mein Posting gesehen?

 

[Empire Phoenix]

Müsste das Programm icht mit
.
.
.
Anfangen bzw mit garnichts statt mit
x
.
.
?? Denke da ist der Fehler

 

[SlaterB]

wer sagt dir wie die Ausgabe von 'gar nichts' bzw. einem Board mit 0 Spalten ist?

.
.
.
wird nicht zu sehen sein, denn jede neue Spalte erhält auch immer gleich eine Dame