Neuer Ansatz zum Neunerpuzzle |
Haevelin
Tripel-As
Dabei seit: 04.06.2013
Beiträge: 221
|
|
Neuer Ansatz zum Neunerpuzzle |
|
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
Tripel-As
Dabei seit: 04.06.2013
Beiträge: 221
|
|
RE: Neuer Ansatz zum Neunerpuzzle |
|
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 |
|
|
|