Neunerpuzzle mit Bäumen

[Haevelin]

Hallo,

gerne würde ich ein Rätsel mit dem Ausgang 1 2 3
8 0 5
4 7 6

lösen, so dass der Zielzustand: 1 2 3
4 5 6
7 8 0
zu erreichen. Mein Code nutzt eine Nodeklasse, und verzweiget für jeden Zustand in die möglichen Richtungen. Allerdings kommt die Rekursion nicht so richtig in Gang! Es wird versetzt, zurückgesetzt und dann abgebrochen! Wo liegt der Fehler?

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package FU_2;

import java.util.ArrayList;

/**
 *
 * @author RK
 */
public class L_E2_3 {

    int[][] ziel = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
    int[][] ausgang = {{1, 2, 3}, {8, 0, 5}, {4, 7, 6}};
    Node root = new Node();

    public Node g_erster(int[][] matrix, Node n) {
        int generiert = 0;
        for (int i = 1; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (matrix[i][j] == 0) {
                    int zwischen = matrix[i - 1][j];
                    matrix[i - 1][j] = 0;
                    matrix[i][j] = zwischen;
                    i = 3;
                    j = 3;
                    generiert = 1;
                    System.out.println("Neue Matrix errechnet");
                    ausgabe(matrix);

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.content == matrix) {
                    doppelt = true;
                    Node neu = new Node();
                    neu = null;
                    return neu;
                } else {
                    n = n.parent;
                }
            }
            System.out.println("Ein neuer Knoten wird generiert " + matrix);
            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        Node neu = new Node();
        neu = null;
        return neu;
    }

