1 /*
  2 
  3  * Grundidee:
  4  * ----------
  5  * 
  6  * Der Puzzle Turm besteht aus 2 konzentrischen Kreisen auf 5 Ebenen.
  7  * Dabei sind die Kreise segmentiert besetzt.
  8  * 
  9  * Äusserer Ring:    besteht aus 12 Segmenten
 10  * Innerer Ring:     1 Segment
 11  * 
 12  * Jedes Puzzle besteht aus einzelnen Segmenten.
 13  * Jede denkbare Segment Position wird {besetzt / frei} pro Puzzle definiert.
 14  * 
 15  * Alle Puzzles werden für alle denkbaren Einbaupositonen gebildet.
 16  * 
 17  * Der gesamte Turm (und alle Puzzles) kann also beschrieben werden in
 18  * einem 5 * (12 + 1) = 65 Bit Array.
 19  * 
 20  * 
 21  * Da heutige Computer nur eine 64 Bit Architektur und java nur diese unterstützt
 22  * erscheint es geeignet zu sein, den Turm als 5*16Bit Struktur abzubilden.
 23  * 
 24  * 1 Puzzle besteht aus einem Array mit 5 Short (16Bit) Elementen.
 25  * 
 26  * 
 27  * oder
 28  * wir ignorieren 1 Segment und rechnen in 64Bit!
 29  * Damit werden die Strukturen einfacher, das setzen und überprüfen ebenfalls.
 30  * Ist der Turm gefüllt muss geprüft werden, ob alle Elemente besetzt sind.
 31  * 
 32  * 
 33  * oder
 34  * wir definieren 2 long variablen pro Puzzle/Turm.
 35  * 
 36  * 
 37  * Stategie:
 38  * Jedes Segment wird sequentiell fortlaufend besetzt, ohne dass Lücken entstehen.
 39  * 
 40  * Segmentierung:
 41  * i ----- aussen -------------      Höhe
 42  * 0 1 2 3 4 5 6 7 8 9 10 11 12      0
 43  * 0 1 2 3 4 5 6 7 8 9 10 11 12      1
 44  * 0 1 2 3 4 5 6 7 8 9 10 11 12      2
 45  * 0 1 2 3 4 5 6 7 8 9 10 11 12      3
 46  * 0 1 2 3 4 5 6 7 8 9 10 11 12      4
 47  * 
 48  * 
 49 
 50 
 51 
 52  */
 53 package jturm;
 54 
 55 import java.util.Arrays;
 56 import java.util.Comparator;
 57 
 58 public class JTurm {
 59 
 60     static int maxPuzzle = 15;
 61     static Puzzle container = null;             // container
 62     static PuzzleShift P[] = new PuzzleShift[maxPuzzle];
 63     static int solCnt = 0;
 64     static int sol[] = new int[maxPuzzle];
 65     static char s[][] = new char[5][13];
 66     static int height = 0;
 67     static boolean unique;              // build unique solutions
 68     static boolean singleSolution;              // build one solution only
 69 
 70     //--------------------------------------------------------------------------
 71     private static int getNextPuzzle(int n) {
 72         // get next puzzle Number, starting from n
 73         for (int i = 0; i < maxPuzzle; i++) {
 74             int x = (n + 1 + i) % maxPuzzle;
 75             if (P[x].inUse == false && P[x].varMax > 0) {
 76                 return x;
 77             }
 78         }
 79         return -1; // ERROR / Solution found
 80     }
 81 
 82     //--------------------------------------------------------------------------
 83     private static void solution() {
 84         StringBuffer sb = new StringBuffer();
 85         solCnt++;
 86 
 87         if (solCnt == 1) {
 88             sb.append("sol\t");
 89             for (int x = 0; x < height; x++) {
 90                 sb.append("  Level = ").append(x).append("\t");
 91             }
 92             for (int i = 0; i < maxPuzzle; i++) {
 93                 if (P[i].var[0].c != '?') {
 94                     sb.append(P[i].var[0].c).append("\t");
 95                 }
 96             }
 97             sb.append("\n");
 98         }
 99 
100         sb.append(solCnt).append("\t");
101         // detailed report
102         for (int i = 0; i < maxPuzzle; i++) {
103             if (P[i].inUse) {
104                 P[i].var[sol[i]].fill(s);
105             }
106         }
107         for (int x = 0; x < height; x++) {
108             sb.append(String.valueOf(s[x])).append("\t");
109         }
110 
111         // short report
112 
113         for (int i = 0; i < maxPuzzle; i++) {
114             if (P[i].inUse) {
115                 sb.append(sol[i]).append("\t");
116             } else {
117                 sb.append(" " + "\t");
118             }
119         }
120 
121 
122         // long report in correct sequence
123 
124         Integer data[][] = new Integer[maxPuzzle][2];
125 
126         System.out.println(sb.toString().trim());
127         if (singleSolution) {
128             System.out.println("\n");
129             for (int i = 0; i < maxPuzzle; i++) {
130                 if (P[i].inUse) {
131                     data[i][0] = P[i].firstBusy[sol[i]];
132                     data[i][1] = i;
133                 } else {
134                     data[i][0] = -1;
135                     data[i][1] = -1;
136                 }
137             }
138             Arrays.sort(data, new Comparator<Integer[]>() {
139                 @Override
140                 public int compare( Integer[] entry1,  Integer[] entry2) {
141                     return entry1[0].compareTo(entry2[0]);
142                 }
143             });
144             for (int x = 0; x < data.length; x++) {
145                 if (data[x][0] >= 0) {
146                     //System.out.println(  data[x][0] + "\t" + data[x][1]);
147                     int i = data[x][1];
148                     P[i].var[sol[i]].disp();
149                 }
150             }
151 
152             System.exit(0);
153         }
154     }
155 
156     //--------------------------------------------------------------------------
157     private static boolean tryIt(int start, int puzzleNbr) {
158         /*
159          * try to insert puzzleNbr into container. If possible, select next free
160          * puzzleNbr and call tryIt.
161          *
162          */
163 
164 
165         boolean canSetThisPuzzle = false;
166         int n = container.getFirstFree();
167         P[puzzleNbr].inUse = true;
168         for (int i = 0; i < P[puzzleNbr].varMax; i++) {
169             if (P[puzzleNbr].firstBusy[i] == n) {            // fillup first whole first   
170 
171                 /*
172                  * if we decide to create unique solutions, then we check here
173                  * the unique rule:
174                  */
175 
176                 //
177                 //  bottom Puzzle    TopPuzzle
178                 //                   not allowed  
179                 //  ----------------------------------
180                 //       A           
181                 //       B               A
182                 //       C               A,B
183                 //       D               A,B,C
184                 //       E               A,B,C,D
185 
186                 if (!(P[puzzleNbr].isTop[i] && puzzleNbr < start) || !unique) {
187 
188                     if (container.add(P[puzzleNbr].var[i])) {   // could be inserted
189                         canSetThisPuzzle = true;
190                         sol[puzzleNbr] = i;
191                         int next = getNextPuzzle(puzzleNbr);
192                         if (container.getFirstFree() < 0 || next < 0) {
193                             solution();
194                         } else {
195                             int firstNext = next;
196                             do {
197                                 if (!tryIt(start, next)) // go deeper
198                                 {
199                                     next = getNextPuzzle(next);  // retry
200                                 }
201                             } while (firstNext != next);
202                         }
203                         container.rem(P[puzzleNbr].var[i]);     // remove this puzzle
204                         canSetThisPuzzle = false;
205                     }
206                 }
207             }
208         }
209         P[puzzleNbr].inUse = false;
210         return canSetThisPuzzle;
211     }
212     //--------------------------------------------------------------------------
213 
214     public static void usage(String info) {
215         System.out.println(info + "\n");
216 
217         System.out.println("1. argument height  (2/3/4/5)");
218         System.out.println("2. argument=unique  (T/F) default=true");
219         System.out.println("3. One Solution     (T/F) default=true");
220         System.exit(1);
221     }
222     //--------------------------------------------------------------------------
223 
224     public static void main(String[] args) {
225         StringBuffer sb = new StringBuffer();
226         singleSolution = true;
227         unique = false;
228         if (args.length < 1) {
229             usage("arguments missing");
230         }
231         height = (int) new Integer(args[0]);
232         if (height < 2 || height > 5) {
233             usage("range check");
234         }
235         if (args.length > 1) {
236             unique = (args[1].charAt(0) == 'T');
237         }
238         if (args.length > 2) {
239             singleSolution = (args[2].charAt(0) == 'T');
240         }
241 
242         sb.append("JTurm, calculate for height=" + height);
243         if (unique) {
244             sb.append(" with unique output");
245         }
246         if (singleSolution) {
247             sb.append(" and list one solution only");
248         }
249 
250         System.out.println(sb.toString());
251         for (int n = 0; n < sb.length(); n++) {
252             System.out.print("-");
253         }
254         System.out.println();
255         // create puzzles
256         Puzzle p[] = new Puzzle[maxPuzzle];
257         for (int x = 0; x < maxPuzzle; x++) {
258             p[x] = new Puzzle(height);
259         }
260 
261         // inner parts
262         p[0].init('A', new int[]{0, 1, 2});
263         p[1].init('B', new int[]{0, 1, 3});
264         p[2].init('C', new int[]{0, 1, 4});
265         p[3].init('D', new int[]{0, 1, 5});
266         p[4].init('E', new int[]{0, 1, 6});
267 
268         // outer parts 2 high
269         p[5].init('a', new int[]{1, 2, 3, 4, 5});
270         p[6].init('b', new int[]{1, 2, 3, 4, 13 + 4});
271         p[7].init('c', new int[]{1, 2, 3, 13 + 3, 13 + 4});
272         p[8].init('d', new int[]{1, 2, 3, 13 + 1, 13 + 3});
273         p[9].init('e', new int[]{1, 2, 3, 4, 13 + 3});
274         p[10].init('f', new int[]{1, 2, 3, 13 + 2, 13 + 3});
275 
276         // outer parts 3 high
277         p[11].init('g', new int[]{1, 2, 3, 13 + 2, 26 + 2});
278         p[12].init('h', new int[]{1, 2, 13 + 2, 26 + 2, 26 + 3});
279         p[13].init('i', new int[]{1, 13 + 1, 13 + 2, 13 + 3, 26 + 2});
280         p[14].init('j', new int[]{1, 13 + 1, 13 + 2, 26 + 2, 26 + 3});
281 
282         System.out.println("setup Puzzle Parts:");
283         // shift + move possibilities
284         for (int x = 0; x < maxPuzzle; x++) {
285             P[x] = new PuzzleShift(p[x], height);
286             if (P[x].var[0].c != '?') {
287                 System.out.println("\tPuzzle " + P[x].var[0].c + "\tvar max=" + P[x].varMax);
288                 //P[x].var[0].disp();
289             }
290 
291         }
292 
293         container = new Puzzle(height);
294         System.out.println("start to create solutions:\n");
295         int maxPuzzleTry = maxPuzzle;
296         if (unique) {
297             maxPuzzleTry = 5 - 1;
298         }
299         for (int x = 0; x < maxPuzzleTry; x++) {
300             int varM = P[x].varMax;             // save
301             if (varM > 0) {
302                 P[x].varMax = 1;                // ignore rotation products
303                 tryIt(x, x);
304                 P[x].varMax = varM;             // restore
305             }
306         }
307 
308 
309     }
310 }
311