001: package de.anifun3.ctpuzzle;
002: 
003: import javax.vecmath.*;
004: import java.util.Vector;
005: import java.text.DecimalFormat;
006: import java.io.*;
007: import javax.media.j3d.Transform3D;
008: 
009: /**
010:  * Diese Klasse repraesentiert den Loesungsalgorithmus.
011:  * Erstellungsdatum: (29.03.2003 14:54:37)
012:  * @author: Oliver Faulhaber
013:  */
014: public class Puzzle implements Runnable
015: {
016:         // Thread, der die Loesungen auf der Konsole ausgibt
017:         private Thread           ivPaintThread     = null;
018: 
019:         // Stoppflag fuer den Thread
020:         private boolean          ivStopped         = false;
021:         
022:    // Zaehler fuer Kombinationen
023:         private long             ivCombCount       = 0;
024: 
025:         // Startzeit der Berechnung
026:         private long             ivStartTime       = 0;
027:         
028:         // die zwoelf Puzzleteile
029:         private Part[]           ivParts           = null;
030: 
031:         // das Spielfeld,
032:         private long             ivField           = 0;
033:         private int[][][]        ivPrintField      = null;
034:         public static int[]      ivSearchOrder     = null;
035: 
036:         // Bitvektor fuer ein lueckenlos gefuelltes Spielfeld
037:         private long             ivSolvedField     = 0;
038: 
039:         // Die gefundenen Loeseungen
040:         private Transform3D[][]  ivSolutions       = null;
041:         private int              ivSolvCount       = 0;
042:         private int              ivMasterSolv      = 0;
043: 
044:         // Position der Beschriftung
045:         private long             ivCMasterPos      = 0;
046:         private long             ivTMasterPos      = 0;
047:         private long             ivAMasterPos      = 0;
048: 
049:         // Dieses Flag bestimmt, ob Loesungen auf der Konsole ausgegeben werden sollen
050:         // Bei manchen Prozessen mit begrenzten Konsolen-Puffergroessen koennte das zu 
051:         // Problemen fuehren.
052:         private boolean          ivIsSilent        = false;
053: 
054:         private boolean          ivModal           = true;
055: 
056:         // Text-Formatierungsobjekte
057:         private DecimalFormat    ivFieldFormat     = null;
058:         private DecimalFormat    ivCombFormat      = null;
059: 
060:         // Abmessungen des "Spielfelds"
061:         public static final int  X                 = 5;
062:         public static final int  Y                 = 3;
063:         public static final int  Z                 = 4;
064:         public static final int  NUM_PARTS         = 12;
065:         public static final int  MAX_FIELDS        = X*Y*Z;
066: 
067:         // Variablen, die zur (hoffentlich) Performance-Steigerung hier angelegt werden
068:         private int  ivpI = 0;
069: /**
070:  * Puzzle - Konstruktorkommentar.
071:  */
072: public Puzzle() 
073: {
074:         this( false, true );
075: }
076: /**
077:  * Puzzle - Konstruktorkommentar.
078:  */
079: public Puzzle( boolean silent, boolean modal ) 
080: {
081:         super();
082:         ivIsSilent = silent;
083:         ivModal    = modal;
084: 
085:         // Initialisieren der Objekte
086:         ivParts       = new Part[NUM_PARTS];
087:         ivField       = 0;
088:         ivPrintField  = new int[X][Y][Z];
089:         ivSolutions   = new Transform3D[409963][ivParts.length];
090:         ivSearchOrder = new int[MAX_FIELDS+1];
091: 
092:         // Alle Felder belegen
093:         ivSolvedField = 0;
094:         for( int i=0; i<(X*Y*Z); i++)
095:                 ivSolvedField |= (long)1 << i;
096: 
097:         // Text-Formatierungsobjekt fuer die Ausgabe der Puzzle-Felder. Einstellige Zahlen sollen
098:         // mit einer voramgehenden '0' ausgegeben werden
099:         ivFieldFormat = new java.text.DecimalFormat();
100:         ivFieldFormat.setMinimumIntegerDigits(2);
101:         ivFieldFormat.setMinimumFractionDigits(0);
102: 
103:         // Text-Formatierungsobjekt fuer die Ausgabe der Kombinationen-Zahl. Hier sorgt die
104:         // Gruppierung in Tausender fuer bessere Lesbarkeit.
105:         ivCombFormat = new java.text.DecimalFormat();
106:         ivCombFormat.setGroupingUsed(true);
107:         ivCombFormat.setMinimumFractionDigits(0);
108: 
109:         // Erstellen der Puzzleteile
110:         initParts();
111: }
112: /**
113:  * Liefert die Anzahl der untersuchten Kombinationen
114:  * Erstellungsdatum: (04.04.2003 14:02:18)
115:  * @return long
116:  */
117: public long getComboCount() 
118: {
119:         return ivCombCount;
120: }
121: /**
122:  * Die Beschreibung der Methode hier eingeben.
123:  * Erstellungsdatum: (10.04.2003 12:33:29)
124:  * @return int
125:  */
126: public int getMasterSolution() 
127: {
128:         return ivMasterSolv;
129: }
130: /**
131:  * Liefert das Array aller Puzzleteile
132:  * Erstellungsdatum: (30.03.2003 15:56:05)
133:  * @return de.anifun3.ctpuzzle.Part[]
134:  */
135: public Part[] getParts() 
136: {
137:         return ivParts;
138: }
139: /**
140:  * Liefert die entsprechende Lösung zurueck
141:  * Erstellungsdatum: (04.04.2003 14:00:23)
142:  * @return Transform3D[]
143:  * @param index int
144:  */
145: public Transform3D[] getSolution(int index) 
146: {
147:         if( index < ivSolvCount && index >= 0)
148:                 return ivSolutions[index];
149:         return null;
150: }
151: /**
152:  * Liefert die Anzahl bereits berechneter Loesungen zurueck
153:  * Erstellungsdatum: (04.04.2003 13:59:33)
154:  * @return int
155:  */
156: public int getSolutionsCount() 
157: {
158:         return ivSolvCount;
159: }
160: /**
161:  * Liefert die Dauer der Berechnung in Millisekunden
162:  * Erstellungsdatum: (04.04.2003 14:01:32)
163:  * @return long
164:  */
165: public long getTime() 
166: {
167:         return System.currentTimeMillis() - ivStartTime;
168: }
169: /**
170:  * Liefert die Dauer als String zurueck
171:  * Erstellungsdatum: (04.04.2003 14:07:27)
172:  * @return java.lang.String
173:  */
174: public String getTimeString() 
175: {
176:         long dur  = getTime();
177:         int  hour = (int)dur / 3600000;
178:         dur       = dur - 3600000*hour;
179:         int  min  = (int)dur / (60000);
180:         dur       = dur - (60000*min);
181:         int  sec  = (int)dur / 1000;
182:         
183:         return ivFieldFormat.format(hour) + ":" + ivFieldFormat.format(min) + ":" + ivFieldFormat.format(sec);
184: }
185: /**
186:  * Initialisiert die Puzzleteile. Die 60 Felder des Puzzles werden im anfolgenden
187:  * Kommentar eindeutig vergeben. Das erste Feld liegt im Nullpunkt des Koordinaten-
188:  * Systems (hinten, links, unten). Das 60. Feld liegt demnach rechts, vorne oben.
189:  * Im Konstruktor eines Bauteils, werden die Felder spezifiziert, die es belegt. Zur 
190:  * Synchronisation mit der grafischen Ausgabe des Puzzles gilt die Konvention, dass
191:  * jedes Part an den Achsen des Koordinatensystems anliegen muss. Der Pivot fuer alle
192:  * Bauteile ist (0/0/0).
193:  * Erstellungsdatum: (29.03.2003 14:57:58)
194:  */
195: private void initParts() 
196: {
197:         // Reihenfolge festlegen, in der das Puzzle durchlaufen wird
198:         ////////////////////////////////////////////////////////////
199:         int field = 0;
200:         // "Kurze Achsen" zuerst
201:         for( int x=0; x<X; x++ )
202:                 for( int z=Z-1; z>=0; z--)
203:                         for( int y=0; y<Y; y++ )
204:                                 ivSearchOrder[field++] = x + z*Puzzle.X + y*Puzzle.X*Puzzle.Z;
205: 
206:         //    41 42 43 44 45  
207:         //   46 47 48 49 50
208:         //  51 52 53 54 55
209:         // 56 57 58 59 60
210:         //
211:         //    21 22 23 24 25
212:         //   26 27 28 29 30
213:         //  31 32 33 34 35
214:         // 36 37 38 39 40
215:         //
216:         //    01 02 03 04 05
217:         //   06 07 08 09 10
218:         //  11 12 13 14 15
219:         // 16 17 18 19 20
220:         //
221:         ivParts[0]  = new Part( new int[]{ 1,2,21,41,42 } );
222:         ivParts[1]  = new Part( new int[]{ 1,2,22,42,43 } );
223:         ivParts[2]  = new Part( new int[]{ 16,17,12,7,2 } );
224:         ivParts[3]  = new Part( new int[]{ 16,11,06,07,1 } );
225:         ivParts[4]  = new Part( new int[]{ 1,6,21,26,7 } );
226:         ivParts[5]  = new Part( new int[]{ 1,2,3,7,12 } );
227:         ivParts[6]  = new Part( new int[]{ 2,6,7,11,12 }, true );
228:         ivParts[7]  = new Part( new int[]{ 11,12,7,8,3 } );
229:         ivParts[8]  = new Part( new int[]{ 21,26,27,7 });
230:         ivParts[9]  = new Part( new int[]{ 2,7,8,12,11 } );
231:         ivParts[10] = new Part( new int[]{ 2,6,7,8,12 } );
232:         ivParts[11] = new Part( new int[]{ 16,17,11,6,7,1 } );
233: 
234:         // Masterpositionen fuer die Beschriftung erstellen
235:         long v = 1;
236:         ivCMasterPos = v<<55 | v<<56 | v<<50 | v<<45 | v<<46;
237:         ivTMasterPos = v<<58 | v<<59 | v<<53 | v<<48 | v<<43 | v<<49;
238:         ivAMasterPos = v<<42 | v<<47 | v<<22 | v<<27 | v<<28;
239: }
240: /**
241:  * Gibt die Belegung des Spielfelds auf der Konsole aus.
242:  * Erstellungsdatum: (31.03.2003 09:39:41)
243:  */
244: public void printField() 
245: {
246:         for( int y=Y-1; y>=0; y--)
247:         {
248:                 for( int z=0; z<Z; z++)
249:                 {
250:                         for( int w = 0; w<Z-z; w++ ) System.out.print(" ");
251:                         
252:                         for( int x=0; x<X; x++)
253:                         {
254:                                 if (ivPrintField[x][y][z] == -1 )
255:                                         System.out.print( "xx " );
256:                                 else
257:                                         System.out.print( ivFieldFormat.format( ivPrintField[x][y][z] +1 ) + " " );
258:                         }
259:                         System.out.println(" ");
260:                 }
261:                 System.out.println(" ");
262:         }
263: 
264:         String mastersolv = (ivMasterSolv >0 ) ? ""+ivMasterSolv : "-";
265:         System.out.println("Combos   : " + ivCombFormat.format(ivCombCount));
266:         System.out.println("Solutions: " + ivSolvCount + " ("+ mastersolv +")");
267:         System.out.println("Time     : " + getTimeString());
268:         System.out.println("Solv/sec : " + ivSolvCount/(getTime()/1000) );
269:         System.out.println("Comb/sec : " + ivCombFormat.format(ivCombCount/(getTime()/1000)));
270:         System.out.println("---");
271: }
272: /**
273:  * Setzt die Berechnugs-Objekte in den Startzustand zurueck
274:  * Erstellungsdatum: (29.03.2003 15:18:06)
275:  */
276: public void reset() 
277: {
278:         int i;
279: 
280:         // Spielfeld "leeren"
281:         ivField = 0;
282: 
283:         // Used-Parts leeren
284:         for( i=0; i<ivParts.length; i++)
285:                 ivParts[i].setIsUsed(false);
286: 
287:         // Print-Field zuruecksetzen
288:         for( int x=0; x<ivPrintField.length; x++)
289:                 for( int y=0; y<ivPrintField[x].length; y++)
290:                         for( int z=0; z<ivPrintField[x][y].length; z++)
291:                                 ivPrintField[x][y][z] = -1;
292: 
293:         // Speicher fuer die Loesungen
294:         ivSolvCount  = 0;
295:         ivMasterSolv = 0;
296: 
297:         // Kombinations-Zaehler
298:         ivCombCount  = 0;
299: }
300: /**
301:  * Die Beschreibung der Methode hier eingeben.
302:  * Erstellungsdatum: (08.04.2003 15:39:53)
303:  */
304: public void run() 
305: {
306:         while ( !ivStopped )
307:         {
308:                 synchronized (ivPaintThread) 
309:                 {
310:                         try
311:                         {
312:                                 // alle 10 sec.
313:                                 ivPaintThread.wait(10000);
314:                         }
315:                         catch( InterruptedException e )
316:                         {
317:                                 e.printStackTrace();
318:                         }
319: 
320:                         // Spielfeld ausgeben
321:                         printField();
322:                 }
323:         }
324: }
325: /**
326:  * Die Beschreibung der Methode hier eingeben.
327:  * Erstellungsdatum: (11.04.2003 15:54:28)
328:  */
329: public void saveResult() 
330: {
331:         try
332:         {
333:                 Matrix3f         m   = new Matrix3f();
334:                 DataOutputStream out = new DataOutputStream( 
335:                                           new BufferedOutputStream( 
336:                                                   new FileOutputStream(new File("ctpuzzle.dat"))) );
337: 
338:                 for( int i=0; i<ivSolvCount; i++)
339:                 {
340:                         for( int y=0; y<ivSolutions[0].length; y++ )
341:                         {
342:                                 ivSolutions[i][y].get(m);
343:                                 out.writeFloat( m.m00 );
344:                                 out.writeFloat( m.m01 );
345:                                 out.writeFloat( m.m02 );
346:                                 out.writeFloat( m.m10 );
347:                                 out.writeFloat( m.m11 );
348:                                 out.writeFloat( m.m12 );
349:                                 out.writeFloat( m.m20 );
350:                                 out.writeFloat( m.m21 );
351:                                 out.writeFloat( m.m22 );
352:                         }
353:                 }
354:                 out.flush();
355:                 out.close();
356:         }
357:         catch( Exception e)
358:         {
359:                 e.printStackTrace();
360:         }
361: }
362: /**
363:  * Startet den Berechnungsvorgang
364:  * Erstellungsdatum: (29.03.2003 15:14:38)
365:  */
366: public void solve() 
367: {
368:         // Ausgabe der Thread-Prioritaet
369:         // System.out.println( "Thread-Priority: " + Thread.currentThread().getPriority() + " ("+Thread.MIN_PRIORITY+","+Thread.NORM_PRIORITY+","+Thread.MAX_PRIORITY+")");
370:         
371:         // Spielfeld zuruecksetzen
372:         reset();
373: 
374:         // Startzeit initialisieren
375:         ivStartTime = System.currentTimeMillis();
376: 
377:         // Paint-Thread starten
378:         if( !ivIsSilent )
379:         {
380:                 ivStopped     = false;
381:                 ivPaintThread = new Thread( this, "PuzzlePainter");
382:                 ivPaintThread.setPriority( Thread.currentThread().getPriority() );
383:                 ivPaintThread.start();
384:         }
385:         
386:         // Ausfuehren der rekursiven Methode mit Feld #1
387:         solve(0);
388: 
389:         // Paint-Thread anhalten
390:         ivStopped = true;
391: 
392:         // Ausgabe der Anzahl gefundener Loesungen
393:         System.out.println("SOLUTIONS TOTAL: " + ivSolvCount);
394: }
395: /**
396:  * Rekursive Methode zur Berechnung der Aufgabe
397:  * Erstellungsdatum: (31.03.2003 08:22:48)
398:  * @param field int
399:  */
400: private void solve(int field) 
401: {
402:         // Fuer Debug-Zwecke
403:         // if( ivSolvCount >= 10000) return;
404:                 
405:         // Anderen Threads Gelegenheit zur Ausfuehrung geben
406: //        if( !ivModal )
407: //                Thread.yield();
408:                                         
409:         // Ist eine Loesung gefunden?
410:         if( ivField == ivSolvedField)
411:         {
412:                 for( int i=0; i<ivParts.length; i++)
413:                 {
414:                         // Die Loesung abspeichern
415:                         if( ivSolvCount<ivSolutions.length) // "Kindersicherung"
416:                                 ivSolutions[ivSolvCount][i] = ivParts[i].ivUnit.transform;
417:                         
418:                         // Die Felder des print-Fields belegen
419:                         if( !ivIsSilent )
420:                                 for( int y=0; y<ivParts[i].ivUnit.geometry.length; y++)
421:                                         ivPrintField [ivParts[i].ivUnit.geometry[y].x]
422:                                                      [ivParts[i].ivUnit.geometry[y].y]
423:                                                      [ivParts[i].ivUnit.geometry[y].z] = (byte)i;
424:                 }
425: 
426:                 // Ist das die "Masterloesung"?
427:                 if(    ivParts[0].ivUnit.fields                == ivCMasterPos
428:                     && ivParts[ivParts.length-1].ivUnit.fields == ivTMasterPos
429:                     && ivParts[4].ivUnit.fields                == ivAMasterPos
430:                   )
431:                         ivMasterSolv = ivSolvCount;
432:                         
433:                 ivSolvCount++;
434:                 return;
435:         }
436: 
437:         long fieldBits = (long)1<<ivSearchOrder[field];
438:         
439:         // Ist das Feld schon belegt?
440:         if( ((fieldBits) & ivField) != 0)
441:         {
442:                 // Mit dem naechsten Feld weitermachen (Rekursion)
443:                 solve( field+1 );
444:                 return;
445:         }
446: 
447:         Projections.Unit[] units;
448:         Projections.Unit   unit;
449:         Part               part;
450:         
451:         // Suche ein Bauteil, welches dieses Feld ausfuellt.
452:         // Probiere alle freien Bauteile
453:         for( int i=0; i<ivParts.length; i++)
454:         {
455:                 part = ivParts[i];
456:                 if( !part.ivIsUsed )
457:                 {
458:                         // Alle Ausrichtungen des Bauteils probieren, deren Unterkante auf dieser Ebene 
459:                         // liegt und die dieses Feld belegen
460:                         units = part.ivProjections.ivMovedProjections[field];
461:                         for( int w=0; w<units.length; w++)
462:                         {
463:                                 unit = units[w];
464:                                 
465:                                 // Gibt es eine Ueberlappung?
466:                                 if( ((ivField  & unit.fields) == 0) )
467:                                 {
468:                                         // Nein --> Das Bauteil passt hinein. -> Die Felder des Puzzles belegen und das Bauteil
469:                                         // als benutzt markieren
470:                                         ivField       |= unit.fields;
471:                                         part.ivIsUsed  = true;
472:                                         part.ivUnit    = unit;
473:                                         ivCombCount++;
474: 
475:                                         // Debug-Ausgabe
476:                                         // printField();
477: 
478:                                         // Das Bauteil wurde abgelegt. Mit dem naechsten Feld weitermachen (Rekursion)
479:                                         solve(field+1);
480: 
481:                                         // Das abgelegte Bauteil wieder entfernen, damit weitere Loesungen gesucht werden
482:                                         // koennen.
483:                                         ivField = ivField ^ unit.fields;
484:                                         part.ivIsUsed = false;
485: 
486:                                 }
487:                         }
488:                 }
489:         }
490: }
491: }