Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Neuer Ansatz zum Neunerpuzzle » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Neuer Ansatz zum Neunerpuzzle
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 220

Neuer Ansatz zum Neunerpuzzle Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo, jetzt habe ich es mit Bäumen versucht. Die Idee ist die Ausgangsstellung in root einzustellen, und dann nach up, down, Right und left zu verzweigen! So entsteht ein Baum mit einer maximalen Verzweigung von vier. Aber im Programm wird eine nullpointerexception geworfen! Das muss wohl irgendwie damit zusammenhängen, dass ich null da ansetze, wo keine Verzweigung mehr erfolgt! Hier der Code:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
/*
 * 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 Richard Kunstwadl
 */
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;

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.parent.content == matrix) {
                    doppelt = true;
                    return null;
                } else {
                    n = n.parent;
                }
            }
            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        return null;
    }
    
    
    
    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;

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.parent.content == matrix) {
                    doppelt = true;
                    return null;
                } else {
                    n = n.parent;
                }
            }
            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        return null;
    }
    
    
    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;

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.parent.content == matrix) {
                    doppelt = true;
                    return null;
                } else {
                    n = n.parent;
                }
            }
            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        return null;
    }
    
    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;

                }
            }

        }

        if (generiert == 1) {
            boolean doppelt = false;
            while (n != null) {
                if (n.parent.content == matrix) {
                    doppelt = true;
                    return null;
                } else {
                    n = n.parent;
                }
            }
            Node neu = new Node();
            neu.parent = n;
            neu.content = matrix;
            return neu;
        }
        return null;
    }

    public Node insert(Node n) {
        if (n != null) {
            n.eins = g_erster(n.content, n);
            if (n.eins != null && !abbruch(n.eins)){
                insert (n.eins);
            }
            if (abbruch(n.eins)) return n.eins;
            n.zwei = g_zweiter(n.content, n);
            if (n.zwei != null && !abbruch(n.zwei)){
                insert (n.zwei);
            }
            if (abbruch(n.zwei)) return n.zwei;
            n.drei = g_dritter(n.content, n);
            if (n.drei != null && !abbruch(n.drei)){
                insert (n.drei);
            }
            if (abbruch(n.drei)) return n.drei;
            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.content==ziel) { return true;} else {return false;}
    }
    

    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=null;
        Node v = new Node();
        v = p.root;
        Node resultat = new Node(); 
        resultat= p.insert(v);
        while (resultat.parent!=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;

    }
}





Es fehlt noch die Nodeklasse:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
/*
 * 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 Richard Kunstwadl
 */
public class Node {
    Node eins; 
    Node zwei;
    Node drei;
    Node vier;
    Node parent;
    int[][] content; 
    
}

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Haevelin: 13.10.2019 17:29.

13.10.2019 17:08 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 220

RE: Neuer Ansatz zum Neunerpuzzle Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Also die Nullpointerausnahmen kommen daher, dass ein Knoten erst erzeugt werden muss, ehe ihm null zugewiesen wird! Das habe ich jetzt behoben, und mein Programm läuft. Allerdings kommt er immer wieder auf die Ausgangslage zurück und bricht dann ab. In der Rekursion muss also noch etwas geändert werden! Kann mir jemand weiterhelfen? Hier der neue Code:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
/*
 * 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 Richard Kunstwadl
 */
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;
        }
    }
}

13.10.2019 18:55 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.858

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Ist die Frage noch aktuell? Ich habe keine Lust mich hier durchzukämpfen um das herauszufinden.

__________________
Syntax Highlighting fürs Board (Link)
20.10.2019 08:25 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Neuer Ansatz zum Neunerpuzzle