--- a/sokosol5.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,486 +0,0 @@
-#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;
-
-}