    public Node g_zweiter(int[][] matrix, Node n) {
        int generiert = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                if (matrix[i][j] == 0) {
                    int zwischen = matrix[i + 1][j];
                    matrix[i + 1][j] = 0;
                    matrix[i][j] = zwischen;
                    i = 3;
                    j = 3;
                    generiert = 1;
                    System.out.println("Neue Matrix errechnet");
                    ausgabe(matrix);

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.content == matrix) {
                    doppelt = true;
                    Node neu = new Node();
                    neu = null;
                    return neu;
                } else {
                    n = n.parent;
                }
            }
            System.out.println("Ein neuer Knoten wird generiert " + matrix);

            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        Node neu = new Node();
        neu = null;
        return neu;
    }

    public Node g_dritter(int[][] matrix, Node n) {
        int generiert = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j < 3; j++) {
                if (matrix[i][j] == 0) {
                    int zwischen = matrix[i][j - 1];
                    matrix[i][j - 1] = 0;
                    matrix[i][j] = zwischen;
                    i = 3;
                    j = 3;
                    generiert = 1;
                    System.out.println("Neue Matrix errechnet");
                    ausgabe(matrix);

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.content == matrix) {
                    doppelt = true;
                    Node neu = new Node();
                    neu = null;
                    return neu;
                } else {
                    n = n.parent;
                }
            }
            System.out.println("Ein neuer Knoten wird generiert " + matrix);

            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        Node neu = new Node();
        neu = null;
        return neu;
    }

    public Node g_vierter(int[][] matrix, Node n) {
        int generiert = 0;
        for (int i = 1; i < 3; i++) {
            for (int j = 0; j < 2; j++) {
                if (matrix[i][j] == 0) {
                    int zwischen = matrix[i][j + 1];
                    matrix[i][j + 1] = 0;
                    matrix[i][j] = zwischen;
                    i = 3;
                    j = 3;
                    generiert = 1;
                    System.out.println("Neue Matrix errechnet");
                    ausgabe(matrix);
                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.content == matrix) {
                    doppelt = true;
                    Node neu = new Node();
                    neu = null;
                    return neu;
                } else {
                    n = n.parent;
                }
            }
            System.out.println("Ein neuer Knoten wird generiert " + matrix);

            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        Node neu = new Node();
        neu = null;
        return neu;
    }

    public Node insert(Node n) {
        if (n != null) {
           // Node v = new Node();
            // n.eins = v;
            n.eins = g_erster(n.content, n);
            if (n.eins != null && !abbruch(n.eins)) {
                insert(n.eins);
            }
            if (abbruch(n.eins)) {
                return n.eins;
            }
            Node w = new Node();
            n.zwei = w;
            n.zwei = g_zweiter(n.content, n);
            if (n.zwei != null && !abbruch(n.zwei)) {
                insert(n.zwei);
            }
            if (abbruch(n.zwei)) {
                return n.zwei;
            }
            Node x = new Node();
            n.drei = x;
            n.drei = g_dritter(n.content, n);
            if (n.drei != null && !abbruch(n.drei)) {
                insert(n.drei);
            }
            if (abbruch(n.drei)) {
                return n.drei;
            }
            Node y = new Node();
            n.vier = y;
            n.vier = g_vierter(n.content, n);
            if (n.vier != null && !abbruch(n.vier)) {
                insert(n.vier);
            }
            if (abbruch(n.vier)) {
                return n.vier;
            }
        }
        return null;
    }

    public boolean abbruch(Node n) {
        if (n != null && n.content == ziel) {
            return true;
        } else {
            return false;
        }
    }
    
    public void ausgabe(int[][] matrix){
        for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("____________________");
            System.out.println();
        }
    

    public static void main(String[] args) {
        // TODO code application logic here
        L_E2_3 p = new L_E2_3();
        p.root.content = p.ausgang;
        p.root.parent = new Node();
        p.root.parent = null;
        Node v = new Node();
        v = p.root;
        Node resultat = new Node();
        resultat = p.insert(p.root);
        while (resultat != null) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    System.out.print(resultat.content[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("____________________");
            System.out.println();
            resultat = resultat.parent;
        }
    }
}

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package FU_2;

/**
*
* @author RK
*/
public class Node {
    Node eins;
    Node zwei;
    Node drei;
    Node vier;
    Node parent;
    int[][] content;
   
}

 

[Xyz1]

Brauchst ne Breitensuche.

Und btw.... wer soll sich das durchlesen?

 

[Haevelin]

Ja es werden ausgehend von root maximal vier Verzweigungen angehängt, und dann wenn unten im Baum eine Lösung auftaucht, der Weg zur Wurzel zurück verfolgt. Das ist der Lösungsweg! Das ist doch die Idee der Breitensuche! Aber wie gesagt, in der Rekursion von insert kommt die ein Knoten auf sich selbst zurück, und es wird abgebrochen! Die Rekursion von insert müsste angepasst werden, aber ich weiß nicht wie!

 

[Xyz1]

Na mit ner Breitensuche und Zyklen Detektion.

 

[MoxxiManagarm]

Wirklich? Eine Breitensuche für ein solches simples Rätsel? Das ist doch ein Schiebepuzzle, oder etwa nicht?

 

[Haevelin]

Ja, es ist ein Schiebepuzzle!

 

[MoxxiManagarm]

Ist das mit den Bäumen denn vorgegeben? Oder ist der Lösungsweg frei wählbar?

 

[CSHW89]

Ganz davon abgesehen, dass man das Problem wohl anders angehen würde, hast du drei Probleme im Code:
1. Du benutzt nur ein Array. Das wird von jedem Node geteilt. Sobald du das Array änderst, änderst du alle Nodes. Du musst das Array jedes mal kopieren.
2. Du vergleichst Arrays mit "==". Das geht so nicht. Ich meine die Arrays.equals Methode (statisch in der Klasse "Arrays" mit "s") kann auch zwei-dimensionale Arrays vergleichen. Die könntest du dann verwenden.
3. Du machst keine Breitensuche, sondern eine Tiefensuche. Deshalb wirst du nach Korrektur von 1 und 2 eine Endlosrekursion haben. Entweder du speicherst alle deine bisherigen Nodes, und prüfst, ob du die Situation schon hattest, und brichst ab falls ja. Dann wäre eine Tiefensuche weiterhin möglich. Und du stellst auf eine Breitensuche um. Da wäre aber deutlich mehr umzustrukturieren.

Viele Grüße
Kevin

 

[Xyz1]

Die Breitensuche wär fast ein Dreizeiler

import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringJoiner;

public class Spiel {
	int[][] ziel = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
	int[][] ausgang = { { 1, 2, 3 }, { 8, 0, 5 }, { 4, 7, 6 } };

	ArrayList<int[][]> followings(int[][] a) {
		ArrayList<int[][]> nextes = new ArrayList<int[][]>();
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				if (a[i][j] == 0) {
					if (i - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i - 1, j));
					}
					if (i + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i + 1, j));
					}
					if (j - 1 >= 0) {
						nextes.add(copyAndShift(a, i, j, i, j - 1));
					}
					if (j + 1 < a.length) {
						nextes.add(copyAndShift(a, i, j, i, j + 1));
					}
					return nextes;
				}
			}
		}
		return nextes;
	}

	int[][] copyAndShift(int[][] a, int i, int j, int i2, int j2) {
		int[][] b = new int[a.length][a.length];
		for (int k = 0; k < a.length; k++) {
			for (int k2 = 0; k2 < a.length; k2++) {
				b[k][k2] = a[k][k2];
			}
		}
		b[i][j] = b[i2][j2];
		b[i2][j2] = 0;
		return b;
	}

	void print() {
		ArrayList<StringJoiner> js = new ArrayList<StringJoiner>();
		js.add(new StringJoiner(" > ").add(Arrays.deepToString(ausgang)));

		ArrayList<int[][]> nextes = new ArrayList<int[][]>();
		nextes.add(ausgang);
		for (int i = 0; i < 1000; i++) {
			int[][] a = nextes.get(i);
			ArrayList<int[][]> b = followings(a);
			nextes.addAll(b);
			for (int[][] c : b) {
				js.add(new StringJoiner(" > ").merge(js.get(i)).add(Arrays.deepToString(c)));

				if (Arrays.deepEquals(c, ziel)) {
					System.out.println(js.get(i));
					return;
				}
			}
		}
	}

	public static void main(String[] args) {

		Spiel l = new Spiel();
		l.print();

	}
}

