--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/sokosold.c	Fri May 05 22:40:45 2006 +0200
@@ -0,0 +1,445 @@
+#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
+ *
+ * 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.
+
+ * 13/01/2002
+ * Comentari afegit el 4/01/2003:
+ * Cerca la solució segons el moviment de caixes, i no el de l'home.
+ * Falta optimitzar: Llocs on no posar caixes segons les caixes (són dinàmics
+ * segons cada element de l'array de mapes!)
+ */
+
+
+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]] == BLANK)
+			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX;
+		else if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM)
+			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM;
+	}
+
+	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("%i", 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++;
+			}
+			else 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++;
+			}
+			else 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++;
+			}
+			else 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)
+			{
+				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)
+			{
+				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)
+			{
+				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)
+			{
+				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;
+}
+
+
+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);
+
+	ShowMap(&Morigin);
+	
+	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(&Morigin);
+
+	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;
+		}
+	}
+
+	// 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
+
+		for (i=0; i < NumMoves; i++)
+		{
+			printf("%c", Moves[i]);
+		}
+		printf("\n");
+*/
+
+		IllegalMove = NumMoves - 1;
+		// Process the combination
+		for (i = OldMaps; i < NumMoves - 1; i++)
+		{
+			CopyMap(&M[i+1], &M[i]);
+			if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))
+			{
+				IllegalMove = i;
+				break;
+			} /*else
+			if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) ||
+				(Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) &&
+				!M[i].BoxMoved)
+			{
+				IllegalMove = i;
+				break;
+			}*/
+			GetManMoves(&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;
+					
+	}
+
+	// Print the combination
+	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");
+
+/*
+	// Print The Steps
+	for (i=0; i < NumMoves; i++)
+	{
+		ShowMap(&M[i]);
+	}
+*/
+	return 0;
+
+}