001: #include <assert.h>
002: #include <limits.h>
003: #include <stdio.h>
004: #include <string.h>
005: #include <windows.h>
006: 
007: #include "Point.h"
008: #include "Piece.h"
009: #include "Puzzle.h"
010: 
011: 
012: typedef struct _THREADDATA
013: {
014:         int         ThreadNum;
015:         unsigned __int64* pBox64;
016:         int         adr;
017:         int  rot;
018: }        THREADDATA, *LPTHREADDATA;
019: 
020: 
021: static DWORD ThreadId[2]; 
022: static THREADDATA ThreadData[2];
023: static HANDLE ThreadHandle[2];
024: static HANDLE ReadyEvent[2];
025: static HANDLE ContinueEvent[2];
026: 
027: 
028: CPiece *pPiece[NUMPIECES];                // pointers to the 12 "monkeys"

029: 
030: 
031: extern "C" 
032: {
033:         int tab[3*4*5*NUMPIECES];        // in this table we store pointers were to find our piece data

034:         int Solutions;                                // this is incremented by the SolveIt function

035: 
036:         void SolveIt(unsigned __int64 Box, int FreeForUse, int dummy); // dummy for a nice stackpointer

037: }
038: 
039: 
040: // this is the puzzle definition: the number of cubes and then the cube-coordinates (x,y,z)

041: // we put the "large" parts at the beginning with the hope to cut the tree early

