?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
(no commit message)
[schiebespiel.git] / schiebe.java
blobf1fbf23b56f00cbc5f22ff61281e91c64e379e29
1 /* Schiebespiel - effectively computes solution for a one player board game
2 * Copyright (C) 2007 Dirk Ribbroch / Martin Drohmann
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19 import java.util.*;
20
21 class schiebe {
22 private final int ALGO_TIEFENSUCHE = 0;
23 private final int ALGO_ASTERN_SIMPEL = 1;
24 private static Transitions trs = new Transitions();
25 private static Knoten start = new Knoten();
26 private static Knoten ziel = new Knoten();
27 private static Knoten ziel_final = new Knoten();
28 private static int beste_tiefe = 32786;
29
30 public static void main(String[] argv) {
31 // Start Konfiguration
32 start.set_field(0,0,Knoten.zweier_links);
33 start.set_field(1,0,Knoten.zweier_rechts);
34 start.set_field(2,0,Knoten.zweier_links);
35 start.set_field(3,0,Knoten.zweier_rechts);
36 start.set_field(4,0,Knoten.einer);
37 start.set_field(0,3,Knoten.zweier_links);
38 start.set_field(1,3,Knoten.zweier_rechts);
39 start.set_field(2,3,Knoten.zweier_links);
40 start.set_field(3,3,Knoten.zweier_rechts);
41 start.set_field(4,3,Knoten.einer);
42 start.set_field(0,1,Knoten.vierer_lu);
43 start.set_field(1,1,Knoten.vierer_ru);
44 start.set_field(2,1,Knoten.zweier_unten);
45 start.set_field(3,1,Knoten.einer);
46 start.set_field(4,1,Knoten.leer);
47 start.set_field(0,2,Knoten.vierer_lo);
48 start.set_field(1,2,Knoten.vierer_ro);
49 start.set_field(2,2,Knoten.zweier_oben);
50 start.set_field(3,2,Knoten.einer);
51 start.set_field(4,2,Knoten.leer);
52 start.set_leere(0, 4, 1);
53 start.set_leere(1, 4, 2);
54 start.set_leere(2, -1,-1);
55 start.set_leere(3, -1,-1);
56 // Ziel Konfiguration
57 ziel.set_field(0,0,Knoten.zweier_links);
58 ziel.set_field(1,0,Knoten.zweier_rechts);
59 ziel.set_field(2,0,Knoten.zweier_links);
60 ziel.set_field(3,0,Knoten.zweier_rechts);
61 ziel.set_field(0,3,Knoten.einer);
62 ziel.set_field(3,2,Knoten.zweier_links);
63 ziel.set_field(4,2,Knoten.zweier_rechts);
64 ziel.set_field(2,3,Knoten.zweier_links);
65 ziel.set_field(3,3,Knoten.zweier_rechts);
66 ziel.set_field(4,3,Knoten.einer);
67 ziel.set_field(0,1,Knoten.vierer_lu);
68 ziel.set_field(1,1,Knoten.vierer_ru);
69 ziel.set_field(2,1,Knoten.zweier_unten);
70 ziel.set_field(3,1,Knoten.einer);
71 ziel.set_field(4,1,Knoten.leer);
72 ziel.set_field(0,2,Knoten.vierer_lo);
73 ziel.set_field(1,2,Knoten.vierer_ro);
74 ziel.set_field(2,2,Knoten.zweier_oben);
75 ziel.set_field(4,0,Knoten.einer);
76 ziel.set_field(1,3,Knoten.leer);
77 // Unser eigentliches Ziel für das das ganze Programm existiert
78 ziel_final.set_field(0,0,Knoten.zweier_links);
79 ziel_final.set_field(1,0,Knoten.zweier_rechts);
80 ziel_final.set_field(0,1,Knoten.zweier_links);
81 ziel_final.set_field(1,1,Knoten.zweier_rechts);
82 ziel_final.set_field(0,2,Knoten.zweier_links);
83 ziel_final.set_field(1,2,Knoten.zweier_rechts);
84 ziel_final.set_field(0,3,Knoten.zweier_links);
85 ziel_final.set_field(1,3,Knoten.zweier_rechts);
86 ziel_final.set_field(2,0,Knoten.einer);
87 ziel_final.set_field(2,1,Knoten.einer);
88 ziel_final.set_field(2,2,Knoten.zweier_oben);
89 ziel_final.set_field(2,3,Knoten.zweier_unten);
90 ziel_final.set_field(3,0,Knoten.vierer_lo);
91 ziel_final.set_field(4,0,Knoten.vierer_ro);
92 ziel_final.set_field(3,1,Knoten.vierer_lu);
93 ziel_final.set_field(4,1,Knoten.vierer_ru);
94 ziel_final.set_field(3,2,Knoten.einer);
95 ziel_final.set_field(4,2,Knoten.einer);
96 ziel_final.set_field(3,3,Knoten.leer);
97 ziel_final.set_field(4,3,Knoten.leer);
98
99 Knoten.set_start(start);
100 Knoten.set_ziel(ziel);
101
102 /* Hiermit beginnen wir */
103 System.out.println("Hiermit beginnen wir: \n" + start.toString());
104 /* Dies ist das Ziel */
105 System.out.println("Das ist das Ziel:\n" + ziel.toString());
106
107 //System.out.println(argv.length);
108 if( argv.length > 0) {
109 if( argv[0].equals("tiefensuche") ) {
110 tiefensuche();
111 } else if( argv[0].equals("asternsimpel") ) {
112 asternsimpel();
113 }
114 } else { /* Default: */
115 asternluft();
116 }
117 }
118 /**
119 * Überprüft, ob das Ziel gefunden wurde und gibt in dem Fall den Weg aus
120 */
121 private static LinkedList<Knoten> testZiel(LinkedList<Knoten> expandListe, boolean systemout)
122 {
123 LinkedList<Knoten> trefferListe = new LinkedList<Knoten>();
124
125 for (Knoten l : expandListe) {
126 if (l.compareTo( ziel ) == 0) {
127 if (l.get_tiefe() < beste_tiefe) {
128 beste_tiefe = l.get_tiefe();
129 trefferListe.add(l);
130 if (systemout) {
131 System.out.println("Wir haben einen Weg gefunden!");
132 System.out.println(l);
133 Knoten p;
134 while( l.get_parent() != null) {
135 p = l.get_parent();
136 System.out.println(p);
137 l = p;
138 }
139 for (int i = 0; i< 3; ++i) {
140 System.out.println(
141 "========================================");
142 }
143 }
144 }
145 }
146 }
147 return trefferListe;
148 }
149 /**
150 * Durchsucht den Suchraum bis Tiefe 6 per Breitensuche. Von dort aus wird eine A*
151 * Suche mit Luftlinienheuristik angestoßen mit dem Nachteil,
152 * dass ab hier die Teilbäume von einander untersucht werden
153 */
154
155
156 private static void asternluft() {
157 // Alle Knoten der Tiefe 7 entwickeln
158 LinkedList<Knoten> schichtListe= new LinkedList<Knoten>();
159 schichtListe.add(start);
160 Knoten.setHeuristikTyp(Knoten.HEURISTIK_SIMPEL);
161 LinkedList<Knoten> expandListe= null;
162 boolean tiefe8=false;
163 while (!tiefe8) {
164 Knoten k = schichtListe.poll();
165 expandListe = trs.expandKnoten(k);
166 testZiel(expandListe,true);
167 if (expandListe.getFirst().get_tiefe()<8) {
168 schichtListe.addAll(expandListe);
169 }
170 else tiefe8 = true;
171 Collections.sort(schichtListe);
172 }
173
174 // nun enthällt schichtListe alle Knoten der Tiefe 7
175 // und wir beginnen mit A* LuftlinienHeuristik
176
177 System.out.println("Schicht 7 entwickelt");
178
179 //zunächst schichtListe nach LuftlinienHeuristik sortieren
180 Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
181 for (Knoten k: schichtListe){
182 k.computeHeuristik();
183 }
184 Collections.sort(schichtListe);
185
186 //nun für jeden Knoten der Schicht 7 A* ausführen
187 for (Knoten k : schichtListe) {
188 LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
189 knotenListe.addAll(trs.expandKnoten(k));
190 Knoten l = null;
191 while (knotenListe.size()>0 && knotenListe.getFirst().get_tiefe()<20 ){
192 l = knotenListe.poll();
193 expandListe = trs.expandKnoten(l);
194 testZiel(expandListe,true);
195 knotenListe.addAll(expandListe);
196 Collections.sort(knotenListe);
197 }
198 }
199 }
200
201 private static void asternsimpel() {
202
203 //int max_tiefe = 0;
204
205 //Knoten.SetHeuristikTyp(Knoten.HEURISTIK_DIFFERENZ);
206
207 LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
208 knotenListe.add(start);
209 while( knotenListe.size() > 0 ) {
210 Knoten k = knotenListe.poll();
211 /*if (k.get_tiefe() > max_tiefe) {
212 max_tiefe = k.get_tiefe();
213 System.out.println("Maximale Tiefe: " + max_tiefe
214 + " Länge der Liste : " + knotenListe.size());
215 }*/
216 LinkedList<Knoten> expandListe = trs.expandKnoten(k);
217 for (Knoten l : expandListe) {
218 if (l.compareTo( ziel ) == 0) {
219 if (l.get_tiefe() < beste_tiefe) {
220 beste_tiefe = l.get_tiefe();
221 System.out.println("Wir haben einen Weg gefunden!");
222 System.out.println(l);
223 Knoten p;
224 while( l.get_parent() != null) {
225 p = l.get_parent();
226 System.out.println(p);
227 l = p;
228 }
229 for (int i = 0; i< 3; ++i) {
230 System.out.println(
231 "========================================");
232 }
233 }
234 }
235 }
236 knotenListe.addAll(expandListe);
237 Collections.sort(knotenListe);
238 //KnotenListe trimmen
239 if (knotenListe.size()>10000)
240 {
241 while (knotenListe.size()>10000)
242 knotenListe.removeLast();
243 }
244 //debugausgaben
245 for (int i=0;i<5 & i<knotenListe.size();i++)
246 {
247 System.out.print(knotenListe.get(i).get_heuristik()+ " (" + knotenListe.get(i).get_tiefe()+") ");
248 }
249 System.out.print(knotenListe.getLast().get_heuristik()+ " (" + knotenListe.getLast().get_tiefe()+") ");
250 System.out.print(knotenListe.size());
251 System.out.println();
252
253 }
254 }
255
256 private static void tiefensuche() {
257 //todo tiefensuche rekursiv implementieren
258 int beste_tiefe = 32786;
259 int max_tiefe = 0;
260
261 Knoten ka=null, kb=null, kc=null, kd=null, ke=null,
262 kf=null, kg=null, kh=null, ki=null, kj=null,
263 kk=null, kl=null, km=null, kn=null, ko=null,
264 kp=null, kq=null, kr=null;
265
266 LinkedList<Knoten> knotenListeA = new LinkedList<Knoten>();
267 LinkedList<Knoten> knotenListeB = new LinkedList<Knoten>();
268 LinkedList<Knoten> knotenListeC = new LinkedList<Knoten>();
269 LinkedList<Knoten> knotenListeD = new LinkedList<Knoten>();
270 LinkedList<Knoten> knotenListeE = new LinkedList<Knoten>();
271 LinkedList<Knoten> knotenListeF = new LinkedList<Knoten>();
272 LinkedList<Knoten> knotenListeG = new LinkedList<Knoten>();
273 LinkedList<Knoten> knotenListeH = new LinkedList<Knoten>();
274 LinkedList<Knoten> knotenListeI = new LinkedList<Knoten>();
275 LinkedList<Knoten> knotenListeJ = new LinkedList<Knoten>();
276 LinkedList<Knoten> knotenListeK = new LinkedList<Knoten>();
277 LinkedList<Knoten> knotenListeL = new LinkedList<Knoten>();
278 LinkedList<Knoten> knotenListeM = new LinkedList<Knoten>();
279 LinkedList<Knoten> knotenListeN = new LinkedList<Knoten>();
280 LinkedList<Knoten> knotenListeO = new LinkedList<Knoten>();
281 LinkedList<Knoten> knotenListeP = new LinkedList<Knoten>();
282 LinkedList<Knoten> knotenListeQ = new LinkedList<Knoten>();
283 LinkedList<Knoten> knotenListeR = new LinkedList<Knoten>();
284
285
286 knotenListeA = trs.expandKnoten(start);
287 System.out.println(knotenListeA.size());
288 for (int a=0; a<knotenListeA.size(); a++)
289 {
290 ka= knotenListeA.get(a);
291 if (ka.compareTo( ziel ) == 0)
292 System.out.println("GEFUNDEN A");
293 knotenListeB = trs.expandKnoten(ka);
294
295 for (int b=0; b<knotenListeB.size(); b++)
296 {
297 kb=knotenListeB.get(b);
298 if (kb.compareTo( ziel ) == 0)
299 System.out.println("GEFUNDEN B");
300 knotenListeC = trs.expandKnoten(kb);
301
302 for (int c=0; c<knotenListeC.size(); c++)
303 {
304 kc=knotenListeC.get(c);
305 if (kc.compareTo( ziel ) == 0)
306 System.out.println("GEFUNDEN C");
307 knotenListeD = trs.expandKnoten(kc);
308
309 for (int d=0; d<knotenListeD.size(); d++)
310 {
311 kd=knotenListeD.get(d);
312 if (kd.compareTo( ziel ) == 0)
313 System.out.println("GEFUNDEN D");
314 knotenListeE = trs.expandKnoten(kd);
315
316 for (int e=0;
317 e<knotenListeE.size(); e++)
318 {
319 ke=knotenListeE.get(e);
320 if (ke.compareTo( ziel ) == 0)
321 System.out.println("GEFUNDEN E");
322 knotenListeF = trs.expandKnoten(ke);
323
324 for (int f=0;
325 f<knotenListeF.size(); f++)
326 {
327
328 kf=knotenListeF.get(f);
329 if (kf.compareTo( ziel ) == 0)
330 System.out.println("GEFUNDEN F");
331 knotenListeG = trs.expandKnoten(kf);
332
333 for (int g=0;
334 g<knotenListeG.size(); g++)
335 {
336
337 kg=knotenListeG.get(g);
338 if (kg.compareTo( ziel ) == 0)
339 System.out.println("GEFUNDEN G");
340
341 knotenListeH = trs.expandKnoten(kg);
342
343 for (int
344 h=0; h<knotenListeH.size(); h++)
345 {
346
347 kh=knotenListeH.get(h);
348
349 if (kh.compareTo( ziel ) == 0)
350 System.out.println("GEFUNDEN H");
351
352 knotenListeI = trs.expandKnoten(kh);
353
354 for
355 (int i=0; h<knotenListeH.size(); h++)
356 {
357 ki=knotenListeI.get(i);
358 if (ki.compareTo( ziel ) == 0)
359 System.out.println("GEFUNDEN I");
360 knotenListeJ = trs.expandKnoten(ki);
361
362 for (int j=0;
363 j<knotenListeJ.size(); j++)
364 {
365 kj=knotenListeJ.get(j);
366 if (kj.compareTo( ziel ) == 0)
367 System.out.println("GEFUNDEN J");
368 knotenListeK = trs.expandKnoten(kj);
369
370 for (int k=0;
371 k<knotenListeK.size(); k++)
372 {
373
374 kk=knotenListeK.get(k);
375 if (kk.compareTo( ziel ) == 0)
376 System.out.println("GEFUNDEN K");
377 knotenListeL =
378 trs.expandKnoten(kk);
379
380 for (int l=0;
381 l<knotenListeL.size(); l++)
382 {
383
384 kl=knotenListeL.get(l);
385 if (kl.compareTo( ziel ) == 0)
386 System.out.println("GEFUNDEN L");
387 knotenListeM =
388 trs.expandKnoten(kl);
389
390 for (int m=0;
391 m<knotenListeM.size(); m++)
392 {
393
394 km=knotenListeM.get(m);
395 if (km.compareTo( ziel ) == 0)
396 System.out.println("GEFUNDEN M");
397 knotenListeN
398 = trs.expandKnoten(km);
399
400 for (int n=0;
401 n<knotenListeN.size(); n++)
402 {
403
404 kn=knotenListeN.get(n);
405 if (kn.compareTo( ziel ) == 0)
406 System.out.println("GEFUNDEN N");
407
408 knotenListeO = trs.expandKnoten(kn);
409
410 for (int o=0; o<knotenListeO.size(); o++)
411 {
412
413 ko=knotenListeO.get(o);
414 if (ko.compareTo( ziel ) == 0)
415 System.out.println("GEFUNDEN O");
416
417 knotenListeP = trs.expandKnoten(ko);
418
419 for
420 (int p=0; p<knotenListeP.size(); p++)
421 {
422
423 kp=knotenListeP.get(p);
424
425 if (kp.compareTo( ziel ) == 0)
426 System.out.println("GEFUNDEN P");
427
428 knotenListeQ = trs.expandKnoten(kp);
429
430
431 for (int q=0; q<knotenListeQ.size(); q++)
432 {
433
434 kq=knotenListeQ.get(q);
435
436 if (kq.compareTo( ziel ) == 0)
437 System.out.println("GEFUNDEN Q");
438
439 knotenListeR = trs.expandKnoten(kq);
440
441
442 for (int r=0; r<knotenListeR.size(); r++)
443
444 {
445
446 kr=knotenListeR.get(r);
447
448 if (kr.compareTo( ziel ) == 0)
449 System.out.println("GEFUNDEN R");
450
451 // knotenListeS = trs.expandKnoten(kr);
452 }
453 }
454 }
455
456 }
457
458 }
459 }
460 }
461 }
462 }
463 }
464 }
465 }
466 }
467 }
468 }
469 }
470 }
471 }
472
473 ////////////////// ENDE TIEFENSUCHE
474 }
475
476 }
477
Compute solutions for the "Schiebespiel" board game