Adding ignored patterns.
#include <stdio.h>
#include <string.h>
#define BOX '*'
#define WALL '#'
#define MAN '8'
#define PLATFORM '+'
#define BOXINPLATFORM 'O'
#define MANINPLATFORM 'E'
#define BLANK ' '
#define DIR_LEFT 'A'
#define DIR_RIGHT 'B'
#define DIR_UP 'C'
#define DIR_DOWN 'D'
#define MAX_X 50
#define MAX_Y 50
#define MAX_MOVES 50
/* SOKOBAN Solution Finder
*
* Cerca totes les possibilitats de tots els nombres de combinacions possibles,
* menys la que tots els moviments són a l'esquerra del número de combinacions
* incials triat.
*/
struct Map
{
char Cells[MAX_X][MAX_Y];
int SizeX, SizeY;
int ManX, ManY;
int NumPlatforms;
int NumBoxesInPlatform;
};
void ReadMap(struct Map *M, char *FileName)
{
FILE *Fitxer;
int i,j;
if(!(Fitxer = fopen(FileName, "r")))
{
printf("Error opening %s!", FileName);
exit(1);
}
M->SizeX=0;
M->SizeY=0;
while (!feof(Fitxer))
{
fgets(M->Cells[M->SizeY++], MAX_X, Fitxer);
}
M->SizeY--;
M->SizeX = strlen(M->Cells[0]) - 1;
M->NumPlatforms = 0;
M->NumBoxesInPlatform = 0;
for (j = 0; j<M->SizeY; j++)
for (i=0; i<M->SizeX; i++)
{
if (M->Cells[j][i] == MAN)
{ M->ManX = i; M->ManY = j; }
else if (M->Cells[j][i] == PLATFORM)
M->NumPlatforms++;
else if (M->Cells[j][i] == BOXINPLATFORM)
{
M->NumPlatforms++;
M->NumBoxesInPlatform++;
}
}
}
void ShowMap (struct Map *M)
{
int i,j;
for (j = 0; j<M->SizeY; j++)
{
for (i=0; i<M->SizeX; i++)
printf("%c", M->Cells[j][i]);
printf("\n");
}
printf("Man is at (%i,%i)\n", M->ManX, M->ManY);
printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms,
M->NumBoxesInPlatform);
}
void CopyMap (struct Map *Mdest, struct Map *Morig)
{
memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
}
int MoveMan (struct Map *M, int Direction)
{
int NewX, NewY;
/*
// Check if man is where it should be
if (M->Cells[M->ManY][M->ManX] != MAN &&
M->Cells[M->ManY][M->ManX] != MANINPLATFORM)
{
printf("Man isn't where it should be!\n");
exit(2);
}
*/
// Process Movement
if (Direction == DIR_LEFT)
{ NewX = M->ManX - 1; NewY = M->ManY; }
else if (Direction == DIR_RIGHT)
{ NewX = M->ManX + 1; NewY = M->ManY; }
else if (Direction == DIR_UP)
{ NewX = M->ManX; NewY = M->ManY - 1; }
else
{ NewX = M->ManX; NewY = M->ManY + 1; }
// What's in front of the man?
if (M->Cells[NewY][NewX] == WALL)
{
return 0; // ILLEGAL MOVE
}
else if (M->Cells[NewY][NewX] == BOX)
{
if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
BLANK)
{
M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
= BOX;
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MAN;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MAN;
}
M->ManX = NewX; M->ManY = NewY;
return 1;
}
else
if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
PLATFORM)
{
M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
= BOXINPLATFORM;
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MAN;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MAN;
}
M->ManX = NewX; M->ManY = NewY;
M->NumBoxesInPlatform++;
return 1;
}
else
{
return 0; // ILLEGAL MOVE
}
}else
if (M->Cells[NewY][NewX] == BOXINPLATFORM)
{
if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
BLANK)
{
M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
= BOX;
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
M->ManX = NewX; M->ManY = NewY;
M->NumBoxesInPlatform--;
return 1;
}
else
if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
PLATFORM)
{
M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
= BOXINPLATFORM;
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
M->ManX = NewX; M->ManY = NewY;
return 1;
}
else
{
return 0; // ILLEGAL MOVE
}
}
else if (M->Cells[NewY][NewX] == PLATFORM)
{
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MANINPLATFORM;
}
M->ManX = NewX; M->ManY = NewY;
return 1;
}
else if (M->Cells[NewY][NewX] == BLANK) // IF not needed
{
if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
{ // Man is over Platform
M->Cells[M->ManY][M->ManX] = PLATFORM;
M->Cells[NewY][NewX] = MAN;
}
else // Man is over Blank
{
M->Cells[M->ManY][M->ManX] = BLANK;
M->Cells[NewY][NewX] = MAN;
}
M->ManX = NewX; M->ManY = NewY;
return 1;
}
return 1;
}
int main()
{
struct Map Morigin;
struct Map M[MAX_MOVES+1];
char Moves[MAX_MOVES];
int NumMoves;
int OldMaps;
int IllegalMove;
int Carry;
int i;
ReadMap(&Morigin, "model");
ShowMap(&Morigin);
printf("Numero de moviments inicials a provar: ");
scanf("%i", &NumMoves);
IllegalMove = NumMoves - 1;
for (i = 0; i < NumMoves; i++)
Moves[i] = DIR_LEFT;
// Reget the original map
CopyMap(&M[0], &Morigin);
CopyMap(&M[NumMoves], &Morigin); // For the first while cond.
IllegalMove = NumMoves - 1;
// Process the combination
for (i = 0; i < NumMoves; i++)
{
CopyMap(&M[i+1], &M[i]);
if (!MoveMan(&M[i+1], Moves[i]))
{
IllegalMove = i;
break;
}
}
// Process the combinations.
// Order: Left, Right, Up, Down
while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform)
{
// Increase the Counter
{
Carry = 1;
// Reset the direction of sure-invalid moves
for (i = IllegalMove + 1; i < NumMoves; i++)
Moves[i] = DIR_LEFT;
// Increase Counter for a new try of moves
for (i = IllegalMove; i >= 0 && Carry; i--)
{
Moves[i]++;
Carry = 0;
if (Moves[i] == DIR_DOWN + 1)
{ Moves[i] = DIR_LEFT; Carry = 1; }
}
OldMaps = i+1; // Sure? I think it's i+1
// If we change the number of movements for solution
if (Carry)
{
if (NumMoves > MAX_MOVES)
break; // MAX MOVES EXCEEDED!!!
NumMoves++;
for (i = 0; i < NumMoves; i++)
Moves[i] = DIR_LEFT;
OldMaps=0;
CopyMap(&M[NumMoves], &Morigin);
// For the first while cond.
printf("Provant %i moviments...\n", NumMoves);
}
}
/*
// Print the combination
for (i=0; i < NumMoves; i++)
{
printf("%c", Moves[i]);
}
printf("\n");
*/
IllegalMove = NumMoves - 1;
// Process the combination
for (i = OldMaps; i < NumMoves; i++)
{
CopyMap(&M[i+1], &M[i]);
if (!MoveMan(&M[i+1], Moves[i]))
{
IllegalMove = i;
break;
}
}
}
// Print the combination
for (i=0; i < NumMoves; i++)
{
printf("%c", Moves[i]);
}
printf("\n");
/*
// Print The Steps
strcpy(Moves, "DDDRUU");
for (i=0; i < 6; i++)
{
printf("%i", MoveMan(&M, Moves[i]));
ShowMap(&M);
}
*/
return 0;
}