042: static const int Cubes[NUMPIECES] = {6,5,5,5,5,5,5,5,5,4,5,5};
043: static const int Coordinate[MAXNUMCUBES*NUMPIECES*3] =
044: {
045:         0,0,0  ,  1, 0,0  ,  2, 0,0  ,  3, 0,0  ,  0, 1,0  , 2,1,0,
046:         0,0,0  ,  1, 0,0  ,  2, 0,0  ,  3, 0,0  ,  0, 1,0  , 0,0,0,
047:         0,0,0  ,  1, 0,0  ,  2, 0,0  ,  3, 0,0  ,  1, 1,0  , 0,0,0,
048:         0,0,0  ,  1, 0,0  ,  0, 1,0  ,  0, 2,0  ,  1, 2,0  , 0,0,0,
049:         0,0,0  ,  1, 0,0  ,  1, 1,0  ,  1, 2,0  ,  2, 2,0  , 0,0,0,
050:         0,0,0  ,  1, 0,0  ,  0, 1,0  ,  1, 1,0  ,  0, 1,1  , 0,0,0,
051:         0,0,0  ,  1, 0,0  ,  2, 0,0  ,  1, 1,0  ,  1, 2,0  , 0,0,0,
052:         0,0,0  ,  1, 0,0  ,  0, 1,0  ,  1, 1,0  , -1, 1,0  , 0,0,0,
053:         0,0,0  ,  1, 0,0  ,  0, 1,0  , -1, 1,0  , -1, 2,0  , 0,0,0,
054:         0,0,0  ,  1, 0,0  ,  0, 1,0  ,  0, 1,1  ,  0, 0,0  , 0,0,0,
055:         0,0,0  ,  0, 1,0  ,  1, 1,0  , -1, 1,0  , -1, 2,0  , 0,0,0,
056:         0,0,0  ,  0, 1,0  ,  0, 2,0  , -1, 1,0  ,  1, 1,0  , 0,0,0
057: };
058: 
059: 
060: CPuzzle::CPuzzle()
061: {
062:         int adr, PieceNr, HighSymmetryPiece, Min_NumRotations = INT_MAX;
063: 
064:         for (PieceNr = 0; PieceNr < NUMPIECES; PieceNr++)
065:         {
066:                 // create the piece

067:                 pPiece[PieceNr] = new CPiece(Cubes[PieceNr],(int*)&(Coordinate[6*3*PieceNr]));
068: 
069:                 // create all unique rotations of the piece

070:                 pPiece[PieceNr]->CreateRotations();
071: 
072:                 // create the possible translations for the piece in the box

073:                 pPiece[PieceNr]->CreateTranslations();
074: 
075:                 if (PieceNr == ASYMMETRIC_PIECE) 
076:                         AsymmetricPieceTotalRotations = pPiece[PieceNr]->GetTotalNumRotations();
077: 
078:                 int NumRotations = pPiece[PieceNr]->GetNumRotations();
079:                 if (NumRotations < Min_NumRotations)
080:                 {
081:                         Min_NumRotations = NumRotations;
082:                         HighSymmetryPiece = PieceNr;                // the Highsymmetrypiece for this puzzle is "+"

083:                 }
084:         }
085: 
086:         // we exchange the piece with the highest symmetry so that it is the last one

087:         CPiece* pTmp = pPiece[LASTPIECE];
088:         pPiece[LASTPIECE] = pPiece[HighSymmetryPiece];
089:         pPiece[HighSymmetryPiece] = pTmp;
090: 
091:         pPiece[LASTPIECE]->SymmetryElimination();        // avoid a factor of 4 for symmetric solutions

092: 
093:         // calculate the amount of memory needed for the 64bit representations of the pieces 

094:         int Ints_needed = 0;        
095:         for (adr = 0; adr < 60; adr++)
096:         {
097:                 for (PieceNr = 0; PieceNr < NUMPIECES-1; PieceNr++)
098:                 {
099:                         int NumRotations = pPiece[PieceNr]->GetNumRotationsXYZ(adr);
100:                         if (NumRotations > 0)
101:                         {
102:                                 if(adr < 60 - 32) 
103:                                         Ints_needed += 2*NumRotations + 1;        // plus one for the end marker

104:                                 else 
105:                                         // if 32 bits are enough we only use 32 bits of course

106:                                         Ints_needed += NumRotations + 1;
107:                         }
108:                 }
109:         }
110: 
111:         pMem = new int[Ints_needed];
112:         int index = 0;
113: 
114:         // now store the 64Bit piece representations depending on the location in the box 

115:         for (adr = 0; adr < 60; adr++)
116:         {
117:                 for (PieceNr = 0; PieceNr < NUMPIECES-1; PieceNr++)
118:                 {
119:                         int NumRotations = pPiece[PieceNr]->GetNumRotationsXYZ(adr);
120:                         if (NumRotations == 0) 
121:                                 tab[adr*(NUMPIECES-1) + PieceNr] = NULL;
122:                         else
123:                         {
124:                                 tab[adr*(NUMPIECES-1) + PieceNr] = (int)&(pMem[index]);
125:                                 for (int i = 0; i < NumRotations; i++)
126:                                 {
127:                                         unsigned __int64 rot64 = pPiece[PieceNr]->GetRotation64(i,adr) << 4;
128:                                         if (adr < 60 - 32) pMem[index++] = (int)(0xffffffff & rot64);
129:                                         pMem[index++] = (int)(rot64 >> 32);
130:                                 }
131:                                 pMem[index++] = -1;                                // this marks the end of the lists

132:                         }
133:                 }
134:         }
135: }
136: 
137: 
138: CPuzzle::~CPuzzle()
139: {
140:         for (int i = 0; i < NUMPIECES; i++)
141:         {
142:                 delete pPiece[i];
143:         }
144:         delete[] pMem;
145: }
146: 
147: 
148: 
149: static unsigned __int64 Rotate64(unsigned __int64 arg, int wx, int wz)
150: {
151:         // rotate a 64bit Box by angles wx and wz

152:         CPoint point;
153:         unsigned __int64 result = 0, eins = 1;
154:         int x,y,z,adr = 0;        
155: 
156:         for (z = 0; z <= 4; z++)
157:                 for(y = 0; y <= 3; y++)
158:                         for (x = 0; x <= 2; x++)
159:                         {
160:                                 if ((arg & (eins << adr)) != 0)
161:                                 {
162:                                         point.x = x;
163:                                         point.y = y;
164:                                         point.z = z;
165:                                         point.Rotate(wx,0,wz,1.0f, 1.5f, 2.0f);
166:                                         result |= (eins << (point.x + point.y*3 + point.z*12));
167:                                 }        
168:                                 adr++;
169:                         }
170: 
171:         return result;
172: }
173: 
174: 
175: static void SymmetryElimination64(int *NumElements, unsigned __int64 *pBox64)
176: {
177:         // for a list of 64bit boxes eliminate symmetric ones

178:         unsigned __int64 last64, Box64_r, Box64;
179:         int i,index, found_index, NumValues = *NumElements;
180: 
181:         index = 0;
182:         do
183:         {
184:                 Box64 = pBox64[index];
185:                 for (int omega = 1; omega <= 3; omega++)
186:                 {
187:                         int wx = (omega & 1) * 180;
188:                         int wz = (omega >> 1) * 180;
189:                         Box64_r = Rotate64(Box64,wx,wz);
190:                         found_index = -1;
191:                         for (i = 0; (i < NumValues) && (found_index < 0); i++)
192:                         {
193:                                 if (pBox64[i] == Box64_r) found_index = i;
194:                         }
195:                         if (found_index >= 0)
196:                         {
197:                                 last64 = pBox64[NumValues-1];
198:                                 pBox64[found_index] = last64;
199:                 NumValues--;
200:                         }
201:                 }
202:                 index++;
203:         } while (index < NumValues);
204: 
205:         *NumElements = NumValues;
206: }
207: 
208: 
209: 
210: 
211: DWORD ThreadFunc(LPTHREADDATA pData)
212: {
213:         // this is the worker thread function

214:         // it creates all solutions for one position (adr) and rotation (rot) of the

215:         // highsymmetry-piece in the box

216: 
217:         int FreeForUse, adr, adr_2, rot, j, index, ThreadNum;
218:         unsigned __int64 Box64_2, Box64;
219: 
220:         FreeForUse = 0xfff ^ (1L << LASTPIECE);  // a bit "1" means the piece can be used

221:         ThreadNum = pData->ThreadNum;
222: 
223:         do
224:         {
225:                 adr = pData->adr;
226:                 rot = pData->rot;
227: 
228:                 // if symmetric degeneration could happen we add another Piece (ASYMMETRIC_PIECE)

229:                 if (pPiece[LASTPIECE]->GetDegeneration(rot,adr))
230:                 {
231:                         Box64 = pPiece[LASTPIECE]->GetRotation64(rot,adr);
232:                         index = 0;
233:                         for (adr_2 = 0; adr_2 < 60; adr_2++)
234:                         {
235:                                 for (j = 0; j < pPiece[ASYMMETRIC_PIECE]->GetNumRotationsXYZ(adr_2); j++)
236:                                 {        
237:                                         Box64_2 = pPiece[ASYMMETRIC_PIECE]->GetRotation64(j,adr_2);
238:                                         if ((Box64 & Box64_2) == 0) pData->pBox64[index++] = (Box64 | Box64_2);
239:                                 }
240:                         }
241:                         SymmetryElimination64(&index, pData->pBox64);
242:                         for (j = 0; j < index; j++)
243:                                 SolveIt( (pData->pBox64[j] << 4) | 15,FreeForUse ^ (1L << ASYMMETRIC_PIECE),0);
244:                 }
245:                 else
246:                         // if no symmetric degeneration is possible we just start with the piece in the box        

247:                         SolveIt((pPiece[LASTPIECE]->GetRotation64(rot,adr) << 4) | 15,FreeForUse,0);
248: 
249:                 SetEvent(ReadyEvent[ThreadNum]);                        // tell the mother thread that we are ready

250:                 WaitForSingleObject(ContinueEvent[ThreadNum],INFINITE);  
251:                 ResetEvent(ContinueEvent[ThreadNum]);
252: 
253:         } while (true);
254: 
255:         return(0);
256: }
257: 
258: 
259: 
260: 
261: void CPuzzle::Solve()
262: {
263:         int RunningThreads = 0;
264: 
265:         Solutions = 0;
266: 
267:         // we employ two threads to create all solutions (plus the mother thread)

268:         ThreadData[0].pBox64 = new unsigned __int64[AsymmetricPieceTotalRotations];
269:         ThreadData[1].pBox64 = new unsigned __int64[AsymmetricPieceTotalRotations];
270:         ThreadData[0].ThreadNum = 0;
271:         ThreadData[1].ThreadNum = 1;
272:         
273:         ReadyEvent[0] = CreateEvent(NULL,TRUE,FALSE,"Thread0");
274:         ReadyEvent[1] = CreateEvent(NULL,TRUE,FALSE,"Thread1");
275:         ContinueEvent[0]  = CreateEvent(NULL,TRUE,FALSE,"Continue0");
276:         ContinueEvent[1]  = CreateEvent(NULL,TRUE,FALSE,"Continue1");
277: 
278:         for (int adr = 0; adr < 60; adr++)
279:         {
280:                 int NumRotations = pPiece[LASTPIECE]->GetNumRotationsXYZ(adr);
281:                 for (int rot = 0; rot < NumRotations; rot++)
282:                 {
283:                         if (RunningThreads < 2)
284:                         {
285:                                 ThreadData[RunningThreads].adr = adr;
286:                                 ThreadData[RunningThreads].rot = rot;
287:                                 ThreadHandle[RunningThreads] = CreateThread(NULL,0,
288:                                                                                         (LPTHREAD_START_ROUTINE)ThreadFunc,
289:                                                                                         &(ThreadData[RunningThreads]),
290:                                                                                         0,&(ThreadId[RunningThreads]));
291:                                 RunningThreads++;
292:                         }
293:                         else
294:                         {
295:                                 // the motherthread waits until one of the worker threads gets ready

296:                                 DWORD result = WaitForMultipleObjects(2,&(ReadyEvent[0]),FALSE,INFINITE);
297:                                 if( ( result >= WAIT_OBJECT_0) && (result <= WAIT_OBJECT_0 + 1))
298:                                 {
299:                                         int NumReady = result - WAIT_OBJECT_0;
300:                                         // give the thread the next piece address and rotation to work at

301:                                         ThreadData[NumReady].adr = adr;
302:                                         ThreadData[NumReady].rot = rot;
303:                                         ResetEvent(ReadyEvent[NumReady]);
304:                                         printf("%i ",Solutions);
305:                                         SetEvent(ContinueEvent[NumReady]);
306:                                 }
307:                         }
308:                 }
309:         }        
310: 
311:         // wait until both treads are ready        

312:         DWORD result = WaitForMultipleObjects(2,&(ReadyEvent[0]),TRUE,INFINITE);
313: 
314:         TerminateThread(ThreadHandle[0],0);
315:         TerminateThread(ThreadHandle[1],0);
316:         CloseHandle(ThreadHandle[0]);
317:         CloseHandle(ThreadHandle[1]);
318:         delete[]ThreadData[1].pBox64;
319:         delete[]ThreadData[0].pBox64;
320: }