Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Ich wünsch allen hier ein besinnliches Weihnachtsfest.
Ich habe mich mit dem 8Dame Problem beschäftig und dieses über BackTracking gelöst.
In meiner Varinte macht das Programm solange weiter, bis alle Lösungen gefunden sind.
Jetzt möchte ich den Vorgang nach der z.B. ersten Lösung abbrechen.
Das eizige was mir einfällt ist einen eigenen Thread dafür zu erstellen und diese dann an
der gewünschten Stelle abzubrechen.
Oder hat jemand für mich eine bessere Lösung?
Java:
void dameSetzen(){
for (int x = 0; x < spielfeld; x++) {
if (yPosDame[x] == leer){
for (int y = 0; y < spielfeld; y++) {
if (checkPos(x,y)){
yPosDame[x] = y;
dameSetzen(); // Rekusion
}
}
yPosDame[x] = leer;
return; // BackTracking
}
}
System.out.println(Arrays.toString(yPosDame));
// Alle rekusiven Aufrufe abbrechen
}
void rekursiveLoesung(int i) {
// Abbruchbedingung
if (i >= Ende) return;
// Forward Step
// z.B. Figur setzen.
// Rekursiver Aufruf
rekursiveLoesung(i+1);
// Backward Step wenn nicht erfolgreich
// z.B. Figur wegnehmen
}
Das ist der typische Aufbau des Backtracking.
Ansonsten treibt man mich nicht so schnell in den Wahnsinn. Ich muss halt nur verstehen, wo es genau hakt.
Wir können das also auf unser Problem anwenden. Da hatten wir ja eine Lösung (Jetzt noch einen kleinen Copy-Fehler korrigiert ... stimmt jetzt hoffentlich):
Auchtung: Ich behandel zwei Dinge in dieser Antwort. Als erstes versuche ich auf Deine Frage einzugehen. Aber im Anschluss gehe ich auf die Rekursion bei Dir ein - die keine richtige Rekursive Lösung ist!
Das bedeutet, dass Du nach dem rekursiven Aufruf von dameSetzen wissen musst, ob Du weiter machen musst oder nicht.
Dazu gibt es mehrere Optionen:
Die erste Option (die ich hier nicht machen würde!) ist einfach, einen "externen" Status zu haben. Du hast eine dameSetzen Instanz-Methode, daher könntest Du eine Instanzvariable haben: boolean loesungGefunden. Am Anfang ist diese variable false. Nach dem rekursiven Aufruf prüfst Du diese Variable aber einfach und gehst ggf. zurück:
Java:
dameSetzen(); // Rekusion
if (loesungGefunden) return; // Abbruch, da Lösung gefunden
Die zweite Variante ist einfach: Das dameSetzen hat ein Ergebnis: Lösung gefunden oder eben nicht. Daher hast Du dann eine neue Signatur:
Java:
boolean dameSetzen() {
// ....
}
Und wenn die Lösung gefunden wurde, dann musst Du true zurück geben. Der Rekursive Aufruf ändert sich dann zu:
Java:
if (dameSetzen()loesungGefunden) return;
Das zweite entspricht der üblichen Vorgehensweise. Wenn man etwas mathematisch beschreibt, dann hat man ja oft etwas wie:
f(x) = 1 für x = 1 oder 2.
f(x) = f(x-1) + f(x-2) für x > 2
(mit x Element aus N).
Sprich: Du hast etwas, das ein Ergebnis liefert und damit arbeitest Du dann weiter. Du arbeitest hier mit Arrays, was den Parameter überflüssig macht. Um die Rekursion besser zu sehen, wäre denkbar, das yPosDame als Parameter zu übergeben. Das wäre ja dieser Parameter.
Und das würde dann zu der dritten Variante führen - das Ergebnis ist natürlich nicht nur ein true/false /Lösung gefunden oder nicht) sondern die Lösung selbst. Daher wäre denbar, dass man das Array mit der Lösung zurück gibt. Also eine Signatur wie:
Java:
int[] dameSetzen(int[]) {
// ....
}
und dann im Code:
Java:
int[] loesung = dameSetzen(yPosDame);
if (loesung != null) return loesung;
Und es müsste natürlich die Lösung zurück gegeben werden bzw. null wenn es keine Lösung ist.
Du der dritten Variante ist aber zu sagen, dass mir diese nicht ganz gefällt. Denn da ist zwar die Rekursion sauber heraus gearbeitet, aber man hat keine objektorientierte Lösung. Die Methode nutzt keine Instanzvariablen mehr und ist damit statisch. Das ist etwas, das ich eher ablehne. Das ist also nur gut, um eine Rekursion anschaulich zu bauen aber nicht um eine wirkliche Software zu schreiben, die ja in der Regel deutlich komplexer ist und auch immer komplexer wird.
Dann noch ein Hinweis zu Deiner Lösung:
Du hast zwar einen rekursiven Aufruf, aber die Lösung ist in erster Linie noch immer iterativ von Deinen Schleifen her. Den rekursiven Aufruf braucht es da so in der Form nicht. Die Rekursion zeichnet sich immer durch diesen Aufbau aus:
Keine Schleife bzw, eine Schleife, die sonst iterativ abgearbeitet wird, ist ersetzt durch den rekursiven Aufruf.
Es gibt eine Abbruchbedingung.
Wenn man eine iterative Lösung hat, dann kann man diese nach einem festen Schema umwandeln:
Itearive Lösung:
Java:
void iterativeLoesung() {
for (int i = 0; i < Ende; i++) {
// Whatever
}
}
Rekursive Umwandlung
Java:
void rekursiveLoesung(int i) {
// Abbruchbedingung
if (i >= Ende) return;
// Whatever
// Rekursivret Aufruf
rekursiveLoesung(i+1);
}
Was Du also brauchst ist etwas ähnliches, das deien äußere Schleife ersetzt durch eben die rekursiven Aufrufe.
Super, hab vielen Dank für die ausführliche Antwort. Die Lösung auf meine Frage konnte ich prima umsetzten. Ich werde das Programm die nächsten Tage noch mal mit einer wirklichen rekursiven Funktion überarbeiten. Ich werde hier an dieser Stelle berichten.
Um die Y-Position mit dem Backtracking zu realisieiren, komme ich um eine Schleife nicht herum, oder?
Jedenfalls konnte ich mit meinem Wissen darauf nicht verzichten.
Ansonsten habe ich deine Anmerkung umgestzt.
Amerkung:
Java:
void rekursiveLoesung(int i) {
// Abbruchbedingung
if (i >= Ende) return;
// Whatever
// Rekursivret Aufruf
rekursiveLoesung(i+1);
}
Vielleicht liege ich falsch, aber den Aufruf in Zeile 17 braucht es doch nicht, oder?
die Prüfung in Zeile 6 dürfte auch unnötig sein, denn das Array sollte komplett leer sein.
Wenn nach dem Aufruf in Zeile 12 das Ergebnis nicht ist, dass es gelöst wurde, dann ist es doch notwendig, die Dame wieder weg zu nehmen.
Java:
private boolean dameSetzen(int xPosDame) {
if (xPosDame+1 > spielfeld) return true; // Abbruch der Rekursion, alle Damen gesetzt!
for (int yPosDame = 0; yPosDame < spielfeld+1; yPosDame++) {
if (checkPos(xPosDame, yPosDame)) {
PosDame[xPosDame] = yPosDame;
boolean result = dameSetzen(xPosDame + 1);
if (resolved) return;
PosDame[xPosDame] = leer;
}
}
return false;
}
Stell es Dir doch bildlich vor:
Du hast ein Schachbrett, und Du gehst so vor:
Für die erste Spalte machst Du:
- Du gehst alle Felder der Spalte durch:
---> Du plazierst die Dame auf dem Feld.
---> Wenn das eine gültige Konstellation ist, dann machst Du bei der nächsten Spalte weiter.
---> Du nimmst die Dame weg (Klar - du willst die ja dann ggf. auf das nächste Feld stellen!)
Nun wird klar:
Das "erste Spalte" ist dynamisch. Also kommt das als Parameter.
Und wenn Du das durchspielst: Du musst natürlich abbrechen, wenn es keine Spalte mehr gibt.
Trozdem sieht die Methode nicht so aus, wie in der Anmerkung oben: Rekursive Umwandlung.
Ich denke, ich komme erstmal klar. Auf dieser Grundlage habe ich ein Algorithmus geschrieben,
welcher ein Sodukofeld lösen kann.
Dann übergebe der Methode doch beide Parameter x und y.
Ist einer der Parameter am Schachbrett Rand ist das deine Abbruchbedingung.
Somit brauchst die For nicht.
Ich glaube ich habe mich auch nicht verständich ausgedrück, bzw meine Anschlußfrage nicht richtig formuliert.
Das Prinzip der Rekursion habe ich mittlerweile Vestanden. Auch mit mehren Parametern.
Was ich halt immer noch nicht verstehe ist das Prinzip des Backtrackings, dass macht für mich nur Sinn, wenn ich halt die Rekursion in einer Schleife aufrufe und dann beim BackTracking ganau dort weiter mache.
Letzlich bin ich mit meiner akuellen Lösung zufrieden, aber ich lerne auch gerne dazu.
Backtracking geht nach dem Versuch-und-Irrtum-Prinzip(trial and error) vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert.
Also in #5 die Zeilen 10 und 11 - 10 prüft, ob das Ergebnis erfolgreich war. Wenn das nicht der Fall warm wird der letzte Schritt zurückgenommen (Feld wird wieder leer gemacht) und - in dieser Lösung noch iterativ - wird die nächste Möglichkeit versucht. Wurden alle Möglichkeiten ausgeschöpft, dann geht es halt noch eine Stufe zurück (Zeile 15 - das return false).
@KonradN
Ich will dich ja nicht in den Wahnsinn treiben.
Backtracking habe ich kapiert, aber wie soll ich das in diesem Muster einbinden.
Java:
void rekursiveLoesung(int i) {
// Abbruchbedingung
if (i >= Ende) return;
// Whatever
// Rekursivret Aufruf
rekursiveLoesung(i+1);
}
Mit dem rekusiven Aufruf in der Schleife bekomme ich das Bachtracking ja auch hin.
Vielleicht stehe ich einfach nur auf dem Schlauch und sollte das Thema noch mal viel Später aufgreifen.
Habe vielen Dank. Zu diesem Thema habe ich mit deiner Hilfe viel gelernt. Mein Code ist optimiert und
läuft so wie gewünscht.
void rekursiveLoesung(int i) {
// Abbruchbedingung
if (i >= Ende) return;
// Forward Step
// z.B. Figur setzen.
// Rekursiver Aufruf
rekursiveLoesung(i+1);
// Backward Step wenn nicht erfolgreich
// z.B. Figur wegnehmen
}
Das ist der typische Aufbau des Backtracking.
Ansonsten treibt man mich nicht so schnell in den Wahnsinn. Ich muss halt nur verstehen, wo es genau hakt.
Wir können das also auf unser Problem anwenden. Da hatten wir ja eine Lösung (Jetzt noch einen kleinen Copy-Fehler korrigiert ... stimmt jetzt hoffentlich):
Java:
private boolean dameSetzen(int xPosDame) {
if (xPosDame+1 > spielfeld) return true; // Abbruch der Rekursion, alle Damen gesetzt!
for (int yPosDame = 0; yPosDame < spielfeld+1; yPosDame++) {
if (checkPos(xPosDame, yPosDame)) {
PosDame[xPosDame] = yPosDame;
boolean result = dameSetzen(xPosDame + 1);
if (result) return true;
PosDame[xPosDame] = leer;
}
}
return false;
}
Bei dem Schema f hatten wir ja die Schleifenvariable zu einem Parameter gemacht. Das brauchen wir auch hier jetzt. Ebenso eine (zusätzliche) Abbruchbedingung:
Java:
private boolean dameSetzen(int xPosDame, int yPosDame) {
if (xPosDame == spielfeld) return true; // Abbruch der Rekursion, alle Damen erfolgreich gesetzt!
if (yPosDame == spielfeld) return false; // Alle Felder durchprobiert - Dame konnte nicht gesetzt werden!
// Prüfen des gegebenen Wertes
if (checkPos(xPosDame, yPosDame)) {
// Erfolg - wir setzen die Dame und machen in der nächsten Spalte weiter!
PosDame[xPosDame] = yPosDame;
boolean result = dameSetzen(xPosDame + 1, 0); // nächste Spalte startet mit yPos 0!
if (result) return true;
PosDame[xPosDame] = leer;
} else {
// Wir machen beim nächsten Feld weiter
boolean result = dameSetzen(xPosDame, yPosDame + 1); // nächste Spalte startet mit yPos 0!
if (result) return true;
}
return false;
}
Hi, @KonradN, super jetzt hab ich es tatsächlich kapiert.
Hat beim Nachdenken echt ein Knoten in die Gehirnwindungen gemacht.
Bei deinem Codebespiel, bedarf es aber keine "else"-Anweisung.
Die Anweisungen müssen dann generell ausgeführt werden, sonst wird der Y-Wert nach dem Backtracking nicht mehr erhöht.
Anbei die fertige, funktionierende Lösung.
Danke.
Java:
private boolean dameSetzen(int xPosDame, int yPosDame){
if (xPosDame == spielfeld) return true;
if (yPosDame == spielfeld) return false;
if (checkPos(xPosDame, yPosDame)){
posDame[xPosDame] = yPosDame;
System.out.println(Arrays.toString(posDame));
boolean result = dameSetzen(xPosDame + 1, 0);
if (result) return true;
}
boolean result = dameSetzen(xPosDame, yPosDame + 1);
if (result) return true;
posDame[xPosDame] = leer;
return false;
}
Was hast Du Dir z.B. mit der inneren Klasse Punkt gedacht? Du willst Speicherplatz sparen, daher quetscht Du die Koordinaten in einen Integer? Aber durch das Ableiten von SimpleEntity hast Du da gleich zwei Referenzen. Und dazu noch den Integer. Also unter dem Strich mehr Platz verbraucht als da einfach ein record mit int x und int y zu nehmen. Performance mit den ganzen Verschiebungen und dem ganzen Boxing / Unboxing mal nicht betrachtet ...
Nehmen wir dies einfach mal als ein Beispiel um zu schauen, was man da noch dran ändern könnte.
a) Innere Klasse Punkt
Hier bieten sich direkt records an - Du hast das ja sogar bereits final gemacht daher ist das direkt ein einfaches: public record Punkt (int x, int y){};
b) java coding styleguide: camel casing bei Bezeichnern, Konstanten in UPPERCASE:
backtracking_calculate_path -> backtrackingCalculatePath
get_moves -> getMoves
calculate_moves -> calculateMoves
moves_cache -> movesCache
dim -> BOARD_DIMENSIONS
c) Funktionalität in Konstruktor der nicht zur Initialisierung dient
Das wird eifnach eine neue Methode: calculate() und in der main landet dann von mir aus: new Springer().calculate();
d) doppelter Code in calculateMoves -> neue Methode, die mehrfach aufgerufen wird mit jeweils unterschiedlichen Parametern. Dabei die Variableb a und b in x und y umbenannt, denn das sind ja diese Koordinaten. a / b sagt ja nichts aus (und dx/dy sind ja Strecken oder Abstände und nicht Punkte im Coordinatensystem - das fand ich etwas verwirrend):
Java:
private void addMoveIfValid(int x, int y, HashSet<Punkt> moves) {
if (x >= 0 && x < dim && y >= 0 && y < dim) {
moves.add(new Punkt(x, y));
}
}
private HashSet<Punkt> calculateMoves(Punkt p) {
HashSet<Punkt> moves = new HashSet<>();
addMoveIfValid(p.x()+2, p.y()+1, moves);
addMoveIfValid(p.x()+2, p.y()-1, moves);
addMoveIfValid(p.x()-2, p.y()+1, moves);
addMoveIfValid(p.x()-2, p.y()-1, moves);
addMoveIfValid(p.x()+1, p.y()+2, moves);
addMoveIfValid(p.x()+1, p.y()-2, moves);
addMoveIfValid(p.x()-1, p.y()+2, moves);
addMoveIfValid(p.x()-1, p.y()-2, moves);
return moves;
}
Hier hätte man noch überlegen können, ob man mit Schleifen arbeiten will um dann zu iterieren. Da wäre z.B. denkbar, dass man die SpringerMoves als 2D Array erfasst um da gut mit einer Schleife zu arbeiten: private final static int[][] SPRINGER_MOVES = { {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, };
e) Dann stellt man fest, dass in dem calculate mehr drin ist - calculateAndPrint ist also passender. Und die Ausgabe kann man dann in Methoden ziehen.
printBoard
printMoves
f) in der Berechnung gehst Du von 0... dim*dim aber du willst nur mit den Koordinaten arbeiten. Daher machen wir doch direkt die Koordinaten und lassen die Berechnung außen vor.
g) Dan ist der Punkt last doch eigentlich der Startpunkt. Also benennen wir es auch so.
h) Das in den zwei Schleifen ist natürlich dann etwas, das man auch in eine Methode auslagern kann.
Damit hätten wir dann jetzt einen Stand, der so aussehen könnte:
Java:
package de.kneitzel;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
public class Springer {
private final static int[][] SPRINGER_MOVES = { {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, };
private final int DX = 0;
private final int DY = 1;
public record Punkt (int x, int y){};
private final int BOARD_DIMENSIONS = 6;
private final HashMap<Punkt, HashSet<Punkt>> movesCache = new HashMap<>();
public void calculateAndPrint() {
for (int x = 0; x < BOARD_DIMENSIONS; x++) {
for (int y = 0; y < BOARD_DIMENSIONS; y++) {
if (CalculateAndPrintForStartpoint(new Punkt(x, y))) break;
}
}
}
private boolean CalculateAndPrintForStartpoint(Punkt startPoint) {
HashSet<Punkt> visited = new HashSet<>();
LinkedList<Punkt> path = new LinkedList<>();
visited.add(startPoint);
path.add(startPoint);
boolean r = backtrackingCalculatePath(startPoint, visited, path);
System.out.println("visited = " + visited);
System.out.println("path = " + path);
printMoves(path);
if (r) {
return true;
}
return false;
}
private void printMoves(LinkedList<Punkt> path) {
for (Punkt p : path) {
printBoard(p);
}
}
private void printBoard(Punkt p) {
for (int i = 0; i < BOARD_DIMENSIONS; i++) {
for (int j = 0; j < BOARD_DIMENSIONS; j++) {
if (i == p.x && j == p.y) {
System.out.print("_s_ ");
} else {
System.out.print("___ ");
}
}
System.out.println();
}
System.out.println();
}
private boolean backtrackingCalculatePath(Punkt last, HashSet<Punkt> visited, LinkedList<Punkt> path) {
if (path.size() == BOARD_DIMENSIONS * BOARD_DIMENSIONS) {
return true;
}
HashSet<Punkt> moves = getMoves(last);
for (Punkt p : moves) {
if (!visited.contains(p)) {
visited.add(p);
path.add(p);
if (backtrackingCalculatePath(p, visited, path)) {
return true;
}
visited.remove(p);
path.removeLast();
}
}
return false;
}
private HashSet<Punkt> getMoves(Punkt p) {
if (!movesCache.containsKey(p)) {
movesCache.put(p, calculateMoves(p));
}
return movesCache.get(p);
}
private void addMoveIfValid(int x, int y, HashSet<Punkt> moves) {
if (x >= 0 && x < BOARD_DIMENSIONS && y >= 0 && y < BOARD_DIMENSIONS) {
moves.add(new Punkt(x, y));
}
}
private HashSet<Punkt> calculateMoves(Punkt p) {
HashSet<Punkt> moves = new HashSet<>();
for (int index = 0; index < SPRINGER_MOVES.length; index++) {
addMoveIfValid(
p.x + SPRINGER_MOVES[index][DX],
p.y + SPRINGER_MOVES[index][DY],
moves);
}
return moves;
}
public static void main(String[] args) {
new Springer().calculateAndPrint();
}
}
Ach ja - dabei wurde das Design selbst nicht wirklich betrachtet. Die Lösung ist also weiter in keiner Weise Objektorientiert oder so. Aber es bietet sich durchaus an, das natürlich auch besser aufzuteilen (wenn man so an Single responsibility denken will oder so).
Das ist so von der Betrachtungsweise nicht nachvollziehbar. Der Punkt ist ja nicht nicht eingefügt sondern an dem Punkt startest Du die Berechnung. Das erkennt man in dem Code sehr gut, wobei ich beim Aufruf ja die Variable raus geworfen habe:
Java:
public void calculateAndPrint() {
for (int x = 0; x < BOARD_DIMENSIONS; x++) {
for (int y = 0; y < BOARD_DIMENSIONS; y++) {
if (CalculateAndPrintForStartpoint(new Punkt(x, y))) break;
}
}
}
Da wird von der Logik her ja doch deutlich, dass es dort startet.
Ich habe nichts als falsch bezeichnet sondern lediglich einen besseren Namen vorgeschlagen. Und an der Funktionalität selbst hatte ich nichts verändert.
Bei Dir war es nun einmal:
Java:
public Springer() {
for (int k = 0; k < dim * dim; k++) {
Punkt last = new Punkt(k % dim, k / dim);
und das ist der Startpunkt - Du gehst da alle Punkte der Reihe nach durch. Aber das muss nicht weiter diskutiert werden. Das ist alles hier off topic. Wenn Du Deinen Code zeigen willst, dann mach eigene Threads auf. In einem Anfänger-Thread zum Thema Rekursion dann so iterative Algorithmen, die zudem noch extrem unleserlich sind, ist einfach nur daneben.
Nein, der Kommentar weist einfach darauf hin, dass es eben sowas wie SOLID Principles gibt und man sich da durchaus etwas danach richten sollte. Dadurch kommen so einfache Dinge zustande, die Du vielleicht auch schon gehört hast - so Dinge wie Trennung von Ausgabe und Berechnungen. Oder das Thema Kapselung die hier in keiner Weise gegeben ist. Aber es ist ok: Du darfst Deine Meinung haben. Es ist schade, dass Du absolut keine Argumente hast oder Diese Quatsch sind wie Dein "den "last" ist tatsächlich immer der zuletzt eingefügte Punkt." - das ist ein neu erstellter Punkt der noch nirgends eingefügt wurde... Aber das will ich nicht weiter thematisieren.
Das zeigt einfach nur, dass mich diese Frage nicht interessiert hat. Dein Algorithmus ist einfach nicht das Thema. Das ich da Deinen unleserlichen Code so behandelt habe, ist schon off topic. Wenn Du Probleme mit Deinem Algorithmus hast, dann mach einen eigenen Thread auf. Aber mach dazu lieber erst einen neuen Account, denn dieser wird vermutlich in Kürze wieder gesperrt.
Ansonsten ist es schade - Jetzt hast Du dich zwei Tage halbwegs zusammen gerissen (nicht wirklich - erste Versuche zu sticheln gab es ja schon direkt am ersten Tag) und dann kommt so eine Entgleisung. Daher fürchte ich, dass nicht meine Zeit abgelaufen ist sondern die von Deinem Account:
Der kleine Tobias will aus dem Bällespieleparadies abgeholt werden.
Wo steht da was von "falsch"? Das war alles sachlich, auch der von dir kritisierte Kommentar, der auf die verbesserungsfähige Objektorientierung hinweist.
Wenn der erste Punkt der einzige ist: Wieso dann die Schleife? Dann bräuchte man die Schleife nicht einmal.
Aber auch das würde nichts daran ändern, dass es der Startpunkt ist, von dem ab dann die Springerzüge losgehen. Und die Variablen sind nun einmal über den Sinn zu benennen.
Darüber kannst Du ja vielleicht einfach einmal nachdenken.
