Damenproblem Java

[Gast KnapsackSolver]

Hallo Community,

ich habe angefangen mich etwas mit Algorithmik zu beschäftigen und bin nachdem ich die Türme von Hanoi/Fib. Zahlen erledigt habe auf folgende Aufgabe gesoßen:

Das Damenproblem. Es gibt ein Array [8][8] und dieses repräsentiert ein Schachbrett! Nun sollen auf diesem Schachbrett 8 Damen (Schachfiguren) platziert werden und zwar so, dass Sie sich gegenseitig nicht schlagen können. Also keine Diagonale, Wagrechte oder Senkrechte Übereinstimmung!

Ich stehe hierzu etwas auf dem Schlauch, folgenden Code habe ich im Moment geschrieben:

Die Problematik liegt nur noch in der Methode, loeseDamenProblem, ich habe jedoch keinen Schimmer, wieso es mit dem rekursiven Ansatz nicht richtig funktioniert!

Danke für die Hilfe!

import AlgoTools.IO;


public class Damenproblem {


	static int counter = 0;


	private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			return true;

		} else {

			for (int i = 0; i < brett.length; i++) {

				for (int j = 0; j < brett[i].length; j++) {

					if (feldOkay(brett, i, j)) {

						brett[i][j] = true;

						loeseDamenProblem(brett, fehlendeDamen-1);

					} else {

						brett[i][j] = false;

					}

				}

			}

			return false;

		}


	}



	private static boolean feldOkay(boolean[][] brett, int zeile, int spalte) {

		// teste ob eine Dame in derselben Spalte oder Zeile gibt

		for (int i = 0; i < brett.length; i++) {

			if (brett[zeile][i] || brett[i][spalte]) {

				return false;

			}

		}

		// teste Diagonale nach rechts unten

		for (int z = zeile + 1, s = spalte + 1; z < brett.length

				&& s < brett.length; z++, s++) {


			if (brett[z][s])

				return false;


		}

		// teste Diagonale nach links oben

		for (int z = zeile - 1, s = spalte - 1; z >= 0 && s >= 0; z--, s--) {


			if (brett[z][s])

				return false;


		}

		// teste Diagonale nach links unten

		for (int z = zeile + 1, s = spalte - 1; z < brett.length && s >= 0; z++, s--) {


			if (brett[z][s])

				return false;


		}

		// teste Diagonale nach rechts oben

		for (int z = zeile - 1, s = spalte + 1; z >= 0 && s < brett.length; z--, s++) {


			if (brett[z][s])

				return false;

		}

		// wenn nirgendwo in der Zeile, Spalte oder den Diagonalen eine Dame

		// gefunden, ist das Feld gueltig.

		return true;

	}


	public static void gibErgebnisAus(boolean[][] brett) {


		// Ausgabe als Schachbrett-Visualisierung

		IO.print("   ");

		for (int j = 0; j < brett.length; j++) {

			IO.print(((char) ('a' + j)) + " ");

		}


		IO.println();


		IO.print("  ");

		for (int j = 0; j < brett.length; j++) {

			IO.print("+");

			IO.print("-");

		}


		IO.println("+");


		for (int i = 0; i < brett.length; i++) {

			IO.print((8 - i) + " ");

			for (int j = 0; j < brett[i].length; j++) {

				IO.print("|");

				IO.print(brett[i][j] ? "D" : " ");

			}

			IO.println("|");

			IO.print("  ");

			for (int j = 0; j < brett[i].length; j++) {

				IO.print("+");

				IO.print("-");

			}

			IO.println("+");

		}


		IO.print("\n\n");


		// Ausgabe als Liste

		int ausgaben = 0;

		for (int zeile = 0; zeile < brett.length; zeile++) {

			for (int spalte = 0; spalte < brett[zeile].length; spalte++) {


				if (brett[zeile][spalte]) {

					IO.print(((char) ('a' + spalte)) + "" + (8 - zeile));

					ausgaben++;


					// Komma beim letzten Element auslassen

					if (ausgaben < brett.length) {

						IO.print(",");

					}

				}


			}

		}


		IO.println(); // Zeilumbruch am Ende


	}


	public static void main(String[] args) {


		// Initialisiere und deklariere Spielfeld

		boolean[][] brett = new boolean[8][8];


		// versuche Damenproblem zu lösen

		if (loeseDamenProblem(brett, 8)) {

			gibErgebnisAus(brett);

		} else {

			IO.println("Eine Lösung konnte nicht gefunden werden. Das Damenproblem für die Kantelänge 8 ist aber lösbar, was bedeutet, dass Ihr Algorithmus noch nicht richtig funktioniert.");

		}

	}

}

