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_BOXES 15

    25 

    26 #define MOVE_OK		1

    27 #define MOVE_BOX	2

    28 #define MOVE_ILLEGAL	0

    29 

    30 /* SOKOBAN Solution Finder

    31  *

    32  * Input File Format: XSB

    33  *

    34  * XSB Format definition:

    35  * 	Character matrix of:

    36  * 		@	MAN

    37  * 		#	WALL

    38  * 		$	BOX

    39  * 		*	BOX over PLATFORM

    40  * 		+	PLATFORM

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

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

    43  * 	marked as is: WALLS.

    44  * 	All lines must be of the same length.

    45  */

    46 

    47 

    48 struct Map

    49 {

    50 	char Cells[MAX_Y][MAX_X];

    51 	char ManMoves[MAX_Y][MAX_X];

    52 	int SizeX, SizeY;

    53 	int ManX, ManY;

    54 	int NumPlatforms;

    55 	int NumBoxesInPlatform;

    56 	int BoxX[MAX_BOXES];

    57 	int BoxY[MAX_BOXES];

    58 	int NumBoxes;

    59 };

    60 

    61 

    62 void CopyMap (struct Map *Mdest, struct Map *Morig)

    63 {

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

    65 }

    66 

    67 

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

    69 {

    70 	FILE *Fitxer;

    71 	int i,j;

    72 

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

    74 	{

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

    76 		exit(1);

    77 	}

    78 

    79 	M->SizeX=0;

    80 	M->SizeY=0;

    81 	while (!feof(Fitxer))

    82 	{

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

    84 		M->SizeY++;

    85 	}

    86 	M->SizeY--;

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

    88 

    89 	M->NumPlatforms = 0;

    90 	M->NumBoxesInPlatform = 0;

    91 	M->NumBoxes = 0;

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

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

    94 		{

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

    96 			{ 

    97 				M->ManX = i; M->ManY = j; 

    98 				M->Cells[M->ManY][M->ManX] = BLANK;

    99 			}

   100 

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

   102 				M->NumPlatforms++;

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

   104 			{

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

   106 

   107 				M->NumPlatforms++;

   108 				M->NumBoxesInPlatform++;

   109 

   110 				M->BoxX[M->NumBoxes] = i;

   111 				M->BoxY[M->NumBoxes] = j;

   112 				M->NumBoxes++;

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

   114 			{

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

   116 

   117 				M->BoxX[M->NumBoxes] = i;

   118 				M->BoxY[M->NumBoxes] = j;

   119 				M->NumBoxes++;

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

   121 			{

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

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

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

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

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

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

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

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

   130 				M->Cells[j][i] = CANTO;

   131 			}

   132 				

   133 		}

   134 

   135 }

   136 

   137 

   138 void ShowMap (struct Map *M)

   139 {

   140 	struct Map Temp;

   141 	int i,j;

   142 

   143 	CopyMap(&Temp, M);

   144 

   145 	Temp.Cells[Temp.ManY][Temp.ManX] = MAN;

   146 

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

   148 	{

   149 		if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM)

   150 			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM;

   151 		else

   152 			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX;

   153 	}

   154 

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

   156 	{

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

   158 			printf("%c", Temp.Cells[j][i]);

   159 		printf("\n");

   160 	}

   161 	// Print Where the man can move

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

   163 	{

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

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

   166 		printf("\n");

   167 	}

   168 

   169 	printf("Man is at (%i,%i)\n", Temp.ManX, Temp.ManY);

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

   171 			Temp.NumBoxesInPlatform);

   172 }

   173 

   174 

   175 

   176 int InverseMove(char Dir1, char Dir2)

   177 {

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

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

   180 		return 1;

   181 	return 0;

   182 }

   183 

   184 

   185 void GetManMoves(struct Map *M)

   186 {

   187 	int X[MAX_MOVES], Y[MAX_MOVES];

   188 	int NewX[MAX_MOVES], NewY[MAX_MOVES];

   189 	int NumMoves, NewMoves;

   190 	int j, i;

   191 	

   192 	NumMoves = 1;

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

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

   195 			M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK;

   196 	for (i = 0; i<M->NumBoxes; i++)

   197 		M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL;

   198 

   199 	NewMoves = 1;

   200 	NewX[0] = M->ManX;

   201 	NewY[0] = M->ManY;

   202 	while (NewMoves)

   203 	{

   204 		NumMoves = NewMoves;

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

   206 		{

   207 			X[i] = NewX[i];

   208 			Y[i] = NewY[i];

   209 		}

   210 		NewMoves = 0;

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

   212 		{

   213 			if(M->ManMoves[Y[i]][X[i]-1] == BLANK)

   214 			{

   215 				NewX[NewMoves] = X[i]-1;

   216 				NewY[NewMoves] = Y[i];

   217 				M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE;

   218 				NewMoves++;

   219 			}

   220 			if(M->ManMoves[Y[i]][X[i]+1] == BLANK)

   221 			{

   222 				NewX[NewMoves] = X[i]+1;

   223 				NewY[NewMoves] = Y[i];

   224 				M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE;

   225 				NewMoves++;

   226 			}

   227 			if(M->ManMoves[Y[i]-1][X[i]] == BLANK)

   228 			{

   229 				NewX[NewMoves] = X[i];

   230 				NewY[NewMoves] = Y[i]-1;

   231 				M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE;

   232 				NewMoves++;

   233 			}

   234 			if(M->ManMoves[Y[i]+1][X[i]] == BLANK)

   235 			{

   236 				NewX[NewMoves] = X[i];

   237 				NewY[NewMoves] = Y[i]+1;

   238 				M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE;

   239 				NewMoves++;

   240 			}

   241 		}

   242 	}

   243 }

   244 

   245 int MoveBox(struct Map *M, int NumBox, int Direction)

   246 {

   247 	char InPlatform;

   248 

   249 	InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM);

   250 

   251 	switch(Direction)

   252 	{

   253 		case DIR_LEFT:

   254 			if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] ==

   255 				MANCANMOVE &&

   256 			M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] !=

   257 				WALL &&

   258 			M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1] !=

   259 				CANTO)

   260 			{

   261 				M->ManX = M->BoxX[NumBox];

   262 				M->ManY = M->BoxY[NumBox];

   263 

   264 				if(InPlatform)

   265 					M->NumBoxesInPlatform--;

   266 				M->BoxX[NumBox]--;

   267 				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

   268 					PLATFORM)

   269 					M->NumBoxesInPlatform++;

   270 				return 1;

   271 			}else return 0;

   272 			break;

   273 		case DIR_RIGHT:

   274 			if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] ==

   275 				MANCANMOVE &&

   276 			M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] !=

   277 				WALL &&

   278 			M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] !=

   279 				CANTO)

   280 			{

   281 				M->ManX = M->BoxX[NumBox];

   282 				M->ManY = M->BoxY[NumBox];

   283 

   284 				if(InPlatform)

   285 					M->NumBoxesInPlatform--;

   286 				M->BoxX[NumBox]++;

   287 				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

   288 					PLATFORM)

   289 					M->NumBoxesInPlatform++;

   290 				return 1;

   291 			}else return 0;

   292 			break;

   293 		case DIR_UP:

   294 			if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] ==

   295 				MANCANMOVE &&

   296 			M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] !=

   297 				WALL &&

   298 			M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] !=

   299 				CANTO)

   300 			{

   301 				M->ManX = M->BoxX[NumBox];

   302 				M->ManY = M->BoxY[NumBox];

   303 

   304 				if(InPlatform)

   305 					M->NumBoxesInPlatform--;

   306 				M->BoxY[NumBox]--;

   307 				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

   308 					PLATFORM)

   309 					M->NumBoxesInPlatform++;

   310 				return 1;

   311 			}else return 0;

   312 			break;

   313 		case DIR_DOWN:

   314 			if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] ==

   315 				MANCANMOVE &&

   316 			M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] !=

   317 				WALL &&

   318 			M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] !=

   319 				CANTO)

   320 			{

   321 				M->ManX = M->BoxX[NumBox];

   322 				M->ManY = M->BoxY[NumBox];

   323 

   324 				if(InPlatform)

   325 					M->NumBoxesInPlatform--;

   326 				M->BoxY[NumBox]++;

   327 				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

   328 					PLATFORM)

   329 					M->NumBoxesInPlatform++;

   330 				return 1;

   331 			}else return 0;

   332 			break;

   333 	}

   334 	return 0;

   335 }

   336 

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

   338 {

   339 	int i;

   340 

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

   342 	{

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

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

   345 			printf("L");

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

   347 			printf("R");

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

   349 			printf("U");

   350 		else

   351 			printf("D");

   352 		printf(",");

   353 	}

   354 	printf("\n");

   355 }

   356 

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

   358 {

   359 	struct Map Morigin;

   360 	struct Map M[MAX_MOVES+1];

   361 	int Moves[MAX_MOVES];

   362 	int NumMoves;

   363 	int OldMaps;

   364 	int IllegalMove;

   365 	int Carry;

   366 

   367 	int i;

   368 

   369 	if (argn != 3)

   370 	{

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

   372 		exit(3);

   373 	}

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

   375 	sscanf(argv[2], "%i", &NumMoves);

   376 

   377 	

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

   379 		Moves[i] = NBOX(0) + DIR_LEFT;

   380 

   381 	// Reget the original map

   382 	CopyMap(&M[0], &Morigin);

   383 	CopyMap(&M[NumMoves], &Morigin);	// For the first while cond.

   384 

   385 	GetManMoves(&M[0]);

   386 

   387 	ShowMap(&M[0]);

   388 

   389 	IllegalMove = NumMoves - 1;

   390 	// Process the combination

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

   392 	{

   393 		CopyMap(&M[i+1], &M[i]);

   394 		if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

   395 		{

   396 			IllegalMove = i;

   397 			break;

   398 		}

   399 		GetManMoves(&M[i+1]);

   400 	}

   401 

   402 	// Main solution finder loop

   403 	while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform)

   404 	{

   405 		// Increase the Counter

   406 		{

   407 			Carry = 1;

   408 			// Reset the direction of sure-invalid moves

   409 			for (i = IllegalMove + 1; i < NumMoves; i++)

   410 				Moves[i] = NBOX(0) + DIR_LEFT;

   411 			// Increase Counter for a new try of moves

   412 			for (i = IllegalMove; i >= 0 && Carry; i--)

   413 			{

   414 				Moves[i]++;

   415 				Carry = 0;

   416 				if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1)

   417 				{ Moves[i] = NBOX(0) + DIR_LEFT; Carry = 1; }

   418 			}

   419 			OldMaps = i+1;	// Sure? I think it's i+1

   420 			// If we change the number of movements for solution

   421 			if (Carry)

   422 			{

   423 				if (NumMoves > MAX_MOVES)

   424 					break;	// MAX MOVES EXCEEDED!!!

   425 				NumMoves++;

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

   427 					Moves[i] = NBOX(0) + DIR_LEFT;

   428 				OldMaps=0;

   429 				CopyMap(&M[NumMoves], &Morigin);

   430 					// For the first while cond.

   431 				printf("Provant %i moviments...\n", NumMoves);

   432 			}

   433 		}

   434 

   435 		// Print the combination

   436 //		PrintCombination(Moves, NumMoves);

   437 

   438 		IllegalMove = NumMoves - 1;

   439 		// Process the combination

   440 //		printf("------- STARTING COMBINATION ------------\n");

   441 		for (i = OldMaps; i < NumMoves - 1; i++)

   442 		{

   443 			CopyMap(&M[i+1], &M[i]);

   444 //			GetManMoves(&M[i+1]);

   445 			if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

   446 			{

   447 				IllegalMove = i;

   448 				break;

   449 			}/* else	// Si el moviment es bo

   450 			if ((Moves[i] >> 2) == (Moves[i+1] >> 2) &&

   451 				((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 1||

   452 				((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 5)))

   453 			{

   454 				IllegalMove = i;

   455 				break;

   456 			}*/

   457 			GetManMoves(&M[i+1]);

   458 //			ShowMap(&M[i+1]);

   459 				

   460 		}

   461 		// Here i = NumMoves - 1

   462 		CopyMap(&M[i+1], &M[i]);

   463 		if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

   464 			IllegalMove = i;

   465 /*

   466 		for (i=0;i < IllegalMove; i++)

   467 		{

   468 			ShowMap(&M[i+1]);

   469 		}

   470 */

   471 					

   472 	}

   473 

   474 	// Print the combination

   475 	PrintCombination(Moves, NumMoves);

   476 

   477 /*

   478 	// Print The Steps

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

   480 	{

   481 		ShowMap(&M[i]);

   482 	}

   483 */

   484 	return 0;

   485 

   486 }