Recursivity changed into a loop. Now the state is loaded on boot, and saved on TERM.
#include <stdio.h>
#include <string.h>
#define BOX '$'
#define WALL '#'
#define MAN '@'
#define PLATFORM '.'
#define BOXINPLATFORM '*'
#define MANINPLATFORM 'E'
#define BLANK ' '
#define CANTO '-'
#define MANCANMOVE '+'
#define NBOX(n) ((n)<<2)
#define DIR_LEFT 0
#define DIR_RIGHT 1
#define DIR_UP 2
#define DIR_DOWN 3
#define MAX_X 50
#define MAX_Y 50
#define MAX_MOVES 50
#define MAX_BOXES 15
#define MOVE_OK 1
#define MOVE_BOX 2
#define MOVE_ILLEGAL 0
/* SOKOBAN Solution Finder
*
* Input File Format: XSB
*
* XSB Format definition:
* Character matrix of:
* @ MAN
* # WALL
* $ BOX
* * BOX over PLATFORM
* + PLATFORM
* - (optional) Where a BOX should not be put
* Everything that cannot be reached by the man or boxes (WALLS) must be
* marked as is: WALLS.
* All lines must be of the same length.
*/
struct Map
{
char Cells[MAX_Y][MAX_X];
char ManMoves[MAX_Y][MAX_X];
int SizeX, SizeY;
int ManX, ManY;
int NumPlatforms;
int NumBoxesInPlatform;
int BoxX[MAX_BOXES];
int BoxY[MAX_BOXES];
int NumBoxes;
};
void CopyMap (struct Map *Mdest, struct Map *Morig)
{
memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
}
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->SizeY--;
M->SizeX = strlen(M->Cells[0]) - 1;
M->NumPlatforms = 0;
M->NumBoxesInPlatform = 0;
M->NumBoxes = 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;
M->Cells[M->ManY][M->ManX] = BLANK;
}
if (M->Cells[j][i] == PLATFORM)
M->NumPlatforms++;
else if (M->Cells[j][i] == BOXINPLATFORM)
{
M->Cells[j][i] = PLATFORM;
M->NumPlatforms++;
M->NumBoxesInPlatform++;
M->BoxX[M->NumBoxes] = i;
M->BoxY[M->NumBoxes] = j;
M->NumBoxes++;
} else if (M->Cells[j][i] == BOX)
{
M->Cells[j][i] = BLANK;
M->BoxX[M->NumBoxes] = i;
M->BoxY[M->NumBoxes] = j;
M->NumBoxes++;
} else if (M->Cells[j][i] != WALL)
{
if ( (M->Cells[j][i-1] == WALL &&
M->Cells[j-1][i] == WALL) ||
(M->Cells[j][i-1] == WALL &&
M->Cells[j+1][i] == WALL) ||
(M->Cells[j][i+1] == WALL &&
M->Cells[j-1][i] == WALL) ||
(M->Cells[j][i+1] == WALL &&
M->Cells[j+1][i] == WALL))
M->Cells[j][i] = CANTO;
}
}
}
void ShowMap (struct Map *M)
{
struct Map Temp;
int i,j;
CopyMap(&Temp, M);
Temp.Cells[Temp.ManY][Temp.ManX] = MAN;
for (i = 0; i < Temp.NumBoxes; i++)
{
if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM)
Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM;
else
Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX;
}
for (j = 0; j<Temp.SizeY; j++)
{
for (i=0; i<Temp.SizeX; i++)
printf("%c", Temp.Cells[j][i]);
printf("\n");
}
// Print Where the man can move
for (j = 0; j<Temp.SizeY; j++)
{
for (i=0; i<Temp.SizeX; i++)
printf("%c", Temp.ManMoves[j][i]);
printf("\n");
}
printf("Man is at (%i,%i)\n", Temp.ManX, Temp.ManY);
printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
Temp.NumBoxesInPlatform);
}
int InverseMove(char Dir1, char Dir2)
{
if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
return 1;
return 0;
}
void GetManMoves(struct Map *M)
{
int X[MAX_MOVES], Y[MAX_MOVES];
int NewX[MAX_MOVES], NewY[MAX_MOVES];
int NumMoves, NewMoves;
int j, i;
NumMoves = 1;
for (j = 0; j<M->SizeY; j++)
for (i=0; i<M->SizeX; i++)
M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK;
for (i = 0; i<M->NumBoxes; i++)
M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL;
NewMoves = 1;
NewX[0] = M->ManX;
NewY[0] = M->ManY;
while (NewMoves)
{
NumMoves = NewMoves;
for (i=0; i<NewMoves; i++)
{
X[i] = NewX[i];
Y[i] = NewY[i];
}
NewMoves = 0;
for (i=0; i<NumMoves; i++)
{
if(M->ManMoves[Y[i]][X[i]-1] == BLANK)
{
NewX[NewMoves] = X[i]-1;
NewY[NewMoves] = Y[i];
M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE;
NewMoves++;
}
if(M->ManMoves[Y[i]][X[i]+1] == BLANK)
{
NewX[NewMoves] = X[i]+1;
NewY[NewMoves] = Y[i];
M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE;
NewMoves++;
}
if(M->ManMoves[Y[i]-1][X[i]] == BLANK)
{
NewX[NewMoves] = X[i];
NewY[NewMoves] = Y[i]-1;
M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE;
NewMoves++;
}
if(M->ManMoves[Y[i]+1][X[i]] == BLANK)
{
NewX[NewMoves] = X[i];
NewY[NewMoves] = Y[i]+1;
M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE;
NewMoves++;
}
}
}
}
int MoveBox(struct Map *M, int NumBox, int Direction)
{
char InPlatform;
InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM);
switch(Direction)
{
case DIR_LEFT:
if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] ==
MANCANMOVE &&
M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] !=
WALL &&
M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1] !=
CANTO)
{
M->ManX = M->BoxX[NumBox];
M->ManY = M->BoxY[NumBox];
if(InPlatform)
M->NumBoxesInPlatform--;
M->BoxX[NumBox]--;
if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
PLATFORM)
M->NumBoxesInPlatform++;
return 1;
}else return 0;
break;
case DIR_RIGHT:
if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] ==
MANCANMOVE &&
M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] !=
WALL &&
M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] !=
CANTO)
{
M->ManX = M->BoxX[NumBox];
M->ManY = M->BoxY[NumBox];
if(InPlatform)
M->NumBoxesInPlatform--;
M->BoxX[NumBox]++;
if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
PLATFORM)
M->NumBoxesInPlatform++;
return 1;
}else return 0;
break;
case DIR_UP:
if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] ==
MANCANMOVE &&
M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] !=
WALL &&
M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] !=
CANTO)
{
M->ManX = M->BoxX[NumBox];
M->ManY = M->BoxY[NumBox];
if(InPlatform)
M->NumBoxesInPlatform--;
M->BoxY[NumBox]--;
if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
PLATFORM)
M->NumBoxesInPlatform++;
return 1;
}else return 0;
break;
case DIR_DOWN:
if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] ==
MANCANMOVE &&
M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] !=
WALL &&
M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] !=
CANTO)
{
M->ManX = M->BoxX[NumBox];
M->ManY = M->BoxY[NumBox];
if(InPlatform)
M->NumBoxesInPlatform--;
M->BoxY[NumBox]++;
if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
PLATFORM)
M->NumBoxesInPlatform++;
return 1;
}else return 0;
break;
}
return 0;
}
void PrintCombination(int Moves[], int NumMoves)
{
int i;
for (i=0; i < NumMoves; i++)
{
printf("%i", Moves[i] >> 2);
if ((Moves[i] & 0x03) == DIR_LEFT)
printf("L");
else if ((Moves[i] & 0x03) == DIR_RIGHT)
printf("R");
else if ((Moves[i] & 0x03) == DIR_UP)
printf("U");
else
printf("D");
printf(",");
}
printf("\n");
}
int main(int argn, char **argv)
{
struct Map Morigin;
struct Map M[MAX_MOVES+1];
int Moves[MAX_MOVES];
int NumMoves;
int OldMaps;
int IllegalMove;
int Carry;
int i;
if (argn != 3)
{
printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]);
exit(3);
}
ReadMap(&Morigin, argv[1]);
sscanf(argv[2], "%i", &NumMoves);
for (i = 0; i < NumMoves; i++)
Moves[i] = NBOX(0) + DIR_LEFT;
// Reget the original map
CopyMap(&M[0], &Morigin);
CopyMap(&M[NumMoves], &Morigin); // For the first while cond.
GetManMoves(&M[0]);
ShowMap(&M[0]);
IllegalMove = NumMoves - 1;
// Process the combination
for (i = 0; i < NumMoves; i++)
{
CopyMap(&M[i+1], &M[i]);
if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))
{
IllegalMove = i;
break;
}
GetManMoves(&M[i+1]);
}
// Main solution finder loop
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] = NBOX(0) + DIR_LEFT;
// Increase Counter for a new try of moves
for (i = IllegalMove; i >= 0 && Carry; i--)
{
Moves[i]++;
Carry = 0;
if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1)
{ Moves[i] = NBOX(0) + 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] = NBOX(0) + DIR_LEFT;
OldMaps=0;
CopyMap(&M[NumMoves], &Morigin);
// For the first while cond.
printf("Provant %i moviments...\n", NumMoves);
}
}
// Print the combination
// PrintCombination(Moves, NumMoves);
IllegalMove = NumMoves - 1;
// Process the combination
// printf("------- STARTING COMBINATION ------------\n");
for (i = OldMaps; i < NumMoves - 1; i++)
{
CopyMap(&M[i+1], &M[i]);
// GetManMoves(&M[i+1]);
if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))
{
IllegalMove = i;
break;
}/* else // Si el moviment es bo
if ((Moves[i] >> 2) == (Moves[i+1] >> 2) &&
((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 1||
((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 5)))
{
IllegalMove = i;
break;
}*/
GetManMoves(&M[i+1]);
// ShowMap(&M[i+1]);
}
// Here i = NumMoves - 1
CopyMap(&M[i+1], &M[i]);
if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))
IllegalMove = i;
/*
for (i=0;i < IllegalMove; i++)
{
ShowMap(&M[i+1]);
}
*/
}
// Print the combination
PrintCombination(Moves, NumMoves);
/*
// Print The Steps
for (i=0; i < NumMoves; i++)
{
ShowMap(&M[i]);
}
*/
return 0;
}