[mfk'); DROP TABLE Users;--]

Du wirfst das Ergebnis des rekursiven Aufrufs weg, und gibst statt dessen immer false zurück.

[flashpixx]

https://flashpixx.de/2012/07/damenproblem/

[Gast KnapsackSolver]

Du wirfst das Ergebnis des rekursiven Aufrufs weg, und gibst statt dessen immer false zurück.

Wie muss ich es denn ansonsten anstellen?

[Gast KnapsackSolver]

Du wirfst das Ergebnis des rekursiven Aufrufs weg, und gibst statt dessen immer false zurück.

Wie muss ich es denn ansonsten anstellen?

Edit: Also ich wäre um genaue Code-Vorschläge dankbar, stehe komplett auf dem Schlauch!

private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			return true;

		} else {

			for (int zeile = 0; zeile < brett.length; zeile++) {

				for (int spalte = 0; spalte < brett[zeile].length; spalte++) {

					if(feldOkay(brett, zeile, spalte)){

						brett[zeile][spalte]=true;

						if(!loeseDamenProblem(brett, fehlendeDamen-1)){

							loeseDamenProblem(brett, fehlendeDamen);

						}

						gibErgebnisAus(brett);

					}else{

						brett[zeile][spalte]=false;

					}

				}

			}

			return false;

		}


	}

[mfk'); DROP TABLE Users;--]

Wenn dir der rekursive Aufruf true liefert, musst du sofort true zurückgeben, denn dann hast du eine Lösung gefunden. Das Ergebnis musst du nur nach oben durchreichen. Bei false suchst du weiter wie gehabt.

Zumindest, wenn es dir nur darum geht, irgendeine Lösung zu finden.

[Gast KnapsackSolver]

Als Beispiel? Sorry bin gerade echt bisschen zu dumm dazu...

[mfk'); DROP TABLE Users;--]

if(loeseDamenProblem(brett, fehlendeDamen-1))

    return true;

[Gast KnapsackSolver]

if(loeseDamenProblem(brett, fehlendeDamen-1))

    return true;

Das macht ja aber kein Sinn, dann ist die Rekursion ja schon beendet... Also ganz konkret, wenn ich deine Lösung einfüge mfk, erhalte ich folgenden Code?!

private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			return true;

		} else {

			for (int zeile = 0; zeile < brett.length; zeile++) {

				for (int spalte = 0; spalte < brett[zeile].length; spalte++) {

					if(feldOkay(brett, zeile, spalte)){

						brett[zeile][spalte]=true;

						if(loeseDamenProblem(brett, fehlendeDamen-1)){

							return true;

						}

						gibErgebnisAus(brett);

					}else{

						brett[zeile][spalte]=false;

					}

				}

			}

			return false;

		}


	}

Anschließend ist ja schon nach einem Durchlauf alles zu ende...

