?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge with git+ssh://dirk2@repo.or.cz/srv/git/schiebespiel.git
[schiebespiel.git] / schiebe.java
blob3aa2f71b0a7e7448101b269f8c712da85448bffb
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 testluft();
117 }
118 }
119 /**
120 * Überprüft, ob das Ziel gefunden wurde und gibt in dem Fall den Weg aus
121 */
122 private static LinkedList<Knoten> testZiel(LinkedList<Knoten> expandListe, boolean systemout)
123 {
124 LinkedList<Knoten> trefferListe = new LinkedList<Knoten>();
125
126 for (Knoten l : expandListe) {
127 if (l.compareTo( ziel ) == 0) {
128 if (l.get_tiefe() < beste_tiefe) {
129 beste_tiefe = l.get_tiefe();
130 trefferListe.add(l);
131 if (systemout) {
132 System.out.println("Wir haben einen Weg gefunden!");
133 System.out.println(l);
134 Knoten p;
135 while( l.get_parent() != null) {
136 p = l.get_parent();
137 System.out.println(p);
138 l = p;
139 }
140 for (int i = 0; i< 3; ++i) {
141 System.out.println(
142 "========================================");
143 }
144 }
145 }
146 }
147 }
148 return trefferListe;
149 }
150 /**
151 * Durchsucht den Suchraum bis Tiefe 6 per Breitensuche. Von dort aus wird eine A*
152 * Suche mit Luftlinienheuristik angestoßen mit dem Nachteil,
153 * dass ab hier die Teilbäume von einander untersucht werden
154 */
155
156 private static void testluft() {
157 Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
158 start.computeHeuristik();
159 System.out.println(start.get_heuristik());
160 }
161
162 private static void asternluft() {
163 // Alle Knoten der Tiefe 7 entwickeln
164 LinkedList<Knoten> schichtListe= new LinkedList<Knoten>();
165 schichtListe.add(start);
166 Knoten.setHeuristikTyp(Knoten.HEURISTIK_SIMPEL);
167 LinkedList<Knoten> expandListe= null;
168 boolean tiefe8=false;
169 while (!tiefe8) {
170 Knoten k = schichtListe.poll();
171 expandListe = trs.expandKnoten(k);
172 testZiel(expandListe,true);
173 if (expandListe.getFirst().get_tiefe()<8) {
174 schichtListe.addAll(expandListe);
175 }
176 else tiefe8 = true;
177 Collections.sort(schichtListe);
178 }
179
180 // nun enthällt schichtListe alle Knoten der Tiefe 7
181 // und wir beginnen mit A* LuftlinienHeuristik
182
183 System.out.println("Schicht 7 entwickelt");
184
185 //zunächst schichtListe nach LuftlinienHeuristik sortieren
186 Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
187 for (Knoten k: schichtListe){
188 k.computeHeuristik();
189 }
190 Collections.sort(schichtListe);
191
192 //nun für jeden Knoten der Schicht 7 A* ausführen
193 for (Knoten k : schichtListe) {
194 LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
195 knotenListe.addAll(trs.expandKnoten(k));
196 Knoten l = null;
197 while (knotenListe.size()>0 && knotenListe.getFirst().get_tiefe()<20 ){
198 l = knotenListe.poll();
199 expandListe = trs.expandKnoten(l);
200 testZiel(expandListe,true);
201 knotenListe.addAll(expandListe);
202 Collections.sort(knotenListe);
203 }
204 }
205 }
206
207 private static void asternsimpel() {
208
209 //int max_tiefe = 0;
210
211 //Knoten.SetHeuristikTyp(Knoten.HEURISTIK_DIFFERENZ);
212
213 LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
214 knotenListe.add(start);
215 while( knotenListe.size() > 0 ) {
216 Knoten k = knotenListe.poll();
217 /*if (k.get_tiefe() > max_tiefe) {
218 max_tiefe = k.get_tiefe();
219 System.out.println("Maximale Tiefe: " + max_tiefe
220 + " Länge der Liste : " + knotenListe.size());
221 }*/
222 LinkedList<Knoten> expandListe = trs.expandKnoten(k);
223 for (Knoten l : expandListe) {
224 if (l.compareTo( ziel ) == 0) {
225 if (l.get_tiefe() < beste_tiefe) {
226 beste_tiefe = l.get_tiefe();
227 System.out.println("Wir haben einen Weg gefunden!");
228 System.out.println(l);
229 Knoten p;
230 while( l.get_parent() != null) {
231 p = l.get_parent();
232 System.out.println(p);
233 l = p;
234 }
235 for (int i = 0; i< 3; ++i) {
236 System.out.println(
237 "========================================");
238 }
239 }
240 }
241 }
242 knotenListe.addAll(expandListe);
243 Collections.sort(knotenListe);
244 //KnotenListe trimmen
245 if (knotenListe.size()>10000)
246 {
247 while (knotenListe.size()>10000)
248 knotenListe.removeLast();
249 }
250 //debugausgaben
251 for (int i=0;i<5 & i<knotenListe.size();i++)
252 {
253 System.out.print(knotenListe.get(i).get_heuristik()+ " (" + knotenListe.get(i).get_tiefe()+") ");
254 }
255 System.out.print(knotenListe.getLast().get_heuristik()+ " (" + knotenListe.getLast().get_tiefe()+") ");
256 System.out.print(knotenListe.size());
257 System.out.println();
258
259 }
260 }
261
262 private static void tiefensuche() {
263 //todo tiefensuche rekursiv implementieren
264 int beste_tiefe = 32786;
265 int max_tiefe = 0;
266
267 Knoten ka=null, kb=null, kc=null, kd=null, ke=null,
268 kf=null, kg=null, kh=null, ki=null, kj=null,
269 kk=null, kl=null, km=null, kn=null, ko=null,
270 kp=null, kq=null, kr=null;
271
272 LinkedList<Knoten> knotenListeA = new LinkedList<Knoten>();
273 LinkedList<Knoten> knotenListeB = new LinkedList<Knoten>();
274 LinkedList<Knoten> knotenListeC = new LinkedList<Knoten>();
275 LinkedList<Knoten> knotenListeD = new LinkedList<Knoten>();
276 LinkedList<Knoten> knotenListeE = new LinkedList<Knoten>();
277 LinkedList<Knoten> knotenListeF = new LinkedList<Knoten>();
278 LinkedList<Knoten> knotenListeG = new LinkedList<Knoten>();
279 LinkedList<Knoten> knotenListeH = new LinkedList<Knoten>();
280 LinkedList<Knoten> knotenListeI = new LinkedList<Knoten>();
281 LinkedList<Knoten> knotenListeJ = new LinkedList<Knoten>();
282 LinkedList<Knoten> knotenListeK = new LinkedList<Knoten>();
283 LinkedList<Knoten> knotenListeL = new LinkedList<Knoten>();
284 LinkedList<Knoten> knotenListeM = new LinkedList<Knoten>();
285 LinkedList<Knoten> knotenListeN = new LinkedList<Knoten>();
286 LinkedList<Knoten> knotenListeO = new LinkedList<Knoten>();
287 LinkedList<Knoten> knotenListeP = new LinkedList<Knoten>();
288 LinkedList<Knoten> knotenListeQ = new LinkedList<Knoten>();
289 LinkedList<Knoten> knotenListeR = new LinkedList<Knoten>();
290
291
292 knotenListeA = trs.expandKnoten(start);
293 System.out.println(knotenListeA.size());
294 for (int a=0; a<knotenListeA.size(); a++)
295 {
296 ka= knotenListeA.get(a);
297 if (ka.compareTo( ziel ) == 0)
298 System.out.println("GEFUNDEN A");
299 knotenListeB = trs.expandKnoten(ka);
300
301 for (int b=0; b<knotenListeB.size(); b++)
302 {
303 kb=knotenListeB.get(b);
304 if (kb.compareTo( ziel ) == 0)
305 System.out.println("GEFUNDEN B");
306 knotenListeC = trs.expandKnoten(kb);
307
308 for (int c=0; c<knotenListeC.size(); c++)
309 {
310 kc=knotenListeC.get(c);
311 if (kc.compareTo( ziel ) == 0)
312 System.out.println("GEFUNDEN C");
313 knotenListeD = trs.expandKnoten(kc);
314
315 for (int d=0; d<knotenListeD.size(); d++)
316 {
317 kd=knotenListeD.get(d);
318 if (kd.compareTo( ziel ) == 0)
319 System.out.println("GEFUNDEN D");
320 knotenListeE = trs.expandKnoten(kd);
321
322 for (int e=0;
323 e<knotenListeE.size(); e++)
324 {
325 ke=knotenListeE.get(e);
326 if (ke.compareTo( ziel ) == 0)
327 System.out.println("GEFUNDEN E");
328 knotenListeF = trs.expandKnoten(ke);
329
330 for (int f=0;
331 f<knotenListeF.size(); f++)
332 {
333
334 kf=knotenListeF.get(f);
335 if (kf.compareTo( ziel ) == 0)
336 System.out.println("GEFUNDEN F");
337 knotenListeG = trs.expandKnoten(kf);
338
339 for (int g=0;
340 g<knotenListeG.size(); g++)
341 {
342
343 kg=knotenListeG.get(g);
344 if (kg.compareTo( ziel ) == 0)
345 System.out.println("GEFUNDEN G");
346
347 knotenListeH = trs.expandKnoten(kg);
348
349 for (int
350 h=0; h<knotenListeH.size(); h++)
351 {
352
353 kh=knotenListeH.get(h);
354
355 if (kh.compareTo( ziel ) == 0)
356 System.out.println("GEFUNDEN H");
357
358 knotenListeI = trs.expandKnoten(kh);
359
360 for
361 (int i=0; h<knotenListeH.size(); h++)
362 {
363 ki=knotenListeI.get(i);
364 if (ki.compareTo( ziel ) == 0)
365 System.out.println("GEFUNDEN I");
366 knotenListeJ = trs.expandKnoten(ki);
367
368 for (int j=0;
369 j<knotenListeJ.size(); j++)
370 {
371 kj=knotenListeJ.get(j);
372 if (kj.compareTo( ziel ) == 0)
373 System.out.println("GEFUNDEN J");
374 knotenListeK = trs.expandKnoten(kj);
375
376 for (int k=0;
377 k<knotenListeK.size(); k++)
378 {
379
380 kk=knotenListeK.get(k);
381 if (kk.compareTo( ziel ) == 0)
382 System.out.println("GEFUNDEN K");
383 knotenListeL =
384 trs.expandKnoten(kk);
385
386 for (int l=0;
387 l<knotenListeL.size(); l++)
388 {
389
390 kl=knotenListeL.get(l);
391 if (kl.compareTo( ziel ) == 0)
392 System.out.println("GEFUNDEN L");
393 knotenListeM =
394 trs.expandKnoten(kl);
395
396 for (int m=0;
397 m<knotenListeM.size(); m++)
398 {
399
400 km=knotenListeM.get(m);
401 if (km.compareTo( ziel ) == 0)
402 System.out.println("GEFUNDEN M");
403 knotenListeN
404 = trs.expandKnoten(km);
405
406 for (int n=0;
407 n<knotenListeN.size(); n++)
408 {
409
410 kn=knotenListeN.get(n);
411 if (kn.compareTo( ziel ) == 0)
412 System.out.println("GEFUNDEN N");
413
414 knotenListeO = trs.expandKnoten(kn);
415
416 for (int o=0; o<knotenListeO.size(); o++)
417 {
418
419 ko=knotenListeO.get(o);
420 if (ko.compareTo( ziel ) == 0)
421 System.out.println("GEFUNDEN O");
422
423 knotenListeP = trs.expandKnoten(ko);
424
425 for
426 (int p=0; p<knotenListeP.size(); p++)
427 {
428
429 kp=knotenListeP.get(p);
430
431 if (kp.compareTo( ziel ) == 0)
432 System.out.println("GEFUNDEN P");
433
434 knotenListeQ = trs.expandKnoten(kp);
435
436
437 for (int q=0; q<knotenListeQ.size(); q++)
438 {
439
440 kq=knotenListeQ.get(q);
441
442 if (kq.compareTo( ziel ) == 0)
443 System.out.println("GEFUNDEN Q");
444
445 knotenListeR = trs.expandKnoten(kq);
446
447
448 for (int r=0; r<knotenListeR.size(); r++)
449
450 {
451
452 kr=knotenListeR.get(r);
453
454 if (kr.compareTo( ziel ) == 0)
455 System.out.println("GEFUNDEN R");
456
457 // knotenListeS = trs.expandKnoten(kr);
458 }
459 }
460 }
461
462 }
463
464 }
465 }
466 }
467 }
468 }
469 }
470 }
471 }
472 }
473 }
474 }
475 }
476 }
477 }
478
479 ////////////////// ENDE TIEFENSUCHE
480 }
481
482 }
483
Compute solutions for the "Schiebespiel" board game