[[1, 2, 3], 
 [8, 0, 5], 
 [4, 7, 6]] > 
[[1, 2, 3], 
 [0, 8, 5], 
 [4, 7, 6]] > 
[[1, 2, 3], 
 [4, 8, 5], 
 [0, 7, 6]] > 
[[1, 2, 3], 
 [4, 8, 5], 
 [7, 0, 6]] > 
[[1, 2, 3], 
 [4, 0, 5], 
 [7, 8, 6]] > 
[[1, 2, 3], 
 [4, 5, 0], 
 [7, 8, 6]]

(Wer schlechte Variablennamen findet der darf sie behalten)

 

[MoxxiManagarm]

Nunja, es kommt auch darauf an, ob man den kürzesten Weg zur Lösung haben will. Dann ist der Suchweg wahrscheinlich sogar richtig. Aber performanter ist dieser deswegen nicht unbedingt. Obwohl wir ja nur von 3x3 reden. 3x3 hat theoretisch maximal 31 Züge zur Lösung. https://math.stackexchange.com/ques...number-of-moves-required-for-hardest-8-puzzle

 

[Haevelin]

Da sag ich mal Respekt! Vielen Dank!

 

[Xyz1]

Aber performanter ist dieser deswegen nicht unbedingt

Es könnte langsam sein da
- Strings verwendet werden,
- keine "Heuristik" verwendet wird.

Aber nur mal eine "Randüberlegung": Es gibt höchstens nur 9^9 = 387420489 Möglichkeiten (eigentlich weniger). Das nich allzu viel.

Da sag ich mal Respekt! Vielen Dank

Bitte bitte.

 

[Xyz1]

Oh Danke für den Link @MoxxiManagarm , 9!/2 = 181440,
habe mich um 99,95 % verschätzt.

 

[mihe7]

habe mich um 99,95 % verschätzt.

Einfach das BER-Motto anwenden: mein Gott, knapp vorbei wär auch daneben...