Java Acht-Damen-Problem

12/07/2014 16:39 The_Dentist#1
Hallo,

ich habe ein Problem mit einer Aufgabe, die uns im Studiengang Informatik gestellt wurde:

Es geht um das Acht-Damen-Problem und wir haben in der Vorlesung folgende Methode zur Lösung geschrieben:

Code:
public static boolean loese (int x) {
		if (x==8) return true; 
		for (int y=0;y<8;y++) {
			feld [x] = y;
			if (zulaessig(x))
					if (loese (x+1)) return true;
		}
	
		return false;  
}
Es geht jetzt darum, die Methode so abzuändern, dass er alle Möglichkeiten zählt, welche die Damen annehmen können, ohne sich gegenseitig schlagen zu können.

Meine Überlegung ist die Folgende: Soblad x = 8 wird, habe ich ja im Prinzip alle 8 Damen gesetzt, d.h. ich habe bereits eine Lösung gefunden und kann den Zähler um eins erhöhen.

Jetzt muss ich diese Lösung irgendwie ausschließen und eine neuen Versuch starten.

Und dabei komme ich nicht weiter. Könnte mir dabei Jemand helfen?

Vielen Dank.

LG
The_Dentist
12/07/2014 17:14 Mikesch01#2
Hallo,

das hatten wir auch vor kurzem gehabt. Das Verfahren nennt sich Backtracking.

Es wird so lange die Figur zurückgesetzt, bis sich die nächste nicht mehr schlagen kann.

Hierzu ein Link, den ich durch Google gefunden habe: [Only registered and activated users can see links. Click Here To Register...]
12/07/2014 17:36 Belur#3
Mussten das letztens auch programmieren in C.
Habs mal nach Java umgeschrieben.

Die Methode die du erweitern sollst, wird in etwa so aussehen:
PHP Code:
void setze (int n) {
    int i;
    if (n==8) {
        ausgabe();
    } else
        for (i=0; i<8; i++) {
            if (!bedroht(i,n)) {
                brett[n]=i;
                setze (n+1);
            }
        }
} 
Das ist genau dieses Backtracking wovon mein Vorposter sprach.
Jetzt brauchste nur noch eine Methode "bedroht" die prüft, ob eine Dame "geschlagen" werden kann.

Am Ende kriegste dann alle 92 Lösungen.
Hab mir noch eine Ausgabe Methode geschrieben, sodass das dann so aussieht:
[Only registered and activated users can see links. Click Here To Register...]
12/07/2014 17:50 The_Dentist#4
Perfekt, vielen Dank! Jetzt habe ich es auch geschafft, jetzt würde mich nur noch interessieren, wie Du diese Darstellung so hinbekommen hast.

Du übergibst deiner Methode ausgabe() ja keinen Wert.

€dit: Ich sehe gerade, die wollen einen boolean Rückgabewert bei der Methode. Damit ist es mir immer noch nicht ganz klar, wie das dann funktionieren soll <.<
12/07/2014 17:58 Belur#5
Kannste ja schnell abändern:
PHP Code:
public boolean setze (int n) {
    int i;
    if (n==8) {
        return true;
        //ausgabe();
    } else
        for (i=0; i<8; i++) {
            if (!bedroht(i,n)) {
                brett[n]=i;
                if(setze (n+1)){
                return true;
               }
;
            }
        }
} 
Meine Ausgabe sieht so aus:
PHP Code:
public void ausgabe() {
        System.out.println("Loesung Nummer:" + loesung);
        loesung++;
        int i, j;
        System.out.println();
        for (i = 0; i < 8; i++) {
            System.out.print(" |");
            for (j = 0; j < 8; j++)
                if (j == brett[i])
                    System.out.print("D|");
                else
                    System.out.print(" |");
            System.out.println();
        }
        System.out.println();
        System.out.println();
    } 
12/07/2014 18:03 The_Dentist#6
Quote:
Originally Posted by Belur View Post
Kannste ja schnell abändern:
PHP Code:
public boolean setze (int n) {
    int i;
    if (n==8) {
        return true;
        //ausgabe();
    } else
        for (i=0; i<8; i++) {
            if (!bedroht(i,n)) {
                brett[n]=i;
                if(setze (n+1)){
                return true;
               }
;
            }
        }
} 
^Genau, das ist das Problem, da er dann sofort abbricht, wenn er eine Lösung gefunden hat.

Mein Code sieht jetzt wie folgt aus:
12/07/2014 18:22 Belur#7
Ja dieser Teil ist Quatsch:

PHP Code:
if(loese (x+1)) [COLOR="red"]return true;[/COLOR] 
Mach die if-Bedingung darum weg. So wie ich in meinem ersten Beispiel.