Java Acht-Damen-Problem

[The_Dentist]

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:

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

[Mikesch01]

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:

[Belur]

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:

[The_Dentist]

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 <.<

[Belur]

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();
    } 


[The_Dentist]

Originally Posted by Belur

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:

 Spoiler

	public static boolean loese (int x) {
		int y;
		if (x==8){
			number++;
			System.out.println(number);
			[COLOR="Red"]return true;[/COLOR]
		} 		
		else{
		for (y=0;y<8;y++) {
			feld [x] = y; 
			if (zulaessig(x))
				if(loese (x+1)) [COLOR="red"]return true;[/COLOR]
		}	
	}
	[COLOR="red"]return false;[/COLOR]
	}

[Belur]

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.