1 #include <stdio.h>

     2 #include <string.h>

     3 #include <assert.h>

     4 #include <stdlib.h>

     5 #include <unistd.h>

     6 #include <signal.h>

     7 

     8 #define BOX '$'

     9 #define WALL '#'

    10 #define MAN '@'

    11 #define PLATFORM '.'

    12 #define BOXINPLATFORM '*'

    13 #define MANINPLATFORM 'E'

    14 #define BLANK ' '

    15 #define CORNER '-'

    16 #define MANCANMOVE '+'

    17 

    18 #define NBOX(n) ((n)<<2)

    19 

    20 //#define DEBUG

    21 

    22 enum

    23 {

    24 	ALARM_SECONDS=1

    25 };

    26 

    27 

    28 enum logic

    29 {

    30 	TRUE=1,

    31 	FALSE=0,

    32 };

    33 

    34 #define MAX_X 50

    35 #define MAX_Y 50

    36 #define MAX_MOVES 50

    37 #define MAX_STEPS 50

    38 #define MAX_BOXES 15

    39 

    40 #define MOVE_OK		1

    41 #define MOVE_BOX	2

    42 #define MOVE_ILLEGAL	0

    43 

    44 

    45 /* SOKOBAN Solution Finder

    46  *

    47  * Input File Format: XSB

    48  *

    49  * XSB Format definition:

    50  * 	Character matrix of:

    51  * 		@	MAN

    52  * 		#	WALL

    53  * 		$	BOX

    54  * 		*	BOX over PLATFORM

    55  * 		+	PLATFORM

    56  * 		-	(optional) Where a BOX should not be put

    57  * 	Everything that cannot be reached by the man or boxes (WALLS) must be

    58  * 	marked as is: WALLS.

    59  * 	All lines must be of the same length.

    60  */

    61 

    62 struct Position

    63 {

    64 	int x;

    65 	int y;

    66 };

    67 

    68 struct Map

    69 {

    70 	char Cells[MAX_Y][MAX_X];

    71 	char cells_boxes[MAX_Y][MAX_X];

    72 	char man_moves[MAX_Y][MAX_X];

    73 	int SizeX, SizeY;

    74 	struct Position Man;

    75 	int NumPlatforms;

    76 	int NumBoxesInPlatform;

    77 	struct Position Box[MAX_BOXES];

    78 	int NumBoxes;

    79 };

    80 

    81 

    82 

    83 enum e_direction

    84 {

    85 	DIR_LEFT,

    86 	DIR_RIGHT,

    87 	DIR_DOWN,

    88 	DIR_UP

    89 };

    90 const struct Position move_vectors[4] = {

    91 	{0, 1},

    92 	{0, -1},

    93 	{1, 0},

    94 	{-1, 0}};

    95 

    96 struct BoxMove

    97 {

    98 	int box;

    99 	struct Position dir;

   100 };

   101 

   102 float percent_to_show = 0;

   103 int depth_to_show = 0;

   104 

   105 int max_depth = 0;

   106 int min_depth_period = 0;

   107 int max_depth_period = 0;

   108 struct Map * actual_map;

   109 

   110 

   111 

   112 

   113 void CopyMap (struct Map *Mdest, const struct Map *Morig)

   114 {

   115 	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));

   116 }

   117 

   118 

   119 void ReadMap(struct Map *M, char *FileName)

   120 {

   121 	FILE *Fitxer;

   122 	int i,j;

   123 

   124 	if(!(Fitxer = fopen(FileName, "r")))

   125 	{

   126 		printf("Error opening %s!", FileName);

   127 		exit(1);

   128 	}

   129 

   130 	M->SizeX=0;

   131 	M->SizeY=0;

   132 	while (!feof(Fitxer))

   133 	{

   134 		fgets(M->Cells[M->SizeY], MAX_X, Fitxer);

   135 		M->SizeY++;

   136 	}

   137 	M->SizeY--;

   138 	M->SizeX = strlen(M->Cells[0]) - 1;

   139 

   140 	M->NumPlatforms = 0;

   141 	M->NumBoxesInPlatform = 0;

   142 	M->NumBoxes = 0;

   143 	for (j = 0; j<M->SizeY; j++)

   144 		for (i=0; i<M->SizeX; i++)

   145 		{

   146 			if (M->Cells[j][i] == MAN)

   147 			{ 

   148 				M->Man.x = i; M->Man.y = j; 

   149 				M->Cells[M->Man.y][M->Man.x] = BLANK;

   150 			}

   151 

   152 			if (M->Cells[j][i] == PLATFORM)

   153 				M->NumPlatforms++;

   154 			else if (M->Cells[j][i] == BOXINPLATFORM)

   155 			{

   156 				M->Cells[j][i] = PLATFORM;

   157 

   158 				M->NumPlatforms++;

   159 				M->NumBoxesInPlatform++;

   160 

   161 				M->Box[M->NumBoxes].x = i;

   162 				M->Box[M->NumBoxes].y = j;

   163 				M->NumBoxes++;

   164 			} else if (M->Cells[j][i] == BOX)

   165 			{

   166 				M->Cells[j][i] = BLANK;

   167 

   168 				M->Box[M->NumBoxes].x = i;

   169 				M->Box[M->NumBoxes].y = j;

   170 				M->NumBoxes++;

   171 			} else if (M->Cells[j][i] == CORNER)

   172 			{

   173 				M->Cells[j][i] = CORNER;

   174 			} else if (M->Cells[j][i] != WALL)

   175 			{

   176 				if (    (M->Cells[j][i-1] == WALL &&

   177 					 M->Cells[j-1][i] == WALL) ||

   178 					(M->Cells[j][i-1] == WALL &&

   179 					 M->Cells[j+1][i] == WALL) ||

   180 					(M->Cells[j][i+1] == WALL &&

   181 					 M->Cells[j-1][i] == WALL) ||

   182 					(M->Cells[j][i+1] == WALL &&

   183 					 M->Cells[j+1][i] == WALL))

   184 				M->Cells[j][i] = CORNER;

   185 			}

   186 				

   187 		}

   188 

   189 }

   190 

   191 

   192 void ShowMap (const struct Map *M)

   193 {

   194 	struct Map Temp;

   195 	int i,j;

   196 

   197 	CopyMap(&Temp, M);

   198 

   199 	Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN;

   200 

   201 	for (i = 0; i < Temp.NumBoxes; i++)

   202 	{

   203 		if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM)

   204 			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM;

   205 		else

   206 			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX;

   207 	}

   208 

   209 	for (j = 0; j<Temp.SizeY; j++)

   210 	{

   211 		for (i=0; i<Temp.SizeX; i++)

   212 			fprintf(stderr,"%c", Temp.Cells[j][i]);

   213 		fprintf(stderr,"\n");

   214 	}

   215 

   216 #if 0

   217 	// Print Where the man can move

   218 	for (j = 0; j<Temp.SizeY; j++)

   219 	{

   220 		for (i=0; i<Temp.SizeX; i++)

   221 			printf("%c", Temp.ManMoves[j][i]);

   222 		printf("\n");

   223 	}

   224 #endif

   225 

   226 	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);

   227 	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,

   228 			Temp.NumBoxesInPlatform);

   229 

   230 }

   231 

   232 

   233 

   234 int InverseMove(char Dir1, char Dir2)

   235 {

   236 	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||

   237 		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))

   238 		return 1;

   239 	return 0;

   240 }

   241 

   242 

   243 void PrintCombination(int Moves[], int NumMoves)

   244 {

   245 	int i;

   246 

   247 	for (i=0; i < NumMoves; i++)

   248 	{

   249 		printf("%i", Moves[i] >> 2);

   250 		if ((Moves[i] & 0x03) == DIR_LEFT)

   251 			printf("L");

   252 		else if ((Moves[i] & 0x03) == DIR_RIGHT)

   253 			printf("R");

   254 		else if ((Moves[i] & 0x03) == DIR_UP)

   255 			printf("U");

   256 		else

   257 			printf("D");

   258 		printf(",");

   259 	}

   260 	printf("\n");

   261 }

   262 

   263 #if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/

   264  Situation:

   265     

   266   ->@$ #

   267       $

   268 */

   269 int box_will_be_blocked(const struct Map * m, const struct Position mov,

   270 	const struct Position box_pos)

   271 {

   272 	struct Position next_pos2, tmp, tmp2[2];

   273 	int i;

   274 

   275 	next_pos2.x = box_pos.x + mov.x;

   276 	next_pos2.y = box_pos.y + mov.y;

   277 

   278 	tmp.x = next_pos2.x + mov.x;

   279 	tmp.y = next_pos2.y + mov.y;

   280 	tmp2[0].x = next_pos2.x + mov.y;

   281 	tmp2[0].y = next_pos2.y + mov.x;

   282 	tmp2[1].x = next_pos2.x - mov.y;

   283 	tmp2[1].y = next_pos2.y - mov.x;

   284 	for (i=0; i < 2; i++)

   285 	{

   286 		if (m->man_moves[tmp.y][tmp.x] == WALL &&

   287 			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

   288 		{

   289 			return TRUE;

   290 		}

   291 		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

   292 			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)

   293 		{

   294 			return TRUE;

   295 		}

   296 		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

   297 			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

   298 		{

   299 			return TRUE;

   300 		}

   301 	}

   302 

   303 	return FALSE;

   304 }

   305 

   306 int is_corner_area(const struct Map * m, const struct Position p,

   307 	const struct Position box, const struct Position new_box)

   308 {

   309 	int NumMoves, NewMoves;

   310 	struct Position pos[MAX_MOVES];

   311 	struct Position new_pos[MAX_MOVES];

   312 	char corners[MAX_Y][MAX_X];

   313 	int i,j;

   314 	struct Position next_pos;

   315 	char *next_cell;

   316 

   317 

   318 	/* Blank the garden */

   319 	for (j = 0; j<m->SizeY; j++)

   320 		for (i=0; i<m->SizeX; i++)

   321 			corners[j][i] = m->Cells[j][i];

   322 

   323 	/* Let's put the boxes */

   324 	for (i = 0; i<m->NumBoxes; i++)

   325 		corners[m->Box[i].y][m->Box[i].x] = BOX;

   326 

   327 	/* Let's put our box - it can be simply added */

   328 	corners[new_box.y][new_box.x] = BOX;

   329 	/* Let's remove the original box. */

   330 	corners[box.y][box.x] = BLANK;

   331 

   332 	NewMoves = 1;

   333 	new_pos[0] = p;

   334 	while (NewMoves > 0)

   335 	{

   336 		/* The before named "New Moves" become the moves we have

   337 		   to analyze */

   338 		NumMoves = NewMoves;

   339 		for (i=0; i<NewMoves; i++)

   340 		{

   341 			pos[i] = new_pos[i];

   342 		}

   343 

   344 		/* Search new positions for each position */

   345 		NewMoves = 0;

   346 		for (i=0; i<NumMoves; i++)

   347 		{

   348 			/* For each direction */

   349 			for (j=0; j<4; j++)

   350 			{

   351 				next_pos.x = pos[i].x + move_vectors[j].x;

   352 				next_pos.y = pos[i].y + move_vectors[j].y;

   353 				next_cell = &corners[next_pos.y][next_pos.x];

   354 				if(*next_cell == BLANK ||

   355 					*next_cell == PLATFORM)

   356 				{

   357 					return FALSE;

   358 				}

   359 				else if(*next_cell == CORNER)

   360 				{

   361 					new_pos[NewMoves] = next_pos;

   362 					*next_cell = MANCANMOVE;

   363 					NewMoves++;

   364 				}

   365 			}

   366 		}

   367 	}

   368 

   369 	return TRUE;

   370 }

   371 

   372 int does_box_close_corners(const struct Map * m, const struct Position mov,

   373 	const struct Position box_pos)

   374 {

   375 	struct Position p, p2;

   376 

   377 	p.x = box_pos.x + mov.x;

   378 	p.y = box_pos.y + mov.y;

   379 	

   380 	/* Let's plan the checks */

   381 	/* The point will be marked with a MANCANMOVE */

   382 	p2.x = p.x + mov.x;

   383 	p2.y = p.y + mov.y;

   384 	if (m->Cells[p2.y][p2.x] == CORNER)

   385 	{

   386 		if (is_corner_area(m, p2, box_pos, p))

   387 			return TRUE;

   388 	}

   389 

   390 	p2.x = p.x + mov.y;

   391 	p2.y = p.y + mov.x;

   392 	if (m->Cells[p2.y][p2.x] == CORNER)

   393 	{

   394 		if (is_corner_area(m, p2, box_pos, p))

   395 			return TRUE;

   396 	}

   397 

   398 	p2.x = p.x - mov.y;

   399 	p2.y = p.y - mov.x;

   400 	if (m->Cells[p2.y][p2.x] == CORNER)

   401 	{

   402 		if (is_corner_area(m, p2, box_pos, p))

   403 			return TRUE;

   404 	}

   405 	return FALSE;

   406 }

   407 #endif

   408 

   409 /*

   410 Catch the situation where a box is moved next to a corner, where the box

   411 next to it will not be able to be moved.

   412 */

   413 int is_dead1(const struct Map * m, const struct Position mov,

   414 	const struct Position new_pos)

   415 {

   416 	struct Position opposite1, opposite2;

   417 

   418 	/* The wall corners must exist */

   419 	opposite1.x = -mov.y;

   420 	opposite1.y = -mov.x;

   421 	opposite2.x = mov.y;

   422 	opposite2.y = mov.x;

   423 

   424 #ifdef DEBUG

   425 	ShowMap(m);

   426 #endif

   427 

   428 	/* Test the first corner */

   429 	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]

   430 		== WALL)

   431 	{

   432 		/* Test wall at opposites 1*/

   433 		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

   434 			== WALL &&

   435 			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

   436 		{

   437 				return TRUE;

   438 		}

   439 		else

   440 		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

   441 			== BOX &&

   442 			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

   443 		{

   444 				return TRUE;

   445 		}

   446 		/* Test wall at opposites 2 */

   447 		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

   448 			== WALL &&

   449 			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

   450 		{

   451 				return TRUE;

   452 		}

   453 		else

   454 		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

   455 			== BOX &&

   456 			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

   457 		{

   458 				return TRUE;

   459 		}

   460 	}

   461 

   462 	/* Test the second corner */

   463 	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]

   464 		== WALL)

   465 	{

   466 		/* Test wall at opposites 1*/

   467 		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

   468 			== WALL &&

   469 			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

   470 		{

   471 				return TRUE;

   472 		}

   473 		else

   474 		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

   475 			== BOX &&

   476 			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

   477 		{

   478 				return TRUE;

   479 		}

   480 		/* Test wall at opposites 2 */

   481 		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

   482 			== WALL &&

   483 			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

   484 		{

   485 				return TRUE;

   486 		}

   487 		else

   488 		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

   489 			== BOX &&

   490 			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

   491 		{

   492 				return TRUE;

   493 		}

   494 	}

   495 

   496 	return FALSE;

   497 }

   498 

   499 /*

   500 Catch the situation where a corner gets surrounded by boxes.

   501 */

   502 int is_dead2(const struct Map * m, const struct Position mov,

   503 	const struct Position new_pos)

   504 {

   505 	struct Position next, next2, opposite1, opposite2;

   506 

   507 	next.x = new_pos.x+mov.x;

   508 	next.y = new_pos.y+mov.y;

   509 

   510 	/* The corner must exist */

   511 	if (m->Cells[next.y][next.x] != CORNER)

   512 		return FALSE;

   513 

   514 

   515 	/* The wall corners must exist */

   516 	opposite1.x = next.x -mov.y;

   517 	opposite1.y = next.y -mov.x;

   518 	opposite2.x = next.x + mov.y;

   519 	opposite2.y = next.y + mov.x;

   520 

   521 	if (m->man_moves[opposite1.y][opposite1.x] == BOX)

   522 	{

   523 		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL

   524 		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)

   525 		   return TRUE;

   526 	}

   527 

   528 	if (m->man_moves[opposite2.y][opposite2.x] == BOX)

   529 	{

   530 		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL

   531 		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)

   532 		   return TRUE;

   533 	}

   534 	return FALSE;

   535 }

   536 

   537 int is_box_movable(const struct Map * m, const struct Position mov,

   538 	const struct Position box_pos)

   539 {

   540 	struct Position next_pos2;

   541 

   542 	next_pos2.x = box_pos.x + mov.x;

   543 	next_pos2.y = box_pos.y + mov.y;

   544 

   545 	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&

   546 		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||

   547 		m->man_moves[next_pos2.y][next_pos2.x] == BOX)

   548 	{

   549 		return FALSE;

   550 	}

   551 	else if (is_dead1(m, mov, next_pos2) == TRUE)

   552 	{

   553 		return FALSE;

   554 	}

   555 	else if (is_dead2(m, mov, next_pos2) == TRUE)

   556 	{

   557 		return FALSE;

   558 	}

   559 	return TRUE;

   560 }

   561 

   562 /* It modifies m->man_moves */

   563 int get_box_movements(struct Map * m,

   564 	struct BoxMove movements[])

   565 {

   566 	struct Position pos[MAX_MOVES];

   567 	struct Position new_pos[MAX_MOVES];

   568 	int NumMoves, NewMoves;

   569 	int j, i;

   570 	struct Position next_pos;

   571 	char *next_cell;

   572 	int num_box_movements = 0;

   573 	

   574 	/* Let's  the map with only walls in man_moves - other, blanks */

   575 	for (j = 0; j<m->SizeY; j++)

   576 		for (i=0; i<m->SizeX; i++)

   577 		{

   578 			if (m->Cells[j][i] == WALL)

   579 				m->man_moves[j][i] = WALL;

   580 			else

   581 				m->man_moves[j][i] = BLANK;

   582 		}

   583 

   584 	/* Let's put the boxes */

   585 	for (i = 0; i<m->NumBoxes; i++)

   586 	{

   587 		m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;

   588 		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;

   589 	}

   590 

   591 	NewMoves = 1;

   592 	new_pos[0].x = m->Man.x;

   593 	new_pos[0].y = m->Man.y;

   594 	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;

   595 	while (NewMoves > 0)

   596 	{

   597 		/* The before named "New Moves" become the moves we have

   598 		   to analyze */

   599 		NumMoves = NewMoves;

   600 		for (i=0; i<NewMoves; i++)

   601 		{

   602 			pos[i] = new_pos[i];

   603 		}

   604 

   605 		/* Search new positions for each position */

   606 		NewMoves = 0;

   607 		for (i=0; i<NumMoves; i++)

   608 		{

   609 			/* For each direction */

   610 			for (j=0; j<4; j++)

   611 			{

   612 				next_pos.x = pos[i].x + move_vectors[j].x;

   613 				next_pos.y = pos[i].y + move_vectors[j].y;

   614 				next_cell = &m->man_moves[next_pos.y][next_pos.x];

   615 				if(*next_cell == BLANK)

   616 				{

   617 					new_pos[NewMoves] = next_pos;

   618 					*next_cell = MANCANMOVE;

   619 					NewMoves++;

   620 				}

   621 				else if (*next_cell == BOX)

   622 				{

   623 						

   624 					/* Check if the box is movable */

   625 

   626 					if (is_box_movable(m, move_vectors[j],

   627 						next_pos ))

   628 					{

   629 						{

   630 					movements[num_box_movements].box =

   631 					m->cells_boxes[next_pos.y][next_pos.x];

   632 					movements[num_box_movements].dir =

   633 					move_vectors[j];

   634 					num_box_movements++;

   635 						}

   636 					}

   637 					

   638 				}

   639 

   640 			}

   641 		}

   642 	}

   643 

   644 	return num_box_movements;

   645 }

   646 

   647 void force_move_box(struct Map *m, struct BoxMove move)

   648 {

   649 	struct Position newpos;

   650 

   651 

   652 	/* Add coords */

   653 	newpos.x = m->Box[move.box].x + move.dir.x;

   654 	newpos.y = m->Box[move.box].y + move.dir.y;

   655 

   656 	/* Be certain the move can be done */

   657 	assert(m->Cells[newpos.y][newpos.x] != BOX);

   658 	assert(m->Cells[newpos.y][newpos.x] != WALL);

   659 

   660 	/* Control if we moved the box to a platform */

   661 	if(m->Cells[newpos.y][newpos.x] == PLATFORM)

   662 	{

   663 		m->NumBoxesInPlatform++;

   664 	}

   665 

   666 	/* Control if we moved the box from a platform */

   667 	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)

   668 	{

   669 		m->NumBoxesInPlatform--;

   670 	}

   671 	m->Man = m->Box[move.box];

   672 

   673 	m->Box[move.box] = newpos;

   674 }

   675 

   676 int are_boxes_equal(const struct Position b1[], const struct Position b2[],

   677 	int n)

   678 {

   679 	int i;

   680 	char tmp[MAX_Y][MAX_X]; /* !!!argh */

   681 

   682 	memset(tmp, 0, sizeof(tmp));

   683 

   684 	for (i=0; i < n; i++)

   685 	{

   686 		tmp[b1[i].y][b1[i].x] = 1;

   687 	}

   688 	for (i=0; i < n; i++)

   689 	{

   690 		if (tmp[b2[i].y][b2[i].x] != 1)

   691 			return FALSE;

   692 	}

   693 	return TRUE;

   694 }

   695 

   696 int is_new_map(struct Map maps[], int depth)

   697 {

   698 	struct Map *m;

   699 	int i;

   700 

   701 	m = &maps[depth];

   702 

   703 	for(i=0; i<max_depth; i++)

   704 	{

   705 		/* No l'hem de comparar amb ell mateix */

   706 		if (i == depth)

   707 			continue;

   708 

   709 		if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)

   710 			continue;

   711 		else

   712 		{

   713 			if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))

   714 				continue;

   715 		}

   716 		return FALSE;

   717 	}

   718 	return TRUE;

   719 }

   720 

   721 void PrintMove(struct BoxMove b)

   722 {

   723 	printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);

   724 }

   725 

   726 void show_percent_callback(int parameter)

   727 {

   728 	fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show,

   729 		min_depth_period, max_depth_period);

   730 	ShowMap(actual_map);

   731 	fflush(stderr);

   732 	min_depth_period = MAX_STEPS;

   733 	max_depth_period = 0;

   734 #ifndef DEBUG

   735 	alarm(ALARM_SECONDS);

   736 #endif

   737 }

   738 

   739 int search_depth(struct Map maps[], int depth,

   740 	struct BoxMove movements[],

   741 	int num_movements, float percent, float total_percent)

   742 {

   743 	struct BoxMove new_movements[MAX_MOVES];

   744 	int num_new_movements;

   745 	struct Map *m; 

   746 	int i;

   747 	float next_percent;

   748 

   749 	next_percent = percent / num_movements;

   750 

   751 	m = &maps[depth+1];

   752 	if (depth > max_depth)

   753 		max_depth = depth;

   754 	if (depth > max_depth_period)

   755 		max_depth_period = depth;

   756 	if (depth < min_depth_period)

   757 		min_depth_period = depth;

   758 

   759 	for (i=0; i < num_movements; i++)

   760 	{

   761 		CopyMap(m, &maps[depth]);

   762 		force_move_box(m, movements[i]);

   763 		if (m->NumPlatforms == m->NumBoxesInPlatform)

   764 		{

   765 			printf("\nSolved!\n");

   766 			PrintMove(movements[i]);

   767 			return 0;

   768 		}

   769 

   770 		if (is_new_map(maps, depth+1))

   771 		{

   772 			num_new_movements = get_box_movements(m, new_movements);

   773 			assert(num_new_movements < MAX_MOVES);

   774 		}

   775 		else

   776 			num_new_movements = 0;

   777 

   778 		if (num_new_movements == 0)

   779 		{

   780 			percent_to_show = total_percent + next_percent*i;

   781 			depth_to_show = depth;

   782 			actual_map = &maps[depth];

   783 #ifdef DEBUG		/* to be out */

   784 			show_percent_callback(0);

   785 #endif

   786 	

   787 		}

   788 		else

   789 		{

   790 			if (depth+1 < MAX_STEPS)

   791 			{

   792 				if(search_depth(maps, depth+1, new_movements,

   793 					num_new_movements, next_percent,

   794 					total_percent + next_percent*i) == 0)

   795 				{

   796 					PrintMove(movements[i]);

   797 					return 0;

   798 				}

   799 			}

   800 		}

   801 	}

   802 	return 1;

   803 }

   804 

   805 

   806 

   807 

   808 void program_alarm()

   809 {

   810         struct sigaction my_action;

   811         int result;

   812 

   813         my_action.sa_handler = show_percent_callback;

   814         my_action.sa_flags = 0;

   815         memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask));

   816 

   817         result = sigaction(SIGALRM, &my_action, NULL);

   818         assert(result == 0);

   819 

   820 	alarm(1);

   821 }

   822 

   823 int main(int argn, char **argv)

   824 {

   825 	struct Map Morigin;

   826 	struct Map maps[MAX_STEPS+1];

   827 	struct BoxMove new_movements[MAX_MOVES];

   828 	int num_new_movements;

   829 

   830 

   831 	if (argn != 2)

   832 	{

   833 		printf("Usage: %s <mapfile>\n", argv[0]);

   834 		exit(3);

   835 	}

   836 	ReadMap(&Morigin, argv[1]);

   837 

   838 	// Reget the original map

   839 	CopyMap(&maps[0], &Morigin);

   840 

   841 	assert(maps[0].NumPlatforms > maps[0].NumBoxesInPlatform);

   842 

   843 	num_new_movements = get_box_movements(&maps[0], new_movements);

   844 	assert(num_new_movements < MAX_MOVES);

   845 	assert(num_new_movements > 0);

   846 

   847 #ifndef DEBUG

   848 	program_alarm();

   849 #endif

   850 	search_depth(maps, 0, new_movements,

   851 		num_new_movements, 100. / num_new_movements,

   852 		0);

   853 

   854 	return 0;

   855 

   856 }