Acht-Damenproblem

[ElifÖzt]

Hi Leute, ich habe wieder das Problem, dass ich meine Gedanken nicht zu Code bringen kann.
Ich habe dieses Problem auch schon gegoogelt und versucht aus den Codes von anderen Schlüsse zu ziehen, doch komme trotzdem nicht voran. (Bin noch Anfänger und muss mir dieses Code/Algorithmus-Denken noch etwas aneignen)

Ich habe ein Schachbrett (8x8) und muss darauf 8 Damen so platzieren, dass sie sich weder vertikal, noch horizontal, noch diagonal bedrohen.

Mein bisheriger Quellcode:

public class Queens {
    private int [] conf;
    int zaehler;
    int keineDame = -1;
   
    public Queens() {
        this.conf = new int[] {0, 1, 2, 3, 4, 5, 6, 7};
    }
    //läuft Array conf ab und gibt es dann aus
    public void printConf(){
        for(int i = 0; i<conf.length; i++){
            System.out.print(conf[i] + " ");
        }
    }
    //läuft bis i durch und schaut ob conf[i] bedroht ist
    //wenn auf gleicher Zeile, gleicher Spalte und gleicher Diagonale keine Dame steht gib true zurück
    public boolean threatened(int i, int j){
        for (int k = 0; k<i; k++){
            int d = i-k;
            if(conf[i]==j || conf[i]==j-d || conf[i]==j+d) {
                return true;
            }
        }
        return false;
    }
    //place belegt das nicht bedrohte Feld mit einer Dame
    //läuft Array ab und wenn ein Platz nicht bedroht ist, wird an die Stelle eine Dame gesetzt
    public void place(int i){
        for(int s=0; s<conf.length ; s++){
            if(!threatened(i, s)){
                this.conf[s]=i;
                if(i==conf.length-1){
                    printConf();
                    zaehler++;
                }
                else{
                    place(i+1);
                    }
            }
        }
    }
   
    public static void main(String[] args){
        Queens a = new Queens();
        //a.printConf();
        a.place(1);
    }
}

Ich finde meinen Fehler nicht und ich glaube ich habe auch ein Problem beim allgemeinen Verständnis des Algorithmus.
Ich hoffe ihr könnt mir weiterhelfen.
LG ElifÖzt

 

[stg]

Das Problem ist ein typisches Beispiel für Back-Tracking. Ich sehe dich aber nirgends "falsche Züge" zurücksetzen.
Außerdem findest du bei deiner Startkonfiguration schon für die erste Dame kein Feld mehr, auf welches du sie setzen kannst. Du solltest mit einem leeren Spielbrett starten.

 

[ElifÖzt]

Wie setze ich denn "falsche Züge" zurück?
Soll ich also beim Array erst mal alles 0 machen oder wie?

 

[JBelarbi]

Hi, ich brauche alle klassen was du geschrieben hast und die Aufgaben Stellung.

 

[ElifÖzt]

Das ist der komplette Code, was ich habe und die genaue Aufgabenstellung lautet:

In dieser Aufgabe soll ein Java-Programm implementiert werden, das alle Lösungen
des Damenproblems mit acht Damen ermittelt. Sie konnen sich dabei an dem in der
Vorlesung vorgestellten Pseudocode orientieren. Eine Platzierung wird durch ein Array
aus acht Ganzzahlen dargestellt. Jedes Array-Element steht dabei fur eine Zeile des
Schachbretts. Der Wert des Array-Elements bezeichnet die Spalte in der die Dame
dieser Zeile zu nden ist. Beachten Sie, dass bei Arrays die Zahlung bei 0 beginnt und
die Zeilen- und Spaltenindizes deshalb Zahlen von 0 bis 7 sind. Die beiden Beispiel-
Kongurationen, die auf Vorlesungsfolie 4.7-4 dargestellt sind, entsprechen den Werten
2, 5, 7, 0, 3, 6, 4, 1 (links) und 3, 5, 7, 1, 6, 0, 2, 4 (rechts).
Aufgabe 2 a)
Erstellen Sie zunachst eine Klasse namens Queens. Sie soll ein Array namens conf aus
acht Ganzzahlen als Attribut haben, welches im Konstruktor erzeugt wird. Fugen Sie
der Klasse eine main-Methode hinzu, die ein Queens-Objekt erzeugt. Die Klasse soll
auerdem eine Methode printConf() besitzen, die die Array-Elemente ausgibt.
Aufgabe 2 b)
Implementieren Sie nun eine Methode boolean threatened(int i, int j), die uberpr
uft, ob das Feld in Zeile i und Spalte j von einer Dame bedroht wird. Ist das Feld
bedroht, soll sie true, andernfalls false zuruckgeben. Zum Uberprufen verwendet die
Methode die aktuelle Platzierung der Damen, die im Array conf gespeichert ist. Auf
Grund der funktionsweise des Pseudocodes in der Vorlesung mussen nur die Damen
oberhalb der Zeile i uberpruft werden, d.h. die Damen in den Zeilen mit einem Index
strikt kleiner als i. Testen Sie Ihre Methode auf Korrektheit fur verschiedene Kongurationen
bevor Sie mit der nachsten Teilaufgabe fortfahren.
Aufgabe 2 c)
Implementieren Sie nun die Methode place(int i) so wie auf Folie 4.7-9 in Pseudocode
vorgegeben. Beachten Sie, dass die for-Schleife angepasst werden muss. Zur
Uberprufung der Bedrohung soll die Methode threatened verwendet werden. Platzieren
einer Dame entspricht einer Zuweisung desWerts h an das Array-Element mit Index
i. Das Brett ist voll, wenn die unterste Dame platziert wurde. Die Ausgabe der Konfiguration
erfolgt durch printConf(). Fugen Sie Ihrer main-Methode den Aufruf place(0)
hinzu. Wenn Sie alles richtig gemacht haben, sollte der Aufruf 92 verschiedene, korrekte
Konfigurationen ausgeben.