001: /*
002: 
003:   File: createSolver.c
004: 
005:   (c) 2003 by Oliver Ehli
006: 
007:      This program is free software; you can redistribute it and/or modify
008:      it under the terms of the GNU General Public License as published by
009:      the Free Software Foundation; either version 2 of the License, or
010:      (at your option) any later version.
011: 
012:      This program is distributed in the hope that it will be useful,
013:      but WITHOUT ANY WARRANTY; without even the implied warranty of
014:      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
015:      GNU General Public License for more details.
016: 
017:      You should have received a copy of the GNU General Public License
018:      along with this program; if not, write to the Free Software
019:      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
020: 
021:      See File LICENSE for more Information.
022: 
023: */
024: #include <stdio.h>
025: #include <time.h>
026: 
027: #define NUM_PCS 12
028: #define START_BIT 4
029: #define NUM_BITS 60
030: #define NUM_HI_BITS 32
031: #define NUM_LO_BITS 32
032: #include "piecePositions.h"
033: #include "createSolver.h"
034: 
035: 
036: 
037: int counter = 0;
038: int leftCounter = 0;
039: int firstNot = -1;
040: int group32[24];
041: long long group[24];
042: int groupLeft32[24];
043: long long groupLeft[24];
044: int partMask[] = {
045:   1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11, 1<<11
046: };
047: 
048: 
049: long long numBits(long long  mix, long long *piece, int pieceNo, int limit)
050: {
051:   long long result = mix & *piece;
052:   int num=0;
053: 
054:   if(*piece == 0ll) return mix;
055: 
056:   for (int i=0; i<64; i++) if(1ll<<i & result) num++;
057: 
058:   if(num>=limit) {
059:     group[counter++] = *piece;
060:     *piece=0ll;
061:   }
062:   else if(firstNot < 0) firstNot = pieceNo;
063: 
064:   return num >= limit ? result : mix;
065: }
066: 
067: 
068: int numBits32(int mix, int *piece, int pieceNo, int limit)
069: {
070:   int result = mix & *piece;
071:   int num=0;
072: 
073:   if(*piece == 0l) return mix;
074: 
075:   for (int i=0; i<32; i++) if(1l<<i & result) num++;
076: 
077:   if(num>=limit) {
078:     group32[counter++] = *piece;
079:     *piece=0l;
080:   }
081: 
082:   else if(firstNot < 0) firstNot = pieceNo;
083: 
084:   return num >= limit ? result : mix;
085: }
086: 
087: 
088: 
089: void writeGroupedPieces(int coord, int piece, char *prefix)
090: {
091:   int k, l;
092:   int groupCounter = 0;
093:   long long bl = -1ll;
094: 
095:   if(positionIndex[piece][coord] > 2) {
096:     while(1) {
097:       if(firstNot >= positionIndex[piece][coord]) break;
098:       for(k=0; k < positionIndex[piece][coord]; k++) {
099:         bl = 1ll<<coord ^ numBits(bl ^ 1ll<<coord, &positions[piece][coord][k], k, 2);
100:       }
101: 
102:       if(counter > 2) {
103:         printf("      if (!(puzzle & 0x%llxll)) {\n", bl);
104:         int l;
105:         for(l=0; l < counter; l++)
106:           printf("         if(!(puzzle & 0x%llxll))\n           %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
107:                  group[l], prefix ? prefix : "", prefix ? "D" : "d", coord+1, 1ll<<(coord+1),
108:                  group[l], partMask[piece]);
109:         printf("      }\n");
110:       }
111:       else {
112:         for(l=0; l < counter; l++)
113:           groupLeft[leftCounter++] = group[l];
114:       }
115:       groupCounter += counter;
116:       counter = 0;
117:       bl = -1ll;
118:       firstNot++;
119:       if(groupCounter == positionIndex[piece][coord]) break;
120:     }
121:     firstNot = -1;
122:     groupCounter = 0;
123:   }
124: 
125:   for(k=0; k < positionIndex[piece][coord]; k++)
126:     if(positions[piece][coord][k] != 0ll)
127:       printf("      if(!(puzzle & 0x%llxll))\n        %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
128:              positions[piece][coord][k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
129:              1ll<<(coord+1), positions[piece][coord][k], partMask[piece]);
130: 
131:   for(k=0; k < leftCounter; k++)
132:       printf("      if(!(puzzle & 0x%llxll))\n        %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
133:            groupLeft[k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
134:            1ll<<(coord+1), groupLeft[k], partMask[piece]);
135: 
136:   firstNot = -1;
137:   counter = 0;
138:   leftCounter = 0;
139: }
140: 
141: 
142: 
143: 
144: void writeGroupedPieces32(int coord, int piece, char *prefix)
145: {
146:   int k, l;
147:   int groupCounter = 0;
148: 
149:   int bl32 = -1l;
150: 
151:   if(positionIndex32[piece][coord] > 2) {
152:     while(1) {
153:       if(firstNot >= positionIndex32[piece][coord]) break;
154:       for(k=0; k < positionIndex32[piece][coord]; k++) {
155:         bl32 = 1l<<coord ^ numBits32(bl32 ^ 1l<<coord, &positions32[piece][coord][k], k, 2);
156:       }
157: 
158:       if(counter > 2) {
159:         printf("      if (!(puzzle & 0x%lxl)) {\n", bl32);
160:         int l;
161:         for(l=0; l < counter; l++)
162:           printf("         if(!(puzzle & 0x%lxl))\n           %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
163:                  group32[l], prefix ? prefix : "", prefix ? "D" : "d", coord+1, 1l<<(coord+1),
164:                  group32[l], partMask[piece]);
165:         printf("      }\n");
166:       }
167:       else {
168:         for(l=0; l < counter; l++)
169:           groupLeft32[leftCounter++] = group32[l];
170:       }
171:       groupCounter += counter;
172:       counter = 0;
173:       bl32 = -1l;
174:       firstNot++;
175:       if(groupCounter == positionIndex32[piece][coord]) break;
176:     }
177:     firstNot = -1;
178:     groupCounter = 0;
179:   }
180: 
181:   for(k=0; k < positionIndex32[piece][coord]; k++)
182:     if(positions32[piece][coord][k] != 0l)
183:       printf("      if(!(puzzle & 0x%lxl))\n        %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
184:              positions32[piece][coord][k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
185:              1l<<(coord+1), positions32[piece][coord][k], partMask[piece]);
186: 
187:   for(k=0; k < leftCounter; k++)
188:     printf("      if(!(puzzle & 0x%lxl))\n        %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
189:            groupLeft32[k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
190:            1l<<(coord+1), groupLeft32[k], partMask[piece]);
191: 
192: 
193:   firstNot = -1;
194:   counter = 0;
195:   leftCounter = 0;
196: }
197: 
198: 
199: 
200: 
201: 
202: 
203: 
204: void writeGroupedAltPieces(int coord, int piece, char *prefix)
205: {
206:   int k, l;
207:   int groupCounter = 0;
208:   long long bl = -1ll;
209: 
210:   if(positionIndex[piece][coord] > 2) {
211:     while(1) {
212:       if(firstNot >= altPositionIndex[piece][coord]) break;
213:       for(k=0; k < altPositionIndex[piece][coord]; k++) {
214:         bl = 1ll<<coord ^ numBits(bl ^ 1ll<<coord, &altPositions[piece][coord][k], k, 2);
215:       }
216: 
217:       if(counter > 2) {
218:         printf("      if (!(puzzle & 0x%llxll)) {\n", bl);
219:         int l;
220:         for(l=0; l < counter; l++)
221:           printf("         if(!(puzzle & 0x%llxll))\n           %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
222:                  group[l], prefix ? prefix : "", prefix ? "D" : "d", coord+1, 1ll<<(coord+1),
223:                  group[l], partMask[piece]);
224:         printf("      }\n");
225:       }
226:       else {
227:         for(l=0; l < counter; l++)
228:           groupLeft[leftCounter++] = group[l];
229:       }
230:       groupCounter += counter;
231:       counter = 0;
232:       bl = -1ll;
233:       firstNot++;
234:       if(groupCounter == altPositionIndex[piece][coord]) break;
235:     }
236:     firstNot = -1;
237:     groupCounter = 0;
238:   }
239: 
240:   for(k=0; k < altPositionIndex[piece][coord]; k++)
241:     if(altPositions[piece][coord][k] != 0ll)
242:       printf("      if(!(puzzle & 0x%llxll))\n        %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
243:              altPositions[piece][coord][k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
244:              1ll<<(coord+1), altPositions[piece][coord][k], partMask[piece]);
245: 
246:   for(k=0; k < leftCounter; k++)
247:       printf("      if(!(puzzle & 0x%llxll))\n        %s%soSolve(%d, 0x%llxll, puzzle | 0x%llxll,\n                   partsUsed | 0x%lxl);\n",
248:            groupLeft[k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
249:            1ll<<(coord+1), groupLeft[k], partMask[piece]);
250: 
251:   firstNot = -1;
252:   counter = 0;
253:   leftCounter = 0;
254: }
255: 
256: 
257: 
258: 
259: void writeGroupedAltPieces32(int coord, int piece, char *prefix)
260: {
261:   int k, l;
262:   int groupCounter = 0;
263: 
264:   int bl32 = -1l;
265: 
266:   if(altPositionIndex32[piece][coord] > 2) {
267:     while(1) {
268:       if(firstNot >= altPositionIndex32[piece][coord]) break;
269:       for(k=0; k < altPositionIndex32[piece][coord]; k++) {
270:         bl32 = 1l<<coord ^ numBits32(bl32 ^ 1l<<coord, &altPositions32[piece][coord][k], k, 2);
271:       }
272: 
273:       if(counter > 2) {
274:         printf("      if (!(puzzle & 0x%lxl)) {\n", bl32);
275:         int l;
276:         for(l=0; l < counter; l++)
277:           printf("         if(!(puzzle & 0x%lxl))\n           %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
278:                  group32[l], prefix ? prefix : "", prefix ? "D" : "d", coord+1, 1l<<(coord+1),
279:                  group32[l], partMask[piece]);
280:         printf("      }\n");
281:       }
282:       else {
283:         for(l=0; l < counter; l++)
284:           groupLeft32[leftCounter++] = group32[l];
285:       }
286:       groupCounter += counter;
287:       counter = 0;
288:       bl32 = -1l;
289:       firstNot++;
290:       if(groupCounter == altPositionIndex32[piece][coord]) break;
291:     }
292:     firstNot = -1;
293:     groupCounter = 0;
294:   }
295: 
296:   for(k=0; k < altPositionIndex32[piece][coord]; k++)
297:     if(altPositions32[piece][coord][k] != 0l)
298:       printf("      if(!(puzzle & 0x%lxl))\n        %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
299:              altPositions32[piece][coord][k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
300:              1l<<(coord+1), altPositions32[piece][coord][k], partMask[piece]);
301: 
302:   for(k=0; k < leftCounter; k++)
303:     printf("      if(!(puzzle & 0x%lxl))\n        %s%soSolve32(%d, 0x%lxl, puzzle | 0x%lxl, partsUsed | 0x%lxl);\n",
304:            groupLeft32[k], prefix ? prefix : "", prefix ? "D" : "d", coord+1,
305:            1l<<(coord+1), groupLeft32[k], partMask[piece]);
306: 
307: 
308:   firstNot = -1;
309:   counter = 0;
310:   leftCounter = 0;
311: }
312: 
313: 
314: 
315: void writeSolver(char *prefix)
316: {
317:   printf("%s%s%s%s%s%s%s", prefix ? "void " : "void ", prefix ? prefix : "", prefix ? "D" : "d", solverStart1,
318:          prefix ? prefix : "", prefix ? "D" : "d", solverStart2);
319: 
320:   printf("  switch(start) {\n");
321: 
322:   int i;
323:   for(i=START_BIT; i<NUM_LO_BITS; i++) {
324:     int j=0;
325:     while(++j < NUM_PCS+1 && !positionIndex[j][i]);
326: 
327:     if(j==NUM_PCS+1) continue;
328:     if(j==NUM_PCS && !prefix) continue;
329:     if(j==NUM_PCS-1 && prefix && !positionIndex[NUM_PCS][i]) continue;
330: 
331:     printf("   case %d:\n", i);
332:     for(; j<NUM_PCS+1; j++) {
333:       if(j==NUM_PCS && !prefix) continue;
334:       if(j==NUM_PCS-1 && prefix) continue;
335: 
336:       if(positionIndex[j][i]) {
337:         printf("      if (partsUsed & 0x%lxl) goto %spiece%dat%d;\n",
338:                partMask[j], prefix ? prefix : "", j+1, i);
339:         if(prefix)
340:           writeGroupedAltPieces(i, j, prefix);
341:         else
342:           writeGroupedPieces(i, j, prefix);
343:          printf("    %spiece%dat%d:\n", prefix ? prefix : "", j+1, i);
344:       }
345:     }
346:     printf("    break;\n");
347:   }
348: 
349:   printf("  }\n");
350:   printf("}\n\n\n");
351: }
352: 
353: 
354: void writeSolver32(char *prefix)
355: {
356:   printf("%s%s%s%s", prefix ? "void " : "void ", prefix ? prefix : "", prefix ? "D" : "d", solver32Start);
357: 
358:   printf("  switch(start) {\n");
359: 
360:   int i;
361:   for(i=0; i<NUM_HI_BITS; i++) {
362:     int j=0;
363:     while(++j < NUM_PCS+1 && !positionIndex32[j][i]);
364: 
365:     if(j==NUM_PCS+1) continue;
366:     if(j==NUM_PCS && !prefix) continue;
367:     if(j==NUM_PCS-1 && prefix && !positionIndex32[NUM_PCS][i]) continue;
368: 
369:     printf("   case %d:\n", i);
370:     for(; j<NUM_PCS+1; j++) {
371:       if(j==NUM_PCS && !prefix) continue;
372:       if(j==NUM_PCS-1 && prefix) continue;
373: 
374:       if(positionIndex32[j][i]) {
375:         printf("      if (partsUsed & 0x%lxl) goto %spiece%dat%dat32;\n",
376:                partMask[j], prefix ? prefix : "", j+1, i);
377:         if(prefix)
378:           writeGroupedAltPieces32(i, j, prefix);
379:         else
380:           writeGroupedPieces32(i, j, prefix);
381:          printf("    %spiece%dat%dat32:\n", prefix ? prefix : "", j+1, i);
382:       }
383:     }
384:     printf("    break;\n");
385:   }
386: 
387:   printf("  }\n");
388:   printf("}\n\n\n");
389: }
390: 
391: 
392: 
393: int main(int argc, char** argv)
394: {
395:   int i;
396: 
397:   printf(solver_head);
398: 
399:   printf("\n\nvoid solve()\n{\n");
400:   for(i=0; i < 8; i++)
401:     printf("  doSolve(4, 1<<4, 0x%llxll, 0x%lxl);\n",
402:            piece0Positions[i] << 4, partMask[0]);
403:   for(i=8; i < piece0NumPositions; i++)
404:     printf("  altDoSolve(4, 1<<4, 0x%llxll, 0x%lxl);\n",
405:            piece0Positions[i] << 4, partMask[0]);
406:   printf("\n}\n\n\n");
407: 
408: 
409:   writeSolver(0);
410:   writeSolver32(0);
411: 
412:   writeSolver("alt");
413:   writeSolver32("alt");
414: }