[mfk'); DROP TABLE Users;--]

Das macht ja aber kein Sinn, dann ist die Rekursion ja schon beendet...

Deswegen meine Anmerkung, ob die Aufgabe ist, einfach nur irgendeine Lösung zu finden. Dann kannst du aufhören zu suchen, wenn du eine gefunden hast. Nur dann ergibt der Rückgabetyp boolean einen Sinn.

Was soll der Rückgabewert denn aussagen?

Wenn es dir darum geht, alle Lösungen zu finden, musst du natürlich weiter suchen.

Die Ausgabe gehört aber auf jeden Fall in die unterste Ebene der Rekursion.

[Gast KnapsackSolver]

Ja also ich will mit diesem Grundgerüst 8 Damen auf dem Feld platzieren. Wie kann ich das lösen?

[mfk'); DROP TABLE Users;--]

Es gibt mehr als eine Möglichkeit, 8 Damen auf einem 8x8-Brett zu platzieren.

Willst du irgendeine Lösung, oder alle?

[sas86ks]

Schau dir doch mal flashpixxs Beitrag an.

[Gast KnapsackSolver]

Es gibt mehr als eine Möglichkeit, 8 Damen auf einem 8x8-Brett zu platzieren.

Willst du irgendeine Lösung, oder alle?

Ich möchte irgendeine Lösung, also damit ichs dann nachvollziehen kann!

[mfk'); DROP TABLE Users;--]

Ich möchte irgendeine Lösung, also damit ichs dann nachvollziehen kann!

Ich meinte nicht eine Lösung des Programmierproblems, sondern eine Lösung des 8-Damen-Problems.

Es gibt über 90 Stellungen mit 8 Damen, wenn ich mich richtig erinnere. Soll dein Programm alle anzeigen, oder nur irgendeine?

[Gast KnapsackSolver]

Ich meinte nicht eine Lösung des Programmierproblems, sondern eine Lösung des 8-Damen-Problems.

Es gibt über 90 Stellungen mit 8 Damen, wenn ich mich richtig erinnere. Soll dein Programm alle anzeigen, oder nur irgendeine?

Irgendeine! Ich möchte nur eine Lösungsmöglichkeit, also 1 Stellung für die Damen haben!

[mfk'); DROP TABLE Users;--]

private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			gibErgebnisAus(brett);

			return true;

		} else {

			for (int zeile = 0; zeile < brett.length; zeile++) {

				for (int spalte = 0; spalte < brett[zeile].length; spalte++) {

					if(feldOkay(brett, zeile, spalte)){

						brett[zeile][spalte]=true;

						if(loeseDamenProblem(brett, fehlendeDamen-1)){

							return true;

						}

					}else{

						brett[zeile][spalte]=false;

					}

				}

			}

			return false;

		}


	}

[Gast KnapsackSolver]

private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			gibErgebnisAus(brett);

			return true;

		} else {

			for (int zeile = 0; zeile < brett.length; zeile++) {

				for (int spalte = 0; spalte < brett[zeile].length; spalte++) {

					if(feldOkay(brett, zeile, spalte)){

						brett[zeile][spalte]=true;

						if(loeseDamenProblem(brett, fehlendeDamen-1)){

							return true;

						}

					}else{

						brett[zeile][spalte]=false;

					}

				}

			}

			return false;

		}


	}

Das tut nicht, hast du es mal mit dem vorherigen Code-Konstukt ausprobiert?

