Jump to content
Gast KnapsackSolver

Damenproblem Java

Empfohlene Beiträge

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.");

		}

	}

}

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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?

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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;

		}


	}

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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...

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
Gast KnapsackSolver

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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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!

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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?

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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!

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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;

		}


	}

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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?

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

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;

		}


	}

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
Sorry, aber
:rolleyes:

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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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 von mfk

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
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 ;)

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

Nimm an der Diskussion teil

Du kannst jetzt hier posten und Dich später registrieren. Wenn Du bereits über eine Konto verfügst, melde Dich jetzt an, um mit Deinem Konto zu posten.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung jetzt entfernen

  Only 75 emoji are allowed.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Clear editor

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.


Fachinformatiker.de, 2020 SE Internet Services

fidelogo_small.png

if_icon-6-mail-envelope-closed_314900.pnSchicken Sie uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App


Get it on Google Play

Kontakt

Hier werben?
Oder senden Sie eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung