Rekursives Backtracking beim Spiel Peg

cookiiee

Mitglied
Hi,
ich möchte das Spiel Peg programmieren. es scheitert aber daran ein rekursives Backtracking zu erstellen. Im Moment ist es so das das Feld nur zum Teil gelöst wird, das Programm aber dann aufhört weiterzurechnen, was daran liegt das er keinen Zug zurückgeht um einen anderern auszuprobieren.

Java:
import java.awt.*;
import java.awt.Image;
import java.awt.Toolkit;
import java.util.ArrayList;
import java.util.Collections;

import javax.swing.*;

public class Kreuzfeld2 {

    static int[] feld = new int[49];
    public static    ArrayList<Zug> züge = new ArrayList<Zug>();
    public static int[][] loesung = new int[100][49];
    public static int[][] zeichne = new int [32][49];
    public static int GemachteZüge = -1;

    public  class Zug implements Comparable<Zug> {
        int x;   
        int y;
        int z;
       

        public  Zug(int x, int y, int z) {
            super();
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override
        public int compareTo(Zug z) {
            return (z.x - x) * 100 + (z.y - y);
        }

    }
    public static void main(String[] args) {
       
        new Kreuzfeld2();
       
    }
   

    public  Kreuzfeld2() {

        feldInit();
        gueltigeZuege();
        Collections.sort(züge);
        zeichnefeld(feld);
        loese(steinAnzahlBestimmen());
        System.out.println("--- Fertig ---");
    }

    private int steinAnzahlBestimmen() {
        int s = 0;
        for (int i = 0; i < 49; i++) {
            if (feld[i] == 1) s++;
        }
        return s;
    }

    public void gueltigeZuege() {
        int[] nachuntenlist = { 2, 3, 4, 9, 10, 11, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25, 30, 31, 32 };
        int[] nachrechtslist = { 2, 9, 14, 15, 16, 17, 18, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 37, 44 };
        int[] nachobenlist = { 16, 17, 18, 23, 24, 25, 28, 29, 30, 31, 32, 33, 34, 37, 38, 39, 44, 45, 46 };
        int[] nachlinkslist = { 4, 11, 16, 17, 18, 19, 20, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34, 39, 46 };
        int[] nachuntenlinkslist = { 3, 4, 9, 10, 11, 16, 17, 18, 19, 20, 25, 26, 27, 32, 33};
        int[] nachobenrechtslist = {15, 16, 21, 22, 23, 28, 29, 30, 31, 32, 37, 38, 39, 44, 45};
        int[] nachuntenrechtslist = {2, 3, 9, 10, 11, 14, 15, 16, 17, 18, 21, 22, 23, 29, 30};
        int[] nachobenlinkslist = {18, 19, 25, 26, 27, 30, 31, 32, 33, 34, 37, 38, 39, 45, 46};
        for(int i : nachobenlinkslist) {
            züge.add(new Zug(i, i - 8, i -16));
        }
        for (int i : nachuntenrechtslist) {
            züge.add(new Zug(i, i + 8, i + 16));
        }
        for (int i : nachuntenlinkslist) {
            züge.add(new Zug(i, i + 6, i + 12));
        }
        for (int i : nachobenrechtslist) {
            züge.add(new Zug(i, i - 6, i - 12));
        }
        for (int i : nachrechtslist) {
            züge.add(new Zug(i, i + 1, i + 2));
        }
        for (int i : nachlinkslist) {
            züge.add(new Zug(i, i - 1, i - 2));
        }
        for (int i : nachuntenlist) {
            züge.add(new Zug(i, i + 7, i + 14));
        }
        for (int i : nachobenlist) {
            züge.add(new Zug(i, i - 7, i - 14));
        }
       
    }

