?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
heuristik blockiert bei tiefe über 18. suche hat dann "Kammerflimmern".
[schiebespiel.git] / schiebe.java
blob5bb0392791636533f4525e798828f5e30668c952
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
29 public static void main(String[] argv) {
30 // Start Konfiguration
31 start.set_field(0,0,Knoten.zweier_links);
32 start.set_field(1,0,Knoten.zweier_rechts);
33 start.set_field(2,0,Knoten.zweier_links);
34 start.set_field(3,0,Knoten.zweier_rechts);
35 start.set_field(4,0,Knoten.einer);
36 start.set_field(0,3,Knoten.zweier_links);
37 start.set_field(1,3,Knoten.zweier_rechts);
38 start.set_field(2,3,Knoten.zweier_links);
39 start.set_field(3,3,Knoten.zweier_rechts);
40 start.set_field(4,3,Knoten.einer);
41 start.set_field(0,1,Knoten.vierer_lu);
42 start.set_field(1,1,Knoten.vierer_ru);
43 start.set_field(2,1,Knoten.zweier_unten);
44 start.set_field(3,1,Knoten.einer);
45 start.set_field(4,1,Knoten.leer);
46 start.set_field(0,2,Knoten.vierer_lo);
47 start.set_field(1,2,Knoten.vierer_ro);
48 start.set_field(2,2,Knoten.zweier_oben);
49 start.set_field(3,2,Knoten.einer);
50 start.set_field(4,2,Knoten.leer);
51 start.set_leere(0, 4, 1);
52 start.set_leere(1, 4, 2);
53 start.set_leere(2, -1,-1);
54 start.set_leere(3, -1,-1);
55 // Ziel Konfiguration
56 ziel.set_field(0,0,Knoten.zweier_links);
57 ziel.set_field(1,0,Knoten.zweier_rechts);
58 ziel.set_field(0,1,Knoten.zweier_links);
59 ziel.set_field(1,1,Knoten.zweier_rechts);
60 ziel.set_field(0,2,Knoten.zweier_links);
61 ziel.set_field(1,2,Knoten.zweier_rechts);
62 ziel.set_field(0,3,Knoten.zweier_links);
63 ziel.set_field(1,3,Knoten.zweier_rechts);
64 ziel.set_field(2,0,Knoten.einer);
65 ziel.set_field(2,1,Knoten.einer);
66 ziel.set_field(2,2,Knoten.zweier_oben);
67 ziel.set_field(2,3,Knoten.zweier_unten);
68 ziel.set_field(3,0,Knoten.vierer_lo);
69 ziel.set_field(4,0,Knoten.vierer_ro);
70 ziel.set_field(3,1,Knoten.vierer_lu);
71 ziel.set_field(4,1,Knoten.vierer_ru);
72 ziel.set_field(3,2,Knoten.einer);
73 ziel.set_field(4,2,Knoten.einer);
74 ziel.set_field(3,3,Knoten.leer);
75 ziel.set_field(4,3,Knoten.leer);
76 // Unser eigentliches Ziel für das das ganze Programm existiert
77 ziel_final.set_field(0,0,Knoten.zweier_links);
78 ziel_final.set_field(1,0,Knoten.zweier_rechts);
79 ziel_final.set_field(0,1,Knoten.zweier_links);
80 ziel_final.set_field(1,1,Knoten.zweier_rechts);
81 ziel_final.set_field(0,2,Knoten.zweier_links);
82 ziel_final.set_field(1,2,Knoten.zweier_rechts);
83 ziel_final.set_field(0,3,Knoten.zweier_links);
84 ziel_final.set_field(1,3,Knoten.zweier_rechts);
85 ziel_final.set_field(2,0,Knoten.einer);
86 ziel_final.set_field(2,1,Knoten.einer);
87 ziel_final.set_field(2,2,Knoten.zweier_oben);
88 ziel_final.set_field(2,3,Knoten.zweier_unten);
89 ziel_final.set_field(3,0,Knoten.vierer_lo);
90 ziel_final.set_field(4,0,Knoten.vierer_ro);
91 ziel_final.set_field(3,1,Knoten.vierer_lu);
92 ziel_final.set_field(4,1,Knoten.vierer_ru);
93 ziel_final.set_field(3,2,Knoten.einer);
94 ziel_final.set_field(4,2,Knoten.einer);
95 ziel_final.set_field(3,3,Knoten.leer);
96 ziel_final.set_field(4,3,Knoten.leer);
97
98 Knoten.set_start(start);
99 Knoten.set_ziel(ziel);
100
101 /* Hiermit beginnen wir */
102 System.out.println("Hiermit beginnen wir: \n" + start.toString());
103 /* Dies ist das Ziel */
104 System.out.println("Das ist das Ziel:\n" + ziel.toString());
105
106 //System.out.println(argv.length);
107 if( argv.length > 0) {
108 if( argv[0].equals("Tiefensuche") ) {
109 tiefensuche();
110 } else if( argv[0].equals("asternsimpel") ) {
111 asternsimpel();
112 }
113 } else { /* Default: */
114 asternsimpel();
115 }
116 }
117
118 private static void asternsimpel() {
119 int beste_tiefe = 32786;
120 int max_tiefe = 0;
121
122 Knoten.SetHeuristikTyp(Knoten.HEURISTIK_DIFFERENZ);
123
124 LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
125 knotenListe.add(start);
126 while( knotenListe.size() > 0 ) {
127 Knoten k = knotenListe.poll();
128 if (k.get_tiefe() > max_tiefe) {
129 max_tiefe = k.get_tiefe();
130 System.out.println("Maximale Tiefe: " + max_tiefe
131 + " Länge der Liste : " + knotenListe.size());
132 }
133 LinkedList<Knoten> expandListe = trs.expandKnoten(k);
134 for (Knoten l : expandListe) {
135 if (l.compareTo( ziel ) == 0) {
136 if (l.get_tiefe() < beste_tiefe) {
137 beste_tiefe = l.get_tiefe();
138 System.out.println("Wir haben einen Weg gefunden!");
139 System.out.println(l);
140 Knoten p;
141 while( l.get_parent() != null) {
142 p = l.get_parent();
143 System.out.println(p);
144 l = p;
145 }
146 for (int i = 0; i< 3; ++i) {
147 System.out.println(
148 "========================================");
149 }
150 }
151 }
152 }
153 knotenListe.addAll(expandListe);
154 Collections.sort(knotenListe);
155 //KnotenListe trimmen
156 if (knotenListe.size()>10000)
157 {
158 while (knotenListe.size()>10000)
159 knotenListe.removeLast();
160 }
161 //debugausgaben
162 for (int i=0;i<5 & i<knotenListe.size();i++)
163 {
164 System.out.print(knotenListe.get(i).get_heuristik()+ " (" + knotenListe.get(i).get_tiefe()+") ");
165 }
166 System.out.print(knotenListe.getLast().get_heuristik()+ " (" + knotenListe.getLast().get_tiefe()+") ");
167 System.out.print(knotenListe.size());
168 System.out.println();
169
170 }
171 }
172
173 private static void tiefensuche() {
174 //todo tiefensuche rekursiv implementieren
175 int beste_tiefe = 32786;
176 int max_tiefe = 0;
177
178 Knoten ka=null, kb=null, kc=null, kd=null, ke=null,
179 kf=null, kg=null, kh=null, ki=null, kj=null,
180 kk=null, kl=null, km=null, kn=null, ko=null,
181 kp=null, kq=null, kr=null;
182
183 LinkedList<Knoten> knotenListeA = new LinkedList<Knoten>();
184 LinkedList<Knoten> knotenListeB = new LinkedList<Knoten>();
185 LinkedList<Knoten> knotenListeC = new LinkedList<Knoten>();
186 LinkedList<Knoten> knotenListeD = new LinkedList<Knoten>();
187 LinkedList<Knoten> knotenListeE = new LinkedList<Knoten>();
188 LinkedList<Knoten> knotenListeF = new LinkedList<Knoten>();
189 LinkedList<Knoten> knotenListeG = new LinkedList<Knoten>();
190 LinkedList<Knoten> knotenListeH = new LinkedList<Knoten>();
191 LinkedList<Knoten> knotenListeI = new LinkedList<Knoten>();
192 LinkedList<Knoten> knotenListeJ = new LinkedList<Knoten>();
193 LinkedList<Knoten> knotenListeK = new LinkedList<Knoten>();
194 LinkedList<Knoten> knotenListeL = new LinkedList<Knoten>();
195 LinkedList<Knoten> knotenListeM = new LinkedList<Knoten>();
196 LinkedList<Knoten> knotenListeN = new LinkedList<Knoten>();
197 LinkedList<Knoten> knotenListeO = new LinkedList<Knoten>();
198 LinkedList<Knoten> knotenListeP = new LinkedList<Knoten>();
199 LinkedList<Knoten> knotenListeQ = new LinkedList<Knoten>();
200 LinkedList<Knoten> knotenListeR = new LinkedList<Knoten>();
201
202
203 knotenListeA = trs.expandKnoten(start);
204 System.out.println(knotenListeA.size());
205 for (int a=0; a<knotenListeA.size(); a++)
206 {
207 ka= knotenListeA.get(a);
208 if (ka.compareTo( ziel ) == 0)
209 System.out.println("GEFUNDEN A");
210 knotenListeB = trs.expandKnoten(ka);
211
212 for (int b=0; b<knotenListeB.size(); b++)
213 {
214 kb=knotenListeB.get(b);
215 if (kb.compareTo( ziel ) == 0)
216 System.out.println("GEFUNDEN B");
217 knotenListeC = trs.expandKnoten(kb);
218
219 for (int c=0; c<knotenListeC.size(); c++)
220 {
221 kc=knotenListeC.get(c);
222 if (kc.compareTo( ziel ) == 0)
223 System.out.println("GEFUNDEN C");
224 knotenListeD = trs.expandKnoten(kc);
225
226 for (int d=0; d<knotenListeD.size(); d++)
227 {
228 kd=knotenListeD.get(d);
229 if (kd.compareTo( ziel ) == 0)
230 System.out.println("GEFUNDEN D");
231 knotenListeE = trs.expandKnoten(kd);
232
233 for (int e=0;
234 e<knotenListeE.size(); e++)
235 {
236 ke=knotenListeE.get(e);
237 if (ke.compareTo( ziel ) == 0)
238 System.out.println("GEFUNDEN E");
239 knotenListeF = trs.expandKnoten(ke);
240
241 for (int f=0;
242 f<knotenListeF.size(); f++)
243 {
244
245 kf=knotenListeF.get(f);
246 if (kf.compareTo( ziel ) == 0)
247 System.out.println("GEFUNDEN F");
248 knotenListeG = trs.expandKnoten(kf);
249
250 for (int g=0;
251 g<knotenListeG.size(); g++)
252 {
253
254 kg=knotenListeG.get(g);
255 if (kg.compareTo( ziel ) == 0)
256 System.out.println("GEFUNDEN G");
257
258 knotenListeH = trs.expandKnoten(kg);
259
260 for (int
261 h=0; h<knotenListeH.size(); h++)
262 {
263
264 kh=knotenListeH.get(h);
265
266 if (kh.compareTo( ziel ) == 0)
267 System.out.println("GEFUNDEN H");
268
269 knotenListeI = trs.expandKnoten(kh);
270
271 for
272 (int i=0; h<knotenListeH.size(); h++)
273 {
274 ki=knotenListeI.get(i);
275 if (ki.compareTo( ziel ) == 0)
276 System.out.println("GEFUNDEN I");
277 knotenListeJ = trs.expandKnoten(ki);
278
279 for (int j=0;
280 j<knotenListeJ.size(); j++)
281 {
282 kj=knotenListeJ.get(j);
283 if (kj.compareTo( ziel ) == 0)
284 System.out.println("GEFUNDEN J");
285 knotenListeK = trs.expandKnoten(kj);
286
287 for (int k=0;
288 k<knotenListeK.size(); k++)
289 {
290
291 kk=knotenListeK.get(k);
292 if (kk.compareTo( ziel ) == 0)
293 System.out.println("GEFUNDEN K");
294 knotenListeL =
295 trs.expandKnoten(kk);
296
297 for (int l=0;
298 l<knotenListeL.size(); l++)
299 {
300
301 kl=knotenListeL.get(l);
302 if (kl.compareTo( ziel ) == 0)
303 System.out.println("GEFUNDEN L");
304 knotenListeM =
305 trs.expandKnoten(kl);
306
307 for (int m=0;
308 m<knotenListeM.size(); m++)
309 {
310
311 km=knotenListeM.get(m);
312 if (km.compareTo( ziel ) == 0)
313 System.out.println("GEFUNDEN M");
314 knotenListeN
315 = trs.expandKnoten(km);
316
317 for (int n=0;
318 n<knotenListeN.size(); n++)
319 {
320
321 kn=knotenListeN.get(n);
322 if (kn.compareTo( ziel ) == 0)
323 System.out.println("GEFUNDEN N");
324
325 knotenListeO = trs.expandKnoten(kn);
326
327 for (int o=0; o<knotenListeO.size(); o++)
328 {
329
330 ko=knotenListeO.get(o);
331 if (ko.compareTo( ziel ) == 0)
332 System.out.println("GEFUNDEN O");
333
334 knotenListeP = trs.expandKnoten(ko);
335
336 for
337 (int p=0; p<knotenListeP.size(); p++)
338 {
339
340 kp=knotenListeP.get(p);
341
342 if (kp.compareTo( ziel ) == 0)
343 System.out.println("GEFUNDEN P");
344
345 knotenListeQ = trs.expandKnoten(kp);
346
347
348 for (int q=0; q<knotenListeQ.size(); q++)
349 {
350
351 kq=knotenListeQ.get(q);
352
353 if (kq.compareTo( ziel ) == 0)
354 System.out.println("GEFUNDEN Q");
355
356 knotenListeR = trs.expandKnoten(kq);
357
358
359 for (int r=0; r<knotenListeR.size(); r++)
360
361 {
362
363 kr=knotenListeR.get(r);
364
365 if (kr.compareTo( ziel ) == 0)
366 System.out.println("GEFUNDEN R");
367
368 // knotenListeS = trs.expandKnoten(kr);
369 }
370 }
371 }
372
373 }
374
375 }
376 }
377 }
378 }
379 }
380 }
381 }
382 }
383 }
384 }
385 }
386 }
387 }
388 }
389
390 ////////////////// ENDE TIEFENSUCHE
391 }
392
393 }
394
Compute solutions for the "Schiebespiel" board game