[mfk'); DROP TABLE Users;--]

Das tut nicht

Super Fehlerbeschreibung!

hast du es mal mit dem vorherigen Code-Konstukt ausprobiert?

Ich habe das gar nicht ausprobiert, weil ich hier keine Möglichkeit habe, Java-Code zu kompilieren.

[mfk'); DROP TABLE Users;--]

Jetzt aber:

private static boolean loeseDamenProblem(boolean[][] brett,int fehlendeDamen) {

		if (fehlendeDamen == 0) {

			gibErgebnisAus(brett);

			return true;

		} else {

			for (int zeile = 0; zeile < brett.length; zeile++) {

				for (int spalte = 0; spalte < brett[zeile].length; spalte++) {

					if(feldOkay(brett, zeile, spalte)){

						brett[zeile][spalte]=true;

						if(loeseDamenProblem(brett, fehlendeDamen-1))

							return true;

						brett[zeile][spalte]=false;

					}

				}

			}

			return false;

		}


	}

[flashpixx]

Sorry, aber dieser Array-Käse bringt rein gar nichts und ist auch nicht wirklich OOP Struktur. Ich habe das ganze einmal anfänger-verständlich in meinem Beitrag (https://flashpixx.de/2012/07/damenproblem/) formuliert. Man sollte schon mal in den Algorithmus etwas Arbeit stecken, denn Damenproblem ist NP-hart, d.h. "durchprobieren von Lösungen ist bei vielen Damen nicht mehr möglich".

[mfk'); DROP TABLE Users;--]

Sorry, aber

dieser Array-Käse bringt rein gar nichts

Es funktioniert, oder?

und ist auch nicht wirklich OOP Struktur.

War das denn gefordert?

Ich habe das ganze einmal anfänger-verständlich in meinem Beitrag (https://flashpixx.de/2012/07/damenproblem/) formuliert.

Verständlich für Uni-Anfänger in MINT-Fächern vielleicht. Außerdem wollte dieser Anfänger wissen, warum sein Code nicht funktioniert. Da hilft ihm das Vorbeten einer perfekten Lösung wenig.

Man sollte schon mal in den Algorithmus etwas Arbeit stecken, denn Damenproblem ist NP-hart, d.h. "durchprobieren von Lösungen ist bei vielen Damen nicht mehr möglich".

Ist hier irgendwo die Rede davon, dass das für eine anderes N als 8 gelöst werden soll? Natürlich kann man jedes Problem beliebig kompliziert machen, wenn man unnötig verallgemeinert.

xkcd: The General Problem

[flashpixx]

War das denn gefordert?

Java impliziert als OOP-Sprache OOP Strukturen. Wenn man eine solcheSprache verwendet, dann sollte man sich im Klaren darüber sein, was dies bedeutet.

Verständlich für Uni-Anfänger in MINT-Fächern vielleicht. Außerdem wollte dieser Anfänger wissen, warum sein Code nicht funktioniert. Da hilft ihm das Vorbeten einer perfekten Lösung wenig.

Es geht darum, dass man überlegt wie ein Problem zu lösen ist, nicht wie man Code-Fixing betreibt. Coding ist der letzte Schritt im Rahmen einer Problemlösung. Man muss zuerst einmal verstehen was Backtracking ist und wie es funktioniert und das kann man auf einem Blatt Papier. Der OP hat das Prinzip von Backtracking nicht verstanden und darum läuft sein Code nicht. Backtracking ist wiederum nur eine Lösungsmöglichkeit von vielen, somit ist die Frage "Ist Backtracking für die Problemlösung ein angemessenes Verfahren" das was man zuerst stellen muss. Um diese Frage beantworten zu können, muss ich erst einmal das Problem verstanden haben.

Ist hier irgendwo die Rede davon, dass das für eine anderes N als 8 gelöst werden soll? Natürlich kann man jedes Problem beliebig kompliziert machen, wenn man unnötig verallgemeinert.

Hier wurde in der Diskussion ein Heftpflaster dem OP auf sein Problem geklebt. Die Problematik hat er nicht verstanden, warum man die Möglichkeiten "durchprobieren" muss, auch nicht. Guter Code / Struktur hat er auch nicht gelernt. Somit wurde hier sich keine Zeit genommen das Problem gut zu erklären und damit bleibt ein Lerneffekt aus.

In dem Artikel den ich gepostet habe, ist beschrieben warum ich zu dieser Lösung komme und was die Idee dieser Lösung ist. In einem Lernprozess ist absolut nicht hilfreich einfach bei Problemen diese zu Lösen. Dem OP ging es um Nachvollziehbarkeit:

Ich möchte irgendeine Lösung, also damit ichs dann nachvollziehen kann!

Im Grunde wäre es hier der bessere Weg erst einmal gewesen das Problem zu analysieren und dann zu schauen warum ist der OP auf den geposteten Code gekommen und warum sind dann Probleme entstanden. Lernen funktioniert nicht, wenn man Lösungen vorgibt, sondern nur dann wenn der Lernende nachvollziehen kann, welche Schritt zur Lösungsfindung notwendig sind und wie man auf diese kommt. Zusätzlich muss er lernen, warum eben manche Wege nicht zielführend sind.

@mfk: Bevor Du hier also die Kritik ansprichst, bitte mal den Lernprozess überdenken...

[mfk'); DROP TABLE Users;--]

Java impliziert als OOP-Sprache OOP Strukturen.

Nö. Man kann in Java auch prima prozedural programmieren.

Es geht darum, dass man überlegt wie ein Problem zu lösen ist, nicht wie man Code-Fixing betreibt. Coding ist der letzte Schritt im Rahmen einer Problemlösung. Man muss zuerst einmal verstehen was Backtracking ist und wie es funktioniert und das kann man auf einem Blatt Papier. Der OP hat das Prinzip von Backtracking nicht verstanden und darum läuft sein Code nicht. Backtracking ist wiederum nur eine Lösungsmöglichkeit von vielen, somit ist die Frage "Ist Backtracking für die Problemlösung ein angemessenes Verfahren" das was man zuerst stellen muss. Um diese Frage beantworten zu können, muss ich erst einmal das Problem verstanden haben.

Man kann auch so viele Schritte zurück machen, dass man das Problem nicht mehr sieht. Ich stelle mir gerade einen Maurerlehrling vor, der als Antwort auf die Frage, warum sein Mörtel nicht abbindet, vom Meister erst einmal in Statik- und Materialwissenschaften-Vorlesungen geschickt wird. Ist der verwendete Mörtel hier überhaupt der richtige? Was ist Mörtel eigentlich, was passiert chemisch beim Abbinden, welche Scherkräfte wirken usw.

Hier wurde in der Diskussion ein Heftpflaster dem OP auf sein Problem geklebt.

Das hängt davon ab, wie man das Problem definiert.

In dem Artikel den ich gepostet habe, ist beschrieben warum ich zu dieser Lösung komme und was die Idee dieser Lösung ist. In einem Lernprozess ist absolut nicht hilfreich einfach bei Problemen diese zu Lösen.

Glaubst du wirklich, dass der OP deine Ausführungen versteht? Ich glaube, ein durchschnittlicher Programmieranfänger hört nach dem ersten Absatz auf zu lesen, weil er nur noch Bahnhof versteht. Spätestens bei den Funktionsgleichungen ist Schluss.

Ich halte deine Lösung für hoffnungslos over-engineered. Eine Punkt-Klasse? Gibt's das in Java nicht schon?

Lernen funktioniert nicht, wenn man Lösungen vorgibt, sondern nur dann wenn der Lernende nachvollziehen kann, welche Schritt zur Lösungsfindung notwendig sind und wie man auf diese kommt.

Ich habe eine Lösung vorgegeben, als mir klar wurde, dass der OP selbst meine deutlichsten Hinweise nicht umzusetzen in der Lage war. Du hast gleich zu Anfang eine OOP-geblähte Komplettlösung nebst unverständlicher Erklärung hingesetzt, die der OP im besten Fall abgeschrieben, aber keinesfalls verstanden hätte.

Und dabei bist du in keiner Weise auf seinen Code eingegangen. Das wirkt wie "Was du machst, ist alles Käse, wirf das weg, und programmier so, wie ich es für richtig halte". Welche Auswirkung auf den Lernprozess das wohl hat?

Bearbeitet 21. November 2014 von mfk

[Heikooo]

Nö. Man kann in Java auch prima prozedural programmieren.

Man kann auch so viele Schritte zurück machen, dass man das Problem nicht mehr sieht. Ich stelle mir gerade einen Maurerlehrling vor, der als Antwort auf die Frage, warum sein Mörtel nicht abbindet, vom Meister erst einmal in Statik- und Materialwissenschaften-Vorlesungen geschickt wird. Ist der verwendete Mörtel hier überhaupt der richtige? Was ist Mörtel eigentlich, was passiert chemisch beim Abbinden, welche Scherkräfte wirken usw.

Das hängt davon ab, wie man das Problem definiert.

Glaubst du wirklich, dass der OP deine Ausführungen versteht? Ich glaube, ein durchschnittlicher Programmieranfänger hört nach dem ersten Absatz auf zu lesen, weil er nur noch Bahnhof versteht. Spätestens bei den Funktionsgleichungen ist Schluss.

Ich halte deine Lösung für hoffnungslos over-engineered. Eine Punkt-Klasse? Gibt's das in Java nicht schon?

Ich habe eine Lösung vorgegeben, als mir klar wurde, dass der OP selbst meine deutlichsten Hinweise nicht umzusetzen in der Lage war. Du hast gleich zu Anfang eine OOP-geblähte Komplettlösung nebst unverständlicher Erklärung hingesetzt, die der OP im besten Fall abgeschrieben, aber keinesfalls verstanden hätte.

Und dabei bist du in keiner Weise auf seinen Code eingegangen. Das wirkt wie "Was du machst, ist alles Käse, wirf das weg, und programmier so, wie ich es für richtig halte". Welche Auswirkung auf den Lernprozess das wohl hat?

Koooorekt Ich kann zwar auch flashpixx verstehen was den Lernprozess angeht, jedoch sind beide Wege Zielführend da auch scheitern hilft