    private void loese(int steine)  {
        if (steine == 1) if (feld[30] == 1) {
            for (int i = 32; i > 1; i--)
                if (GemachteZüge < 31) {
                    zeichnefeld(loesung[i]);
                   
                }
               
               
           
           
                    }
        for (Zug zug : züge) {
            if (feld[zug.x] == 1) if (feld[zug.y] == 1) if (feld[zug.z] == 0) if(feld[zug.y] != loesung[zug.y][steine + 1] )    {
                feld[zug.x] = 0;
                feld[zug.y] = 0;
                feld[zug.z] = 1;
                System.arraycopy(feld, 0, loesung[steine], 0, feld.length);
                loese(steine - 1);
                feld[zug.x] = 1;
                feld[zug.y] = 1;
                feld[zug.z] = 0;
            }
           
        }
   
    }

   
    private static void zeichnefeld(int[] f) {
       
        GemachteZüge++;
       
       
       
        System.out.println();
        for (int i = 0; i < 49; i++) {
            if (i % 7 == 0) System.out.println();
            System.out.print((f[i] == 1) ? "x" : (f[i] == 0 ? "o" : " "));
           
        }
        System.out.println();
        System.out.println(GemachteZüge);
       
       
       
        for (int i = 0; i < 49; i++) {
           
            zeichne[GemachteZüge][i]= f[i];
           
           
        }
       
       
       
   
       
    }
   

