Neunerpuzzle mit Bäumen

H

Haevelin

Mitglied
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?

Java:
/*
 * 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;
        }
    }
}


Java:
/*
* 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;
   
}
 
H

Haevelin

Mitglied
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!
 
MoxxiManagarm

MoxxiManagarm

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

MoxxiManagarm

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

CSHW89

Bekanntes Mitglied
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
 
X

Xyz1

Gast
Die Breitensuche wär fast ein Dreizeiler
Java:
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();

	}
}


Code:
[[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)
 
Anzeige

Neue Themen


Oben