|
1 #include <stdio.h> |
|
2 #include <string.h> |
|
3 |
|
4 #define BOX '$' |
|
5 #define WALL '#' |
|
6 #define MAN '@' |
|
7 #define PLATFORM '.' |
|
8 #define BOXINPLATFORM '*' |
|
9 #define MANINPLATFORM 'E' |
|
10 #define BLANK ' ' |
|
11 #define CANTO '-' |
|
12 #define MANCANMOVE '+' |
|
13 |
|
14 #define NBOX(n) ((n)<<2) |
|
15 |
|
16 #define DIR_LEFT 0 |
|
17 #define DIR_RIGHT 1 |
|
18 #define DIR_UP 2 |
|
19 #define DIR_DOWN 3 |
|
20 |
|
21 #define MAX_X 50 |
|
22 #define MAX_Y 50 |
|
23 #define MAX_MOVES 50 |
|
24 #define MAX_MANMOVES 50 |
|
25 #define MAX_BOXES 15 |
|
26 |
|
27 #define MOVE_OK 1 |
|
28 #define MOVE_BOX 2 |
|
29 #define MOVE_ILLEGAL 0 |
|
30 |
|
31 /* SOKOBAN Solution Finder |
|
32 * |
|
33 * Cerca totes les possibilitats de tots els nombres de combinacions possibles, |
|
34 * menys la que tots els moviments són a l'esquerra del número de combinacions |
|
35 * incials triat. |
|
36 |
|
37 * 13/01/2002 |
|
38 * Comentari afegit el 4/01/2003: |
|
39 * Cerca la solució segons el moviment de caixes, i no el de l'home. |
|
40 * Falta optimitzar: Llocs on no posar caixes segons les caixes (són dinàmics |
|
41 * segons cada element de l'array de mapes!) |
|
42 * |
|
43 * Diria que el programa no es deixa cap branca de l'arbre de backtracking |
|
44 */ |
|
45 |
|
46 |
|
47 struct Map |
|
48 { |
|
49 char Cells[MAX_Y][MAX_X]; |
|
50 char ManMoves[MAX_Y][MAX_X]; |
|
51 int SizeX, SizeY; |
|
52 int ManX, ManY; |
|
53 int NumPlatforms; |
|
54 int NumBoxesInPlatform; |
|
55 int BoxX[MAX_BOXES]; |
|
56 int BoxY[MAX_BOXES]; |
|
57 int NumBoxes; |
|
58 }; |
|
59 |
|
60 |
|
61 void CopyMap (struct Map *Mdest, struct Map *Morig) |
|
62 { |
|
63 memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); |
|
64 } |
|
65 |
|
66 |
|
67 void ReadMap(struct Map *M, char *FileName) |
|
68 { |
|
69 FILE *Fitxer; |
|
70 int i,j; |
|
71 |
|
72 if(!(Fitxer = fopen(FileName, "r"))) |
|
73 { |
|
74 printf("Error opening %s!", FileName); |
|
75 exit(1); |
|
76 } |
|
77 |
|
78 M->SizeX=0; |
|
79 M->SizeY=0; |
|
80 while (!feof(Fitxer)) |
|
81 { |
|
82 fgets(M->Cells[M->SizeY], MAX_X, Fitxer); |
|
83 M->SizeY++; |
|
84 } |
|
85 M->SizeY--; |
|
86 M->SizeX = strlen(M->Cells[0]) - 1; |
|
87 |
|
88 M->NumPlatforms = 0; |
|
89 M->NumBoxesInPlatform = 0; |
|
90 M->NumBoxes = 0; |
|
91 for (j = 0; j<M->SizeY; j++) |
|
92 for (i=0; i<M->SizeX; i++) |
|
93 { |
|
94 if (M->Cells[j][i] == MAN) |
|
95 { |
|
96 M->ManX = i; M->ManY = j; |
|
97 M->Cells[M->ManY][M->ManX] = BLANK; |
|
98 } |
|
99 |
|
100 if (M->Cells[j][i] == PLATFORM) |
|
101 M->NumPlatforms++; |
|
102 else if (M->Cells[j][i] == BOXINPLATFORM) |
|
103 { |
|
104 M->Cells[j][i] = PLATFORM; |
|
105 |
|
106 M->NumPlatforms++; |
|
107 M->NumBoxesInPlatform++; |
|
108 |
|
109 M->BoxX[M->NumBoxes] = i; |
|
110 M->BoxY[M->NumBoxes] = j; |
|
111 M->NumBoxes++; |
|
112 } else if (M->Cells[j][i] == BOX) |
|
113 { |
|
114 M->Cells[j][i] = BLANK; |
|
115 |
|
116 M->BoxX[M->NumBoxes] = i; |
|
117 M->BoxY[M->NumBoxes] = j; |
|
118 M->NumBoxes++; |
|
119 } else if (M->Cells[j][i] != WALL) |
|
120 { |
|
121 if ( (M->Cells[j][i-1] == WALL && |
|
122 M->Cells[j-1][i] == WALL) || |
|
123 (M->Cells[j][i-1] == WALL && |
|
124 M->Cells[j+1][i] == WALL) || |
|
125 (M->Cells[j][i+1] == WALL && |
|
126 M->Cells[j-1][i] == WALL) || |
|
127 (M->Cells[j][i+1] == WALL && |
|
128 M->Cells[j+1][i] == WALL)) |
|
129 M->Cells[j][i] = CANTO; |
|
130 } |
|
131 |
|
132 } |
|
133 |
|
134 if(M->NumBoxes > M->NumPlatforms) |
|
135 { |
|
136 printf("More boxes than platforms!\n"); |
|
137 exit(2); |
|
138 } |
|
139 } |
|
140 |
|
141 |
|
142 void ShowMap (struct Map *M) |
|
143 { |
|
144 struct Map Temp; |
|
145 int i,j; |
|
146 |
|
147 CopyMap(&Temp, M); |
|
148 |
|
149 Temp.Cells[Temp.ManY][Temp.ManX] = MAN; |
|
150 |
|
151 for (i = 0; i < Temp.NumBoxes; i++) |
|
152 { |
|
153 if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == BLANK) |
|
154 Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX; |
|
155 else if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM) |
|
156 Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM; |
|
157 } |
|
158 |
|
159 for (j = 0; j<Temp.SizeY; j++) |
|
160 { |
|
161 for (i=0; i<Temp.SizeX; i++) |
|
162 printf("%c", Temp.Cells[j][i]); |
|
163 printf("\n"); |
|
164 } |
|
165 // Print Where the man can move |
|
166 for (j = 0; j<Temp.SizeY; j++) |
|
167 { |
|
168 for (i=0; i<Temp.SizeX; i++) |
|
169 printf("%c", Temp.ManMoves[j][i]); |
|
170 printf("\n"); |
|
171 } |
|
172 |
|
173 printf("Man is at (%i,%i)\n", Temp.ManX, Temp.ManY); |
|
174 printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms, |
|
175 Temp.NumBoxesInPlatform); |
|
176 } |
|
177 |
|
178 |
|
179 |
|
180 int InverseMove(char Dir1, char Dir2) |
|
181 { |
|
182 if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) || |
|
183 (Dir1 + Dir2 == DIR_UP + DIR_DOWN)) |
|
184 return 1; |
|
185 return 0; |
|
186 } |
|
187 |
|
188 |
|
189 void GetManMoves(struct Map *M) |
|
190 { |
|
191 int X[MAX_MANMOVES], Y[MAX_MANMOVES]; |
|
192 int NewX[MAX_MANMOVES], NewY[MAX_MANMOVES]; |
|
193 int NumMoves, NewMoves; |
|
194 int j, i; |
|
195 |
|
196 NumMoves = 1; |
|
197 for (j = 0; j<M->SizeY; j++) |
|
198 for (i=0; i<M->SizeX; i++) |
|
199 M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK; |
|
200 for (i = 0; i<M->NumBoxes; i++) |
|
201 M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL; |
|
202 |
|
203 NewMoves = 1; |
|
204 NewX[0] = M->ManX; |
|
205 NewY[0] = M->ManY; |
|
206 M->ManMoves[M->ManY][M->ManX] = MANCANMOVE; |
|
207 while (NewMoves) |
|
208 { |
|
209 NumMoves = NewMoves; |
|
210 for (i=0; i<NewMoves; i++) |
|
211 { |
|
212 X[i] = NewX[i]; |
|
213 Y[i] = NewY[i]; |
|
214 } |
|
215 NewMoves = 0; |
|
216 for (i=0; i<NumMoves; i++) |
|
217 { |
|
218 if(M->ManMoves[Y[i]][X[i]-1] == BLANK) |
|
219 { |
|
220 NewX[NewMoves] = X[i]-1; |
|
221 NewY[NewMoves] = Y[i]; |
|
222 M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE; |
|
223 NewMoves++; |
|
224 } |
|
225 if(M->ManMoves[Y[i]][X[i]+1] == BLANK) |
|
226 { |
|
227 NewX[NewMoves] = X[i]+1; |
|
228 NewY[NewMoves] = Y[i]; |
|
229 M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE; |
|
230 NewMoves++; |
|
231 } |
|
232 if(M->ManMoves[Y[i]-1][X[i]] == BLANK) |
|
233 { |
|
234 NewX[NewMoves] = X[i]; |
|
235 NewY[NewMoves] = Y[i]-1; |
|
236 M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE; |
|
237 NewMoves++; |
|
238 } |
|
239 if(M->ManMoves[Y[i]+1][X[i]] == BLANK) |
|
240 { |
|
241 NewX[NewMoves] = X[i]; |
|
242 NewY[NewMoves] = Y[i]+1; |
|
243 M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE; |
|
244 NewMoves++; |
|
245 } |
|
246 } |
|
247 } |
|
248 } |
|
249 |
|
250 |
|
251 /* Returns bool */ |
|
252 char IsStupidPos(struct Map *M, int X, int Y) |
|
253 { |
|
254 struct Map MTemp; |
|
255 int NumBoxes, NumWalls, NumBoxesInPlatform; |
|
256 int j, i; |
|
257 |
|
258 CopyMap(&MTemp, M); |
|
259 |
|
260 |
|
261 for (i = 0; i<MTemp.NumBoxes; i++) |
|
262 if (MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] == PLATFORM) |
|
263 MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] = |
|
264 BOXINPLATFORM; |
|
265 else |
|
266 MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] = BOX; |
|
267 |
|
268 // ShowMap(&MTemp); |
|
269 |
|
270 /* We don't verify if j<=Y or i<=X is outside the map. It shouldn't |
|
271 * be, as it will be called with X,Y pair beeing the coordinates of a |
|
272 * Box! |
|
273 */ |
|
274 for (j = Y-1; j<=Y; j++) |
|
275 for (i=X-1; i<=X; i++) |
|
276 { |
|
277 NumBoxes = NumWalls = NumBoxesInPlatform = 0; |
|
278 /* Up-Left Cell */ |
|
279 if (MTemp.Cells[j][i] == WALL) |
|
280 NumWalls++; |
|
281 else if (MTemp.Cells[j][i] == BOX) |
|
282 NumBoxes++; |
|
283 else if (MTemp.Cells[j][i] == BOXINPLATFORM) |
|
284 NumBoxesInPlatform++; |
|
285 /* Up-Right Cell */ |
|
286 if (MTemp.Cells[j][i+1] == WALL) |
|
287 NumWalls++; |
|
288 else if (MTemp.Cells[j][i+1] == BOX) |
|
289 NumBoxes++; |
|
290 else if (MTemp.Cells[j][i+1] == BOXINPLATFORM) |
|
291 NumBoxesInPlatform++; |
|
292 /* Down-Right Cell */ |
|
293 if (MTemp.Cells[j+1][i+1] == WALL) |
|
294 NumWalls++; |
|
295 else if (MTemp.Cells[j+1][i+1] == BOX) |
|
296 NumBoxes++; |
|
297 else if (MTemp.Cells[j+1][i+1] == BOXINPLATFORM) |
|
298 NumBoxesInPlatform++; |
|
299 /* Down-Left Cell */ |
|
300 if (MTemp.Cells[j+1][i] == WALL) |
|
301 NumWalls++; |
|
302 else if (MTemp.Cells[j+1][i] == BOX) |
|
303 NumBoxes++; |
|
304 else if (MTemp.Cells[j+1][i] == BOXINPLATFORM) |
|
305 NumBoxesInPlatform++; |
|
306 |
|
307 if ((NumBoxesInPlatform + NumBoxes + NumWalls == 4) && |
|
308 (NumBoxes >= 1)) |
|
309 return MOVE_ILLEGAL; |
|
310 } |
|
311 |
|
312 return MOVE_OK; |
|
313 } |
|
314 |
|
315 |
|
316 int MoveBox(struct Map *M, int NumBox, int Direction) |
|
317 { |
|
318 char InPlatform; |
|
319 |
|
320 InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM); |
|
321 |
|
322 switch(Direction) |
|
323 { |
|
324 case DIR_LEFT: |
|
325 if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] == |
|
326 MANCANMOVE && |
|
327 (M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] |
|
328 != WALL) && |
|
329 (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1] |
|
330 != CANTO) ) |
|
331 { |
|
332 if(InPlatform) |
|
333 M->NumBoxesInPlatform--; |
|
334 M->BoxX[NumBox]--; |
|
335 if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == |
|
336 PLATFORM) |
|
337 M->NumBoxesInPlatform++; |
|
338 return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); |
|
339 }else return 0; |
|
340 break; |
|
341 case DIR_RIGHT: |
|
342 if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] == |
|
343 MANCANMOVE && |
|
344 (M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] |
|
345 != WALL) && |
|
346 (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]+1] |
|
347 != CANTO) ) |
|
348 { |
|
349 if(InPlatform) |
|
350 M->NumBoxesInPlatform--; |
|
351 M->BoxX[NumBox]++; |
|
352 if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == |
|
353 PLATFORM) |
|
354 M->NumBoxesInPlatform++; |
|
355 return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); |
|
356 }else return 0; |
|
357 break; |
|
358 case DIR_UP: |
|
359 if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] == |
|
360 MANCANMOVE && |
|
361 (M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] |
|
362 != WALL) && |
|
363 (M->Cells[M->BoxY[NumBox]-1][M->BoxX[NumBox]] |
|
364 != CANTO) ) |
|
365 { |
|
366 if(InPlatform) |
|
367 M->NumBoxesInPlatform--; |
|
368 M->BoxY[NumBox]--; |
|
369 if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == |
|
370 PLATFORM) |
|
371 M->NumBoxesInPlatform++; |
|
372 return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); |
|
373 }else return 0; |
|
374 break; |
|
375 case DIR_DOWN: |
|
376 if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] == |
|
377 MANCANMOVE && |
|
378 (M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] |
|
379 != WALL) && |
|
380 (M->Cells[M->BoxY[NumBox]+1][M->BoxX[NumBox]] |
|
381 != CANTO) ) |
|
382 { |
|
383 if(InPlatform) |
|
384 M->NumBoxesInPlatform--; |
|
385 M->BoxY[NumBox]++; |
|
386 if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == |
|
387 PLATFORM) |
|
388 M->NumBoxesInPlatform++; |
|
389 return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); |
|
390 }else return 0; |
|
391 break; |
|
392 } |
|
393 /* Check for stupid movement */ |
|
394 return 0; |
|
395 } |
|
396 |
|
397 void PrintCombination(int Moves[], int NumMoves) |
|
398 { |
|
399 int i; |
|
400 |
|
401 for (i=0; i < NumMoves; i++) |
|
402 { |
|
403 printf("%i", Moves[i] >> 2); |
|
404 if ((Moves[i] & 0x03) == DIR_LEFT) |
|
405 printf("L"); |
|
406 else if ((Moves[i] & 0x03) == DIR_RIGHT) |
|
407 printf("R"); |
|
408 else if ((Moves[i] & 0x03) == DIR_UP) |
|
409 printf("U"); |
|
410 else |
|
411 printf("D"); |
|
412 printf(","); |
|
413 } |
|
414 printf("\n"); |
|
415 } |
|
416 |
|
417 int main(int argn, char **argv) |
|
418 { |
|
419 struct Map Morigin; |
|
420 struct Map M[MAX_MOVES+1]; |
|
421 int Moves[MAX_MOVES]; |
|
422 int NumMoves; |
|
423 int OldMaps; |
|
424 int IllegalMove; |
|
425 int Carry; |
|
426 |
|
427 int i; |
|
428 |
|
429 if (argn != 3) |
|
430 { |
|
431 printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]); |
|
432 exit(3); |
|
433 } |
|
434 ReadMap(&Morigin, argv[1]); |
|
435 sscanf(argv[2], "%i", &NumMoves); |
|
436 |
|
437 //ShowMap(&Morigin); |
|
438 |
|
439 for (i = 0; i < NumMoves; i++) |
|
440 Moves[i] = NBOX(0) + DIR_LEFT; |
|
441 |
|
442 // Reget the original map |
|
443 CopyMap(&M[0], &Morigin); |
|
444 CopyMap(&M[NumMoves], &Morigin); // For the first while cond. |
|
445 |
|
446 GetManMoves(&M[0]); |
|
447 ShowMap(&M[0]); |
|
448 |
|
449 IllegalMove = NumMoves - 1; |
|
450 // Process the combination |
|
451 for (i = 0; i < NumMoves; i++) |
|
452 { |
|
453 CopyMap(&M[i+1], &M[i]); |
|
454 if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) |
|
455 { |
|
456 IllegalMove = i; |
|
457 break; |
|
458 } |
|
459 } |
|
460 |
|
461 // Main solution finder loop |
|
462 while (!(M[NumMoves].NumPlatforms == M[NumMoves].NumBoxesInPlatform && |
|
463 IllegalMove == -1)) |
|
464 { |
|
465 // Increase the Counter |
|
466 { |
|
467 Carry = 1; |
|
468 // If last combination was legal |
|
469 if (IllegalMove == -1) |
|
470 IllegalMove = NumMoves -1; |
|
471 // Reset the direction of sure-invalid moves |
|
472 for (i = IllegalMove + 1; i < NumMoves; i++) |
|
473 Moves[i] = NBOX(0) + DIR_LEFT; |
|
474 // Increase Counter for a new try of moves |
|
475 for (i = IllegalMove; i >= 0 && Carry; i--) |
|
476 { |
|
477 Moves[i]++; |
|
478 Carry = 0; |
|
479 if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1) |
|
480 { Moves[i] = NBOX(0) + DIR_LEFT; Carry = 1; } |
|
481 } |
|
482 OldMaps = i+1; // Sure? I think it's i+1 |
|
483 // If we change the number of movements for solution |
|
484 if (Carry) |
|
485 { |
|
486 if (NumMoves > MAX_MOVES) |
|
487 break; // MAX MOVES EXCEEDED!!! |
|
488 NumMoves++; |
|
489 for (i = 0; i < NumMoves; i++) |
|
490 Moves[i] = NBOX(0) + DIR_LEFT; |
|
491 OldMaps=0; |
|
492 CopyMap(&M[NumMoves], &Morigin); |
|
493 // For the first while cond. |
|
494 printf("Provant %i moviments...\n", NumMoves); |
|
495 fflush(stdout); |
|
496 } |
|
497 } |
|
498 |
|
499 |
|
500 // First assume combination is legal |
|
501 IllegalMove = -1; |
|
502 // Process the combination |
|
503 for (i = OldMaps; i < NumMoves - 1; i++) |
|
504 { |
|
505 CopyMap(&M[i+1], &M[i]); |
|
506 if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) |
|
507 { |
|
508 IllegalMove = i; |
|
509 break; |
|
510 } /*else |
|
511 if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) || |
|
512 (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) && |
|
513 !M[i].BoxMoved) |
|
514 { |
|
515 IllegalMove = i; |
|
516 break; |
|
517 }*/ |
|
518 // For next map: |
|
519 GetManMoves(&M[i+1]); |
|
520 |
|
521 } |
|
522 // Here i = NumMoves - 1 |
|
523 CopyMap(&M[i+1], &M[i]); |
|
524 if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) |
|
525 IllegalMove = i; |
|
526 //ShowMap(&M[i+1]); |
|
527 |
|
528 //printf("IM: %i\n", IllegalMove); |
|
529 |
|
530 } |
|
531 |
|
532 // Print the combination |
|
533 PrintCombination(Moves, NumMoves); |
|
534 /* |
|
535 // Print The Steps |
|
536 for (i=0; i < NumMoves; i++) |
|
537 { |
|
538 ShowMap(&M[i]); |
|
539 } |
|
540 */ |
|
541 return 0; |
|
542 |
|
543 } |