    public void feldInit() {
        for (int i = 0; i < 49; i++)
            feld[i] = -1;
        feld[2] = 1;
        feld[3] = 1;
        feld[4] = 1;
        feld[9] = 1;
        feld[10] = 1;
        feld[11] = 1;
        feld[14] = 1;
        feld[15] = 1;
        feld[16] = 1;
        feld[17] = 1;
        feld[18] = 1;
        feld[19] = 1;
        feld[20] = 1;
        feld[21] = 1;
        feld[22] = 1;
        feld[23] = 1;
        feld[24] = 1;
        feld[25] = 1;
        feld[26] = 1;
        feld[27] = 1;
        feld[28] = 1;
        feld[29] = 1;
        feld[30] = 0;
        feld[31] = 1;
        feld[32] = 1;
        feld[33] = 1;
        feld[34] = 1;
        feld[37] = 1;
        feld[38] = 1;
        feld[39] = 1;
        feld[44] = 1;
        feld[45] = 1;
        feld[46] = 1;
       
       
    }

}

Meine Frage ist nun wie muss ich die loese Methode verändern damit er wenn er keinen Zug mehr gehen kann dann einen zurückgeht und einen anderen ausprobiert?
Vielen Dank im Voraus
cookiiee
 

mihe7

Top Contributor
Java:
if (feld[zug.x] == 1) if (feld[zug.y] == 1) if (feld[zug.z] == 0) if(feld[zug.y] != loesung[zug.y][steine + 1] )   {
Witziges Konstrukt. Das geht auch mit &&.

Wofür ist die letzte Bedingung?

damit er wenn er keinen Zug mehr gehen kann dann einen zurückgeht und einen anderen ausprobiert?
Wenn ich nix übersehen habe, machst Du das schon. Lediglich bzgl. der letzten Bedingung mache ich mir Gedanken :)
 

cookiiee

Mitglied
Die letzte Bedingung sollte dazu dienen das er wenn er nen Zug zurück gehen würde er dann nicht den gleichen Zug wieder macht, den er davor schon gemacht hat. Weil er ja sonst die ganze Zeit wenn er zurückgeht den gleichen Zug wieder macht. Aber so wirklich Sinn macht die Bedingung nicht wenn ich so weiter drüber nachdenk.
 

cookiiee

Mitglied
Ja, aber wie stell ichs an das er wenn er keine Züge mehr machen kann er dann einen zurückgeht und einen anderen probiert? Bzw. das er den gleichen Zug dann nicht wieder macht?
 

cookiiee

Mitglied
private void loese(int steine) {
if (steine == 1) if (feld[30] == 1) {
for (int i = 32; i > 1; i--)
if (GemachteZüge < 31) {
zeichnefeld(loesung[i]);

}




}
for (Zug zug : züge) {
if (feld[zug.x] == 1) if (feld[zug.y] == 1) if (feld[zug.z] == 0) if(feld[zug.y] != loesung[zug.y][steine + 1] ) {
feld[zug.x] = 0;
feld[zug.y] = 0;
feld[zug.z] = 1;
System.arraycopy(feld, 0, loesung[steine], 0, feld.length);
loese(steine - 1);
feld[zug.x] = 1;
feld[zug.y] = 1;
feld[zug.z] = 0;
}

}

}

Im Moment ist es so das wenn man z.b. die if-Bedingung steine=1 auch steine=4 setzt das Programm bis zu steinen runterrechnet und dann das Ergebnis als Lösung ausgibt. Nur möchte ich gern das er das auch bei steine=1 macht. Dazu muss das Programm aber wenn es nicht mehr weiter rechnen kann einen Zug zurück gehen und einen anderen probieren und das solange bis er eine Lösung gefunden hat bei der nur noch 1 stein auf dem Feld ist.
 

mihe7

Top Contributor
@cookiiee Ich verstehe das Problem nicht.

loese(1): es ist nur noch ein Stein auf dem Spielbrett, damit hast Du eine Lösung gefunden.

loese(n) mit n > 1: Du hast noch keine Lösung gefunden. Dann ist entweder noch ein Zug möglich oder nicht. Die möglichen Züge werden in Deiner for-Schleife gefunden. Falls kein möglicher Zug gefunden wird, ist loese(n) beendet. Falls doch, wird der betreffende Zug z ausgeführt, loese(n-1) aufgerufen und danach der Zug z wieder rückgängig gemacht, so dass bei jedem Zug in loese(n) immer das gleiche Spielfeld als Ausgangssituation vorgefunden wird.

Sprich: du probierst ALLE möglichen Zugkombinationen(!) durch.
 

cookiiee

Mitglied
@mihe7
Ja aber das Problem ist das er das Feld bis zu einem gewissen Stand rechnet und dann aber weder Steine = 1 ist noch er einen möglichen Zug findet. Was ich nun nicht verstehe wie ich definiere das er , wenn er einen Zug wieder zurück geht weil dieser nicht zu einer Lösung führt, dann einen anderen Zug probiert als den vorherigen. Weil im Moment springt er dann quasi ein Zug zurück und dann diesen wieder vor und das permanent.
 

mihe7

Top Contributor
Ich steige da gedanklich auch nicht durch....
Im Endeffekt spielt es keine Rolle. Es geht im Wesentlichen darum, dass am Ende nur ein Stein übrig bleibt.

Der Algorithmus, den er hat ist:
Code:
loese(n) {
     if (n == 1) { fertig; }
     for (zug : moeglicheZuege) {
         wendeZugAn(zug);
         loese(n-1);
         macheZugRückgängig(zug);
    }
}
Ich verstehe nicht, warum er permanent hin und her springen sollte...
 

cookiiee

Mitglied
@mihe7

Naja irgendwas muss ja falsch sein weil
wenn ichs starte dann kommt er zu keinem Ergebnis. und mein Gedanke ist das wenn er einen Zug zurück geht weil er keine Lösung findet wo nur noch 1 Stein ist er immer zwischen 2 Zügen hin und her springt. Aber so wie du mir das grad erklärst ist mein Gedankengang wohl falsch. Aber wieso zeichnet er mir beim ausführen des Programms keine Lösung.
 

mihe7

Top Contributor
Probier mal:
Java:
    private void loese(int steine)  {
        if (steine == 1) {
            zeichnefeld(feld);
            return;
        }

        for (Zug zug : züge) {
            if ((feld[zug.x] == 1) && (feld[zug.y] == 1) && (feld[zug.z] == 0)) {
                feld[zug.x] = 0;
                feld[zug.y] = 0;
                feld[zug.z] = 1;
                System.arraycopy(feld, 0, loesung[steine], 0, feld.length);
                loese(steine - 1);
                feld[zug.x] = 1;
                feld[zug.y] = 1;
                feld[zug.z] = 0;
            }
        }
    }
 

mihe7

Top Contributor
Der Zug hat drei Werte: von-Feld (x), nach-Feld (z) und übersprungenes Feld (y).

Er prüft also ab, ob von-Feld und übersprungenes Feld im Spielfeld belegt sind und das nach-Feld frei ist (1, 1, 0). Ist das der Fall, ist der Zug möglich und wird ausgeführt -> 0, 0, 1. Nach der Lösungssuche wird es wieder rückgängig gemacht -> 1,1,0
 
X

Xyz1

Gast
1. Asse nach oben
2. Nur Könige auf freie Felder
3. Untere Karten umschichten
3.1 schichte hintere Karten zuerst um
4. Neue Karte ziehen

das sollte ungefähr die Reihenfolge sein in der Züge gemacht werden sollten (Strategie)....
Mich juckt es schon in den Fingern, da mal was auszuprobieren aber nicht mehr heute.
 

cookiiee

Mitglied
@mihe7
Erstmal Danke für deinen Vorschlag.
Jetzt rechnet er es durch und gibt mir das Lösungsfeld auch aus.
if (steine == 1) {
Aber du hast ja die if-Bedingung die angibt an welchen Feld am Schluss ein stein also eine 1 stehen muss ja entfernt. Wenn ich es wieder hinzu füge dann rechnet er komischer Weise aber nicht mehr. Ich versteh nicht ganz warum nicht.
 

mihe7

Top Contributor
Code:
Zug: 2467173
ooooooo    xxx      xxx      xxx      xxx      xxx      xxx      xxx
ooooooo    xxx      xxx      xxx      xxx      xxx      xxx      xxx
ooooooo  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx
ooooooo  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx  xxxxxxx
ooooooo  xxxxxxx  xxxxxxx  xxxxxox  xxxxxox  xxxooxx  xxxoxoo  xoxoxoo
ooooooo    xox      xox      xoo      xoo      xoo      xoo      ooo
ooooooo    xxo      oox      oxx      xoo      xoo      xoo      xxo

Darf man diagonal über eine Ecke springen?

Aber du hast ja die if-Bedingung die angibt an welchen Feld am Schluss ein stein also eine 1 stehen muss ja entfernt.
Wer sagt denn, dass der angegebene Stein eine mögliche Lösung ist und wer sagt, dass die nicht irgendwann erreicht wird?
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Rekursives Programm zum Anzeigen von Primzahlen Java Basics - Anfänger-Themen 3
G Rekursives Programmieren --> harmonische Reihe Java Basics - Anfänger-Themen 3
S Rekursives Problem.... Java Basics - Anfänger-Themen 16
S Rekursives Durchlaufen eines Verzeichnisses - AccessDeniedException behandeln Java Basics - Anfänger-Themen 1
S Rekursives Zählen einer Zahl Java Basics - Anfänger-Themen 8
J Rekursives Parsen (ohne Reg Expressions) Java Basics - Anfänger-Themen 8
S Rekursives Umdrehen, Spiegeln. etc. von Strings Java Basics - Anfänger-Themen 3
I Rekursives Löschen in Binärem Suchbaum Java Basics - Anfänger-Themen 2
L rekursives spiel programmieren Java Basics - Anfänger-Themen 4
G Rekursives aufrufen führt zu StackOverflowError Panel durchl Java Basics - Anfänger-Themen 5
M Rekursives suchen im TreeMenu Java Basics - Anfänger-Themen 10
N Rekursives suchen in einer Liste Java Basics - Anfänger-Themen 8
G Primzahlentester als rekursives Programm! Java Basics - Anfänger-Themen 13
H Rekursives einlesen von Lokalen Ordner Java Basics - Anfänger-Themen 4
Max246Sch 3D Box Filler BAcktracking Java Basics - Anfänger-Themen 1
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 14
districon Dynamisch Programmierung/Backtracking/Memoization Java Basics - Anfänger-Themen 3
districon Backtracking funktioniert nicht ganz Java Basics - Anfänger-Themen 3
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
G Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
O Backtracking Java Basics - Anfänger-Themen 5
A Backtracking Java Basics - Anfänger-Themen 56
R Backtracking Java Basics - Anfänger-Themen 1
V Feld sortieren mit Backtracking Java Basics - Anfänger-Themen 1
A Sudoku mit Backtracking lösen Java Basics - Anfänger-Themen 3
L Sudoku Backtracking Pseudocode Java Basics - Anfänger-Themen 3
N Backtracking - Labyrinth/Irrgarten Java Basics - Anfänger-Themen 14
I Backtracking Schach Java Basics - Anfänger-Themen 5
L Magisches Quadrat und Backtracking Java Basics - Anfänger-Themen 19
M Backtracking/Solve Methode Java Basics - Anfänger-Themen 7
P Labyrinth, Backtracking, verzögerte Anzeige Java Basics - Anfänger-Themen 15
D Sudoku lösen mit Backtracking Java Basics - Anfänger-Themen 20
E backtracking und Induktionsprinzip Java Basics - Anfänger-Themen 2
D Backtracking Waage Problem Java Basics - Anfänger-Themen 23
N Backtracking Solohalma Java Basics - Anfänger-Themen 2
W Backtracking und Frustration Java Basics - Anfänger-Themen 6
X Sudoku Backtracking Java Basics - Anfänger-Themen 6
J Solitaire via Backtracking Java Basics - Anfänger-Themen 7
A Backtracking - kennt Java keine Rücksprungmarken? Java Basics - Anfänger-Themen 15
G Backtracking mit globaler Variable Java Basics - Anfänger-Themen 5
M BackTracking Java Basics - Anfänger-Themen 22
J Backtracking Algorithmus Java Basics - Anfänger-Themen 16
Juelin jedit Fehler beim starten Java Basics - Anfänger-Themen 2
Kerstininer Vererbung Hilfe beim lernen von Objektorientierung für eine Klausur Java Basics - Anfänger-Themen 10
A Hilfe beim Lesen von Pfaden und Systemvariablen Java Basics - Anfänger-Themen 3
M Ausgabe beim Overloading Java Basics - Anfänger-Themen 3
W Null-Pointer Exception beim Programmstart Java Basics - Anfänger-Themen 8
H Nutzt Eclipse alle CPU-Threads beim Ausführen von Java-Programmen? Java Basics - Anfänger-Themen 4
M Nullpointer beim befüllen meiner Liste im Object Java Basics - Anfänger-Themen 3
J Beim Start des Programms zB. eine Linie in JPanel ausgeben Java Basics - Anfänger-Themen 4
I Projekte in IDE untereinander sharen / Probleme beim Build Java Basics - Anfänger-Themen 8
paulen1 Best Practice "Unchecked Assignment" Warnung beim erstellen eines 2D Arrays of Arraylists Java Basics - Anfänger-Themen 2
T Probleme beim Import eines Git-Repos Java Basics - Anfänger-Themen 2
C GLOOP Problem beim Erstellen der Kamera Java Basics - Anfänger-Themen 9
N Array beim erstellen mit Werten füllen Java Basics - Anfänger-Themen 6
T DamagedFontException beim drucken Java Basics - Anfänger-Themen 3
Z SNAKE Schlange beim Aufheben von Essen verlängern Java Basics - Anfänger-Themen 4
Bugs Bunny Fehlerhafte Berechnung beim erneuten Durchlaufen der Schleife Java Basics - Anfänger-Themen 5
stormyark Fehler beim überschreiben einer Variable Java Basics - Anfänger-Themen 1
T String Array Fehler beim Index Java Basics - Anfänger-Themen 3
Fiedelbambu Prüfen von Komma stelle beim Taschenrechner Java Basics - Anfänger-Themen 5
B Objekte verschwinden beim Übersetzen Java Basics - Anfänger-Themen 5
L Beim Java Programmstart, mehrere Parameter über die Kommandozeile übergeben Java Basics - Anfänger-Themen 9
sserio Problem beim Anzeigen Java Basics - Anfänger-Themen 5
X Hilfe beim Übertragen in eine For-Schleife Java Basics - Anfänger-Themen 1
S Fehler beim Programm Java Basics - Anfänger-Themen 2
G Main Methode wird beim ersten Aufruf nicht richtig ausgeführt Java Basics - Anfänger-Themen 1
M String beim einlesen formatieren Java Basics - Anfänger-Themen 12
N Exception beim Verwenden von Arraylist? Java Basics - Anfänger-Themen 10
I InputStream beim zweiten Mal fehlerhaft Java Basics - Anfänger-Themen 10
C Fehler beim erstellen eines Objektes Java Basics - Anfänger-Themen 3
C Brauche Hilfe beim Schreiben eines Programmes :/ Java Basics - Anfänger-Themen 1
cmn489 Werte beim Funktionsaufruf in ein Feld übertragen(falls dieses leer ist) Java Basics - Anfänger-Themen 1
I Output BigDecimal anstatt double / Problem beim Rechnen Java Basics - Anfänger-Themen 16
S Kriege Fehler "Exception in thread" beim Benutzen von SubStrings. Java Basics - Anfänger-Themen 2
D Hilfe beim Erzeugen eines Arrays NullPointerException wird ausgelöst Java Basics - Anfänger-Themen 11
Nerdinfekt BMI Rechner, fehler beim Zurückgeben des Strings? Java Basics - Anfänger-Themen 2
CptK Richtigen Pfad beim einlesen von Datei finden Java Basics - Anfänger-Themen 2
O Methode in while-Schleife aufrufen geht nur beim ersten Mal Java Basics - Anfänger-Themen 2
pry bitte Hilfe beim Kreditrechner objektorientiert Java Basics - Anfänger-Themen 6
J Hilfe beim Label animieren Java Basics - Anfänger-Themen 1
Avalon Programmierstil beim Mocken Java Basics - Anfänger-Themen 45
Avalon NullPointerException beim Mocken Java Basics - Anfänger-Themen 6
J Hilfe beim verstehen Java Basics - Anfänger-Themen 3
A Fehler beim Ausführen einer class Datei Java Basics - Anfänger-Themen 6
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Compiler-Fehler Fehler beim Ausführen des Codes Java Basics - Anfänger-Themen 25
L Anfänger braucht Hilfe - Stecke beim Lernen fest Java Basics - Anfänger-Themen 10
N Probleme beim printen von Arrays durch for Schleife Java Basics - Anfänger-Themen 3
Bluedaishi Hilfe beim erklären dieser Methode Java Basics - Anfänger-Themen 5
E Macht Java Rechenfehler beim Potenzieren und Mod? Java Basics - Anfänger-Themen 5
J Hilfe beim Programmieren Java Basics - Anfänger-Themen 5
C Fehler beim Speichern (Build projekt) Java Basics - Anfänger-Themen 42
S Endlosschleife beim Ausgeben einer LinkedList Java Basics - Anfänger-Themen 2
tom.j85 TicTacToe - probleme beim Casten Java Basics - Anfänger-Themen 6
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
Kirby.exe Fehler beim Ausgeben Java Basics - Anfänger-Themen 2
L Brauche Hilfe beim arbeiten mit Konstruktoren Java Basics - Anfänger-Themen 20

Ähnliche Java Themen

Neue Themen


Oben