# HG changeset patch
# User viric@llimona
# Date 1146864033 -7200
# Node ID 29cc57a9678e4a0e34006df1d7bdc28d8bf96ed0
# Parent  415159228618b09654d0725f617d67aabc4e8d55
Moving the files to appropiate locations.



diff -r 415159228618 -r 29cc57a9678e Makefile
--- a/Makefile	Fri May 05 23:18:24 2006 +0200
+++ b/Makefile	Fri May 05 23:20:33 2006 +0200
@@ -1,13 +1,10 @@
 CC=gcc
 
 # OPT
-CFLAGS=-march=athlon-xp -pipe -O3 -Wall
+#CFLAGS=-march=athlon-xp -pipe -O3 -Wall
 
 # DEBUG
-#CFLAGS=-Wall -g -pg
-#LDFLAGS=-pg
+CFLAGS=-Wall -g -pg
+LDFLAGS=-pg
 
-all: sokosold2 sokosol5 sokosol-profund
-sokosold2: sokosold2.o
-sokosol5: sokosol5.o
-sokosol-profund: sokosol-profund.o
+all: sokosol
diff -r 415159228618 -r 29cc57a9678e old/sokosol-branques.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol-branques.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,381 @@
+#include <stdio.h>
+#include <string.h>
+
+#define BOX '*'
+#define WALL '#'
+#define MAN '8'
+#define PLATFORM '+'
+#define BOXINPLATFORM 'O'
+#define MANINPLATFORM 'E'
+#define BLANK ' '
+#define CANTO '-'
+
+#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 100
+
+#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.
+ */
+
+
+struct Map
+{
+	char Cells[MAX_X][MAX_Y];
+	int SizeX, SizeY;
+	int ManX, ManY;
+	int NumPlatforms;
+	int NumBoxesInPlatform;
+	char BoxMoved;		// Boolean
+};
+
+
+
+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; }
+			if (M->Cells[j][i] == PLATFORM)
+				M->NumPlatforms++;
+			else if (M->Cells[j][i] == BOXINPLATFORM)
+			{
+				M->NumPlatforms++;
+				M->NumBoxesInPlatform++;
+			} 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;
+		}
+
+	M->Cells[M->ManY][M->ManX] = BLANK;
+	M->BoxMoved = 0;	// Needed?
+}
+
+
+void CopyMap (struct Map *Mdest, struct Map *Morig)
+{
+	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
+}
+
+
+void ShowMap (struct Map *M)
+{
+	struct Map TempMap;
+	int i,j;
+
+	CopyMap(&TempMap, M);
+
+	if (TempMap.Cells[TempMap.ManY][TempMap.ManX] == BLANK)
+		TempMap.Cells[TempMap.ManY][TempMap.ManX] = MAN;
+	else
+		TempMap.Cells[TempMap.ManY][TempMap.ManX] = MANINPLATFORM;
+	
+	for (j = 0; j<TempMap.SizeY; j++)
+	{
+		for (i=0; i<TempMap.SizeX; i++)
+			printf("%c", TempMap.Cells[j][i]);
+		printf("\n");
+	}
+	printf("Man is at (%i,%i)\n", TempMap.ManX, TempMap.ManY);
+	printf("Platforms: %i, BoxesInPlatform: %i\n", TempMap.NumPlatforms,
+			TempMap.NumBoxesInPlatform);
+}
+
+
+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 MOVE_ILLEGAL;	// ILLEGAL MOVE
+	}
+	else if (M->Cells[NewY][NewX] == BOX)
+	{
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+			BLANK)
+		{
+			M->Cells[NewY][NewX] = BLANK;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOX;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+				PLATFORM)
+		{
+			M->Cells[NewY][NewX] = BLANK;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOXINPLATFORM;
+
+			M->ManX = NewX; M->ManY = NewY;
+
+			M->NumBoxesInPlatform++;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		{
+			return MOVE_ILLEGAL;	// ILLEGAL MOVE
+		}
+	}else
+	if (M->Cells[NewY][NewX] == BOXINPLATFORM)
+	{
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+			BLANK)
+		{
+			M->Cells[NewY][NewX] = PLATFORM;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOX;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->NumBoxesInPlatform--;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+				PLATFORM)
+		{
+			M->Cells[NewY][NewX] = PLATFORM;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOXINPLATFORM;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		{
+			return MOVE_ILLEGAL;	// ILLEGAL MOVE
+		}
+	}
+	else
+	{
+		M->ManX = NewX; M->ManY = NewY;
+		M->BoxMoved = 0;
+		return MOVE_OK;
+	}
+	
+	// Not Reachable
+	return MOVE_ILLEGAL;
+}
+
+int InverseMove(char Dir1, char Dir2)
+{
+	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
+		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
+		return 1;
+	return 0;
+}
+
+int main()
+{
+	struct Map Morigin;
+	struct Map M[MAX_MOVES+1];
+	char Moves[MAX_MOVES];
+	int NumMoves;
+	int OldMaps;
+	int IllegalMove;
+	int Carry;
+	int MoveResult;
+	int Solution;
+
+	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
+	Solution = 0;
+	while (Solution == 0)
+	{
+		// 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)
+			{
+				printf("No Solution Found\n");
+				NumMoves = 0;
+				Solution = 1;
+				break;
+			}
+		}
+
+/*
+		// 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 (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
+			{
+				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;
+			}
+			if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform)
+			{
+				Solution = i+1;
+				break;
+			}
+				
+		}
+		// Here i = NumMoves - 1
+		CopyMap(&M[i+1], &M[i]);
+		if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
+			IllegalMove = i;
+		if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform &&
+			Solution == 0)
+		{
+			Solution = i+1;
+			break;
+		}
+					
+	}
+
+	// Print the combination
+	for (i=0; i < NumMoves; i++)
+	{
+		if (Moves[i] == DIR_LEFT)
+			printf("L");
+		else if (Moves[i] == DIR_RIGHT)
+			printf("R");
+		else if (Moves[i] == DIR_UP)
+			printf("U");
+		else if (Moves[i] == DIR_DOWN)
+			printf("D");
+	}
+	printf("\n");
+
+/*
+	// Print The Steps
+	for (i=0; i < NumMoves; i++)
+	{
+		ShowMap(&M[i]);
+	}
+	return 0;
+*/
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosol.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,381 @@
+#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 500
+#define MAX_Y 500
+#define MAX_MOVES 100
+
+/* 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 if (Direction == DIR_DOWN)		// if not needed
+	{ 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(int argn, char **argv)
+{
+	struct Map Morigin, M[MAX_MOVES];
+	char Moves[MAX_MOVES];
+	int NumMoves;
+	int OldMaps;
+	int IllegalMove;
+	int Carry;
+
+	int i, j;
+
+	if (argn != 2)
+	{
+		printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]);
+		exit(3);
+	}
+
+	ReadMap(&Morigin, argv[1]);
+	sscanf(argv[2], "%i", &NumMoves);
+
+	ShowMap(&Morigin);
+
+	CopyMap(&M, &Morigin);
+
+	IllegalMove = NumMoves - 1;
+
+	for (i = 0; i < NumMoves; i++)
+		Moves[i] = DIR_LEFT;
+
+	// Reget the original map
+	CopyMap(&M[0], &Morigin);
+
+	OldMaps = 0;
+
+	IllegalMove = NumMoves - 1;
+	// Process the combination
+	for (i = 0; i < NumMoves; i++)
+	{
+		CopyMap(&M[i+1], &M[i]);
+		// Could we use OldMaps for indexing, as faster than i+1?
+		if (!MoveMan(&M[i+1], Moves[i]))
+		{
+			IllegalMove = i;
+			break;
+		}
+	}
+
+	// Process the combinations.
+	// Order: Left, Right, Up, Down
+	while (M.NumPlatforms != M.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]++;
+				if (Moves[i] == DIR_DOWN + 1)
+				{ Moves[i] = DIR_LEFT; Carry = 1; }
+			}
+			OldMaps = i;	// Sure?
+			// 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;
+				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 = 0; i < NumMoves; i++)
+		{
+			if (i>=OldMaps)
+			{
+				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);
+	}
+*/
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosol2.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol2.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,311 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#define BOX '*'
+#define WALL '#'
+#define MAN '8'
+#define PLATFORM '+'
+#define BOXINPLATFORM 'O'
+#define MANINPLATFORM 'E'
+#define BLANK ' '
+
+#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 100
+
+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 if (Direction == DIR_DOWN)		// if not needed
+	{ 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;
+		}
+		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++;
+		}
+		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--;
+		}
+		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;
+		}
+		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;
+	}
+	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;
+}
+
+int main()
+{
+	struct Map Morigin, M;
+	char Moves[MAX_MOVES];
+	int NumMoves;
+	int IllegalMove;
+	int Carry;
+	int Arrel;
+
+	int i, j;
+
+	ReadMap(&Morigin, "model");
+
+	ShowMap(&Morigin);
+
+	CopyMap(&M, &Morigin);
+
+	printf("Numero de moviments a provar: ");
+	scanf("%i", &NumMoves);
+	printf("Arrel: ");
+	scanf("%i", &Arrel);
+	srand(Arrel);
+
+	// Process the combinations.
+	// Order: Left, Right, Up, Down
+	while (M.NumPlatforms != M.NumBoxesInPlatform)
+	{
+		// Reget the original map
+		CopyMap(&M, &Morigin);
+
+/*
+		// Print the combination
+
+		for (i=0; i < NumMoves; i++)
+		{
+			printf("%c", Moves[i]);
+		}
+		printf("\n");
+*/
+
+		// Process the combination
+		for (i = 0; i < NumMoves; i++)
+		{
+			if (!MoveMan(&M, Moves[i]=rand()%4))
+				break;
+		}
+					
+	}
+
+	// Print the combination
+	for (i=0; i < NumMoves; i++)
+	{
+		printf("%c", Moves[i]+48);
+	}
+	printf("\n");
+
+/*
+	// Print The Steps
+	strcpy(Moves, "DDDRUU");
+
+	for (i=0; i < 6; i++)
+	{
+		printf("%i", MoveMan(&M, Moves[i]));
+		ShowMap(&M);
+	}
+*/
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosol3.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol3.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,375 @@
+#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;
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosol4.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol4.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,366 @@
+#include <stdio.h>
+#include <string.h>
+
+#define BOX '$'
+#define WALL '#'
+#define MAN '@'
+#define PLATFORM '.'
+#define BOXINPLATFORM '*'
+#define MANINPLATFORM 'E'
+#define BLANK ' '
+#define CANTO '-'
+
+#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
+
+#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.
+ */
+
+
+struct Map
+{
+	char Cells[MAX_X][MAX_Y];
+	int SizeX, SizeY;
+	int ManX, ManY;
+	int NumPlatforms;
+	int NumBoxesInPlatform;
+	char BoxMoved;		// Boolean
+};
+
+
+
+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; }
+			if (M->Cells[j][i] == PLATFORM)
+				M->NumPlatforms++;
+			else if (M->Cells[j][i] == BOXINPLATFORM)
+			{
+				M->NumPlatforms++;
+				M->NumBoxesInPlatform++;
+			} 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;
+		}
+
+	M->Cells[M->ManY][M->ManX] = BLANK;
+	M->BoxMoved = 0;	// Needed?
+}
+
+
+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 MOVE_ILLEGAL;	// ILLEGAL MOVE
+	}
+	else if (M->Cells[NewY][NewX] == BOX)
+	{
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+			BLANK)
+		{
+			M->Cells[NewY][NewX] = BLANK;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOX;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+				PLATFORM)
+		{
+			M->Cells[NewY][NewX] = BLANK;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOXINPLATFORM;
+
+			M->ManX = NewX; M->ManY = NewY;
+
+			M->NumBoxesInPlatform++;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		{
+			return MOVE_ILLEGAL;	// ILLEGAL MOVE
+		}
+	}else
+	if (M->Cells[NewY][NewX] == BOXINPLATFORM)
+	{
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+			BLANK)
+		{
+			M->Cells[NewY][NewX] = PLATFORM;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOX;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->NumBoxesInPlatform--;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
+				PLATFORM)
+		{
+			M->Cells[NewY][NewX] = PLATFORM;
+			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
+				= BOXINPLATFORM;
+
+			M->ManX = NewX; M->ManY = NewY;
+			M->BoxMoved = 1;
+			return MOVE_BOX;
+		}
+		else
+		{
+			return MOVE_ILLEGAL;	// ILLEGAL MOVE
+		}
+	}
+	else
+	{
+		M->ManX = NewX; M->ManY = NewY;
+		M->BoxMoved = 0;
+		return MOVE_OK;
+	}
+	
+	// Not Reachable
+	return MOVE_ILLEGAL;
+}
+
+int InverseMove(char Dir1, char Dir2)
+{
+	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
+		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
+		return 1;
+	return 0;
+}
+
+int main(int argn, char **argv)
+{
+	struct Map Morigin;
+	struct Map M[MAX_MOVES+1];
+	char Moves[MAX_MOVES];
+	int NumMoves;
+	int OldMaps;
+	int IllegalMove;
+	int Carry;
+	int MoveResult;
+
+	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] = 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 - 1; i++)
+		{
+			CopyMap(&M[i+1], &M[i]);
+			if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
+			{
+				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;
+			}
+				
+		}
+		// Here i = NumMoves - 1
+		CopyMap(&M[i+1], &M[i]);
+		if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
+			IllegalMove = i;
+					
+	}
+
+	// Print the combination
+	for (i=0; i < NumMoves; i++)
+	{
+		if (Moves[i] == DIR_LEFT)
+			printf("L");
+		else if (Moves[i] == DIR_RIGHT)
+			printf("R");
+		else if (Moves[i] == DIR_UP)
+			printf("U");
+		else if (Moves[i] == DIR_DOWN)
+			printf("D");
+	}
+	printf("\n");
+
+/*
+	// Print The Steps
+	for (i=0; i < NumMoves; i++)
+	{
+		ShowMap(&M[i]);
+	}
+*/
+	return 0;
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosol5.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosol5.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,486 @@
+#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;
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosold.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosold.c	Fri May 05 23:20:33 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;
+
+}
diff -r 415159228618 -r 29cc57a9678e old/sokosold2.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/old/sokosold2.c	Fri May 05 23:20:33 2006 +0200
@@ -0,0 +1,543 @@
+#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_MANMOVES 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!)
+ *
+ * Diria que el programa no es deixa cap branca de l'arbre de backtracking
+ */
+
+
+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;
+			}
+				
+		}
+
+	if(M->NumBoxes > M->NumPlatforms)
+	{
+		printf("More boxes than platforms!\n");
+		exit(2);
+	}
+}
+
+
+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("%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_MANMOVES], Y[MAX_MANMOVES];
+	int NewX[MAX_MANMOVES], NewY[MAX_MANMOVES];
+	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;
+	M->ManMoves[M->ManY][M->ManX] = MANCANMOVE;
+	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++;
+			}
+		}
+	}
+}
+
+
+/* Returns bool */
+char IsStupidPos(struct Map *M, int X, int Y)
+{
+	struct Map MTemp;
+	int NumBoxes, NumWalls, NumBoxesInPlatform;
+	int j, i;
+
+	CopyMap(&MTemp, M);
+
+
+	for (i = 0; i<MTemp.NumBoxes; i++)
+		if (MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] == PLATFORM)
+			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] =
+			BOXINPLATFORM;
+		else
+			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] = BOX;
+
+//	ShowMap(&MTemp);
+
+	/* We don't verify if j<=Y or i<=X is outside the map. It shouldn't
+	 * be, as it will be called with X,Y pair beeing the coordinates of a
+	 * Box!
+	 */
+	for (j = Y-1; j<=Y; j++)
+		for (i=X-1; i<=X; i++)
+		{
+			NumBoxes = NumWalls = NumBoxesInPlatform = 0;
+			/* Up-Left Cell */
+			if (MTemp.Cells[j][i] == WALL)
+				NumWalls++;
+			else if (MTemp.Cells[j][i] == BOX)
+				NumBoxes++;
+			else if (MTemp.Cells[j][i] == BOXINPLATFORM)
+				NumBoxesInPlatform++;
+			/* Up-Right Cell */
+			if (MTemp.Cells[j][i+1] == WALL)
+				NumWalls++;
+			else if (MTemp.Cells[j][i+1] == BOX)
+				NumBoxes++;
+			else if (MTemp.Cells[j][i+1] == BOXINPLATFORM)
+				NumBoxesInPlatform++;
+			/* Down-Right Cell */
+			if (MTemp.Cells[j+1][i+1] == WALL)
+				NumWalls++;
+			else if (MTemp.Cells[j+1][i+1] == BOX)
+				NumBoxes++;
+			else if (MTemp.Cells[j+1][i+1] == BOXINPLATFORM)
+				NumBoxesInPlatform++;
+			/* Down-Left Cell */
+			if (MTemp.Cells[j+1][i] == WALL)
+				NumWalls++;
+			else if (MTemp.Cells[j+1][i] == BOX)
+				NumBoxes++;
+			else if (MTemp.Cells[j+1][i] == BOXINPLATFORM)
+				NumBoxesInPlatform++;
+
+			if ((NumBoxesInPlatform + NumBoxes + NumWalls == 4) &&
+				(NumBoxes >= 1)) 
+				return MOVE_ILLEGAL;
+		}
+
+	return MOVE_OK;
+}
+
+
+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) )
+			{
+				if(InPlatform)
+					M->NumBoxesInPlatform--;
+				M->BoxX[NumBox]--;
+				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
+					PLATFORM)
+					M->NumBoxesInPlatform++;
+				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
+			}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->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]+1]
+				!= CANTO) )
+			{
+				if(InPlatform)
+					M->NumBoxesInPlatform--;
+				M->BoxX[NumBox]++;
+				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
+					PLATFORM)
+					M->NumBoxesInPlatform++;
+				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
+			}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->Cells[M->BoxY[NumBox]-1][M->BoxX[NumBox]]
+				!= CANTO) )
+			{
+				if(InPlatform)
+					M->NumBoxesInPlatform--;
+				M->BoxY[NumBox]--;
+				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
+					PLATFORM)
+					M->NumBoxesInPlatform++;
+				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
+			}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->Cells[M->BoxY[NumBox]+1][M->BoxX[NumBox]]
+				!= CANTO) )
+			{
+				if(InPlatform)
+					M->NumBoxesInPlatform--;
+				M->BoxY[NumBox]++;
+				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
+					PLATFORM)
+					M->NumBoxesInPlatform++;
+				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
+			}else return 0;
+			break;
+	}
+	/* Check for stupid movement */
+	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);
+
+	//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(&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;
+		}
+	}
+
+	// Main solution finder loop
+	while (!(M[NumMoves].NumPlatforms == M[NumMoves].NumBoxesInPlatform && 
+	IllegalMove == -1))
+	{
+		// Increase the Counter
+		{
+			Carry = 1;
+			// If last combination was legal
+			if (IllegalMove == -1)
+				IllegalMove = NumMoves -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);
+				fflush(stdout);
+			}
+		}
+
+
+		// First assume combination is legal
+		IllegalMove = -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;
+			}*/
+			// For next map:
+			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;
+		//ShowMap(&M[i+1]);
+
+		//printf("IM: %i\n", IllegalMove);
+					
+	}
+
+	// Print the combination
+	PrintCombination(Moves, NumMoves);
+/*
+	// Print The Steps
+	for (i=0; i < NumMoves; i++)
+	{
+		ShowMap(&M[i]);
+	}
+*/
+	return 0;
+
+}
diff -r 415159228618 -r 29cc57a9678e sokosol-branques.c
--- a/sokosol-branques.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,381 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-
-#define BOX '*'
-#define WALL '#'
-#define MAN '8'
-#define PLATFORM '+'
-#define BOXINPLATFORM 'O'
-#define MANINPLATFORM 'E'
-#define BLANK ' '
-#define CANTO '-'
-
-#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 100
-
-#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.
- */
-
-
-struct Map
-{
-	char Cells[MAX_X][MAX_Y];
-	int SizeX, SizeY;
-	int ManX, ManY;
-	int NumPlatforms;
-	int NumBoxesInPlatform;
-	char BoxMoved;		// Boolean
-};
-
-
-
-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; }
-			if (M->Cells[j][i] == PLATFORM)
-				M->NumPlatforms++;
-			else if (M->Cells[j][i] == BOXINPLATFORM)
-			{
-				M->NumPlatforms++;
-				M->NumBoxesInPlatform++;
-			} 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;
-		}
-
-	M->Cells[M->ManY][M->ManX] = BLANK;
-	M->BoxMoved = 0;	// Needed?
-}
-
-
-void CopyMap (struct Map *Mdest, struct Map *Morig)
-{
-	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
-}
-
-
-void ShowMap (struct Map *M)
-{
-	struct Map TempMap;
-	int i,j;
-
-	CopyMap(&TempMap, M);
-
-	if (TempMap.Cells[TempMap.ManY][TempMap.ManX] == BLANK)
-		TempMap.Cells[TempMap.ManY][TempMap.ManX] = MAN;
-	else
-		TempMap.Cells[TempMap.ManY][TempMap.ManX] = MANINPLATFORM;
-	
-	for (j = 0; j<TempMap.SizeY; j++)
-	{
-		for (i=0; i<TempMap.SizeX; i++)
-			printf("%c", TempMap.Cells[j][i]);
-		printf("\n");
-	}
-	printf("Man is at (%i,%i)\n", TempMap.ManX, TempMap.ManY);
-	printf("Platforms: %i, BoxesInPlatform: %i\n", TempMap.NumPlatforms,
-			TempMap.NumBoxesInPlatform);
-}
-
-
-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 MOVE_ILLEGAL;	// ILLEGAL MOVE
-	}
-	else if (M->Cells[NewY][NewX] == BOX)
-	{
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-			BLANK)
-		{
-			M->Cells[NewY][NewX] = BLANK;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOX;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-				PLATFORM)
-		{
-			M->Cells[NewY][NewX] = BLANK;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOXINPLATFORM;
-
-			M->ManX = NewX; M->ManY = NewY;
-
-			M->NumBoxesInPlatform++;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		{
-			return MOVE_ILLEGAL;	// ILLEGAL MOVE
-		}
-	}else
-	if (M->Cells[NewY][NewX] == BOXINPLATFORM)
-	{
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-			BLANK)
-		{
-			M->Cells[NewY][NewX] = PLATFORM;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOX;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->NumBoxesInPlatform--;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-				PLATFORM)
-		{
-			M->Cells[NewY][NewX] = PLATFORM;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOXINPLATFORM;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		{
-			return MOVE_ILLEGAL;	// ILLEGAL MOVE
-		}
-	}
-	else
-	{
-		M->ManX = NewX; M->ManY = NewY;
-		M->BoxMoved = 0;
-		return MOVE_OK;
-	}
-	
-	// Not Reachable
-	return MOVE_ILLEGAL;
-}
-
-int InverseMove(char Dir1, char Dir2)
-{
-	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
-		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
-		return 1;
-	return 0;
-}
-
-int main()
-{
-	struct Map Morigin;
-	struct Map M[MAX_MOVES+1];
-	char Moves[MAX_MOVES];
-	int NumMoves;
-	int OldMaps;
-	int IllegalMove;
-	int Carry;
-	int MoveResult;
-	int Solution;
-
-	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
-	Solution = 0;
-	while (Solution == 0)
-	{
-		// 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)
-			{
-				printf("No Solution Found\n");
-				NumMoves = 0;
-				Solution = 1;
-				break;
-			}
-		}
-
-/*
-		// 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 (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
-			{
-				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;
-			}
-			if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform)
-			{
-				Solution = i+1;
-				break;
-			}
-				
-		}
-		// Here i = NumMoves - 1
-		CopyMap(&M[i+1], &M[i]);
-		if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
-			IllegalMove = i;
-		if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform &&
-			Solution == 0)
-		{
-			Solution = i+1;
-			break;
-		}
-					
-	}
-
-	// Print the combination
-	for (i=0; i < NumMoves; i++)
-	{
-		if (Moves[i] == DIR_LEFT)
-			printf("L");
-		else if (Moves[i] == DIR_RIGHT)
-			printf("R");
-		else if (Moves[i] == DIR_UP)
-			printf("U");
-		else if (Moves[i] == DIR_DOWN)
-			printf("D");
-	}
-	printf("\n");
-
-/*
-	// Print The Steps
-	for (i=0; i < NumMoves; i++)
-	{
-		ShowMap(&M[i]);
-	}
-	return 0;
-*/
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosol-profund.c
--- a/sokosol-profund.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,856 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include <assert.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <signal.h>
-
-#define BOX '$'
-#define WALL '#'
-#define MAN '@'
-#define PLATFORM '.'
-#define BOXINPLATFORM '*'
-#define MANINPLATFORM 'E'
-#define BLANK ' '
-#define CORNER '-'
-#define MANCANMOVE '+'
-
-#define NBOX(n) ((n)<<2)
-
-//#define DEBUG
-
-enum
-{
-	ALARM_SECONDS=1
-};
-
-
-enum logic
-{
-	TRUE=1,
-	FALSE=0,
-};
-
-#define MAX_X 50
-#define MAX_Y 50
-#define MAX_MOVES 50
-#define MAX_STEPS 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 Position
-{
-	int x;
-	int y;
-};
-
-struct Map
-{
-	char Cells[MAX_Y][MAX_X];
-	char cells_boxes[MAX_Y][MAX_X];
-	char man_moves[MAX_Y][MAX_X];
-	int SizeX, SizeY;
-	struct Position Man;
-	int NumPlatforms;
-	int NumBoxesInPlatform;
-	struct Position Box[MAX_BOXES];
-	int NumBoxes;
-};
-
-
-
-enum e_direction
-{
-	DIR_LEFT,
-	DIR_RIGHT,
-	DIR_DOWN,
-	DIR_UP
-};
-const struct Position move_vectors[4] = {
-	{0, 1},
-	{0, -1},
-	{1, 0},
-	{-1, 0}};
-
-struct BoxMove
-{
-	int box;
-	struct Position dir;
-};
-
-float percent_to_show = 0;
-int depth_to_show = 0;
-
-int max_depth = 0;
-int min_depth_period = 0;
-int max_depth_period = 0;
-struct Map * actual_map;
-
-
-
-
-void CopyMap (struct Map *Mdest, const 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->Man.x = i; M->Man.y = j; 
-				M->Cells[M->Man.y][M->Man.x] = 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->Box[M->NumBoxes].x = i;
-				M->Box[M->NumBoxes].y = j;
-				M->NumBoxes++;
-			} else if (M->Cells[j][i] == BOX)
-			{
-				M->Cells[j][i] = BLANK;
-
-				M->Box[M->NumBoxes].x = i;
-				M->Box[M->NumBoxes].y = j;
-				M->NumBoxes++;
-			} else if (M->Cells[j][i] == CORNER)
-			{
-				M->Cells[j][i] = CORNER;
-			} 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] = CORNER;
-			}
-				
-		}
-
-}
-
-
-void ShowMap (const struct Map *M)
-{
-	struct Map Temp;
-	int i,j;
-
-	CopyMap(&Temp, M);
-
-	Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN;
-
-	for (i = 0; i < Temp.NumBoxes; i++)
-	{
-		if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM)
-			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM;
-		else
-			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX;
-	}
-
-	for (j = 0; j<Temp.SizeY; j++)
-	{
-		for (i=0; i<Temp.SizeX; i++)
-			fprintf(stderr,"%c", Temp.Cells[j][i]);
-		fprintf(stderr,"\n");
-	}
-
-#if 0
-	// 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");
-	}
-#endif
-
-	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
-	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 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");
-}
-
-#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
- Situation:
-    
-  ->@$ #
-      $
-*/
-int box_will_be_blocked(const struct Map * m, const struct Position mov,
-	const struct Position box_pos)
-{
-	struct Position next_pos2, tmp, tmp2[2];
-	int i;
-
-	next_pos2.x = box_pos.x + mov.x;
-	next_pos2.y = box_pos.y + mov.y;
-
-	tmp.x = next_pos2.x + mov.x;
-	tmp.y = next_pos2.y + mov.y;
-	tmp2[0].x = next_pos2.x + mov.y;
-	tmp2[0].y = next_pos2.y + mov.x;
-	tmp2[1].x = next_pos2.x - mov.y;
-	tmp2[1].y = next_pos2.y - mov.x;
-	for (i=0; i < 2; i++)
-	{
-		if (m->man_moves[tmp.y][tmp.x] == WALL &&
-			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
-		{
-			return TRUE;
-		}
-		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
-			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)
-		{
-			return TRUE;
-		}
-		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
-			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
-		{
-			return TRUE;
-		}
-	}
-
-	return FALSE;
-}
-
-int is_corner_area(const struct Map * m, const struct Position p,
-	const struct Position box, const struct Position new_box)
-{
-	int NumMoves, NewMoves;
-	struct Position pos[MAX_MOVES];
-	struct Position new_pos[MAX_MOVES];
-	char corners[MAX_Y][MAX_X];
-	int i,j;
-	struct Position next_pos;
-	char *next_cell;
-
-
-	/* Blank the garden */
-	for (j = 0; j<m->SizeY; j++)
-		for (i=0; i<m->SizeX; i++)
-			corners[j][i] = m->Cells[j][i];
-
-	/* Let's put the boxes */
-	for (i = 0; i<m->NumBoxes; i++)
-		corners[m->Box[i].y][m->Box[i].x] = BOX;
-
-	/* Let's put our box - it can be simply added */
-	corners[new_box.y][new_box.x] = BOX;
-	/* Let's remove the original box. */
-	corners[box.y][box.x] = BLANK;
-
-	NewMoves = 1;
-	new_pos[0] = p;
-	while (NewMoves > 0)
-	{
-		/* The before named "New Moves" become the moves we have
-		   to analyze */
-		NumMoves = NewMoves;
-		for (i=0; i<NewMoves; i++)
-		{
-			pos[i] = new_pos[i];
-		}
-
-		/* Search new positions for each position */
-		NewMoves = 0;
-		for (i=0; i<NumMoves; i++)
-		{
-			/* For each direction */
-			for (j=0; j<4; j++)
-			{
-				next_pos.x = pos[i].x + move_vectors[j].x;
-				next_pos.y = pos[i].y + move_vectors[j].y;
-				next_cell = &corners[next_pos.y][next_pos.x];
-				if(*next_cell == BLANK ||
-					*next_cell == PLATFORM)
-				{
-					return FALSE;
-				}
-				else if(*next_cell == CORNER)
-				{
-					new_pos[NewMoves] = next_pos;
-					*next_cell = MANCANMOVE;
-					NewMoves++;
-				}
-			}
-		}
-	}
-
-	return TRUE;
-}
-
-int does_box_close_corners(const struct Map * m, const struct Position mov,
-	const struct Position box_pos)
-{
-	struct Position p, p2;
-
-	p.x = box_pos.x + mov.x;
-	p.y = box_pos.y + mov.y;
-	
-	/* Let's plan the checks */
-	/* The point will be marked with a MANCANMOVE */
-	p2.x = p.x + mov.x;
-	p2.y = p.y + mov.y;
-	if (m->Cells[p2.y][p2.x] == CORNER)
-	{
-		if (is_corner_area(m, p2, box_pos, p))
-			return TRUE;
-	}
-
-	p2.x = p.x + mov.y;
-	p2.y = p.y + mov.x;
-	if (m->Cells[p2.y][p2.x] == CORNER)
-	{
-		if (is_corner_area(m, p2, box_pos, p))
-			return TRUE;
-	}
-
-	p2.x = p.x - mov.y;
-	p2.y = p.y - mov.x;
-	if (m->Cells[p2.y][p2.x] == CORNER)
-	{
-		if (is_corner_area(m, p2, box_pos, p))
-			return TRUE;
-	}
-	return FALSE;
-}
-#endif
-
-/*
-Catch the situation where a box is moved next to a corner, where the box
-next to it will not be able to be moved.
-*/
-int is_dead1(const struct Map * m, const struct Position mov,
-	const struct Position new_pos)
-{
-	struct Position opposite1, opposite2;
-
-	/* The wall corners must exist */
-	opposite1.x = -mov.y;
-	opposite1.y = -mov.x;
-	opposite2.x = mov.y;
-	opposite2.y = mov.x;
-
-#ifdef DEBUG
-	ShowMap(m);
-#endif
-
-	/* Test the first corner */
-	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
-		== WALL)
-	{
-		/* Test wall at opposites 1*/
-		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
-			== WALL &&
-			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
-		{
-				return TRUE;
-		}
-		else
-		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
-			== BOX &&
-			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
-		{
-				return TRUE;
-		}
-		/* Test wall at opposites 2 */
-		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
-			== WALL &&
-			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
-		{
-				return TRUE;
-		}
-		else
-		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
-			== BOX &&
-			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
-		{
-				return TRUE;
-		}
-	}
-
-	/* Test the second corner */
-	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
-		== WALL)
-	{
-		/* Test wall at opposites 1*/
-		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
-			== WALL &&
-			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
-		{
-				return TRUE;
-		}
-		else
-		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
-			== BOX &&
-			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
-		{
-				return TRUE;
-		}
-		/* Test wall at opposites 2 */
-		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
-			== WALL &&
-			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
-		{
-				return TRUE;
-		}
-		else
-		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
-			== BOX &&
-			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
-		{
-				return TRUE;
-		}
-	}
-
-	return FALSE;
-}
-
-/*
-Catch the situation where a corner gets surrounded by boxes.
-*/
-int is_dead2(const struct Map * m, const struct Position mov,
-	const struct Position new_pos)
-{
-	struct Position next, next2, opposite1, opposite2;
-
-	next.x = new_pos.x+mov.x;
-	next.y = new_pos.y+mov.y;
-
-	/* The corner must exist */
-	if (m->Cells[next.y][next.x] != CORNER)
-		return FALSE;
-
-
-	/* The wall corners must exist */
-	opposite1.x = next.x -mov.y;
-	opposite1.y = next.y -mov.x;
-	opposite2.x = next.x + mov.y;
-	opposite2.y = next.y + mov.x;
-
-	if (m->man_moves[opposite1.y][opposite1.x] == BOX)
-	{
-		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL
-		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)
-		   return TRUE;
-	}
-
-	if (m->man_moves[opposite2.y][opposite2.x] == BOX)
-	{
-		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL
-		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)
-		   return TRUE;
-	}
-	return FALSE;
-}
-
-int is_box_movable(const struct Map * m, const struct Position mov,
-	const struct Position box_pos)
-{
-	struct Position next_pos2;
-
-	next_pos2.x = box_pos.x + mov.x;
-	next_pos2.y = box_pos.y + mov.y;
-
-	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&
-		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||
-		m->man_moves[next_pos2.y][next_pos2.x] == BOX)
-	{
-		return FALSE;
-	}
-	else if (is_dead1(m, mov, next_pos2) == TRUE)
-	{
-		return FALSE;
-	}
-	else if (is_dead2(m, mov, next_pos2) == TRUE)
-	{
-		return FALSE;
-	}
-	return TRUE;
-}
-
-/* It modifies m->man_moves */
-int get_box_movements(struct Map * m,
-	struct BoxMove movements[])
-{
-	struct Position pos[MAX_MOVES];
-	struct Position new_pos[MAX_MOVES];
-	int NumMoves, NewMoves;
-	int j, i;
-	struct Position next_pos;
-	char *next_cell;
-	int num_box_movements = 0;
-	
-	/* Let's  the map with only walls in man_moves - other, blanks */
-	for (j = 0; j<m->SizeY; j++)
-		for (i=0; i<m->SizeX; i++)
-		{
-			if (m->Cells[j][i] == WALL)
-				m->man_moves[j][i] = WALL;
-			else
-				m->man_moves[j][i] = BLANK;
-		}
-
-	/* Let's put the boxes */
-	for (i = 0; i<m->NumBoxes; i++)
-	{
-		m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;
-		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
-	}
-
-	NewMoves = 1;
-	new_pos[0].x = m->Man.x;
-	new_pos[0].y = m->Man.y;
-	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;
-	while (NewMoves > 0)
-	{
-		/* The before named "New Moves" become the moves we have
-		   to analyze */
-		NumMoves = NewMoves;
-		for (i=0; i<NewMoves; i++)
-		{
-			pos[i] = new_pos[i];
-		}
-
-		/* Search new positions for each position */
-		NewMoves = 0;
-		for (i=0; i<NumMoves; i++)
-		{
-			/* For each direction */
-			for (j=0; j<4; j++)
-			{
-				next_pos.x = pos[i].x + move_vectors[j].x;
-				next_pos.y = pos[i].y + move_vectors[j].y;
-				next_cell = &m->man_moves[next_pos.y][next_pos.x];
-				if(*next_cell == BLANK)
-				{
-					new_pos[NewMoves] = next_pos;
-					*next_cell = MANCANMOVE;
-					NewMoves++;
-				}
-				else if (*next_cell == BOX)
-				{
-						
-					/* Check if the box is movable */
-
-					if (is_box_movable(m, move_vectors[j],
-						next_pos ))
-					{
-						{
-					movements[num_box_movements].box =
-					m->cells_boxes[next_pos.y][next_pos.x];
-					movements[num_box_movements].dir =
-					move_vectors[j];
-					num_box_movements++;
-						}
-					}
-					
-				}
-
-			}
-		}
-	}
-
-	return num_box_movements;
-}
-
-void force_move_box(struct Map *m, struct BoxMove move)
-{
-	struct Position newpos;
-
-
-	/* Add coords */
-	newpos.x = m->Box[move.box].x + move.dir.x;
-	newpos.y = m->Box[move.box].y + move.dir.y;
-
-	/* Be certain the move can be done */
-	assert(m->Cells[newpos.y][newpos.x] != BOX);
-	assert(m->Cells[newpos.y][newpos.x] != WALL);
-
-	/* Control if we moved the box to a platform */
-	if(m->Cells[newpos.y][newpos.x] == PLATFORM)
-	{
-		m->NumBoxesInPlatform++;
-	}
-
-	/* Control if we moved the box from a platform */
-	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
-	{
-		m->NumBoxesInPlatform--;
-	}
-	m->Man = m->Box[move.box];
-
-	m->Box[move.box] = newpos;
-}
-
-int are_boxes_equal(const struct Position b1[], const struct Position b2[],
-	int n)
-{
-	int i;
-	char tmp[MAX_Y][MAX_X]; /* !!!argh */
-
-	memset(tmp, 0, sizeof(tmp));
-
-	for (i=0; i < n; i++)
-	{
-		tmp[b1[i].y][b1[i].x] = 1;
-	}
-	for (i=0; i < n; i++)
-	{
-		if (tmp[b2[i].y][b2[i].x] != 1)
-			return FALSE;
-	}
-	return TRUE;
-}
-
-int is_new_map(struct Map maps[], int depth)
-{
-	struct Map *m;
-	int i;
-
-	m = &maps[depth];
-
-	for(i=0; i<max_depth; i++)
-	{
-		/* No l'hem de comparar amb ell mateix */
-		if (i == depth)
-			continue;
-
-		if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)
-			continue;
-		else
-		{
-			if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))
-				continue;
-		}
-		return FALSE;
-	}
-	return TRUE;
-}
-
-void PrintMove(struct BoxMove b)
-{
-	printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
-}
-
-void show_percent_callback(int parameter)
-{
-	fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show,
-		min_depth_period, max_depth_period);
-	ShowMap(actual_map);
-	fflush(stderr);
-	min_depth_period = MAX_STEPS;
-	max_depth_period = 0;
-#ifndef DEBUG
-	alarm(ALARM_SECONDS);
-#endif
-}
-
-int search_depth(struct Map maps[], int depth,
-	struct BoxMove movements[],
-	int num_movements, float percent, float total_percent)
-{
-	struct BoxMove new_movements[MAX_MOVES];
-	int num_new_movements;
-	struct Map *m; 
-	int i;
-	float next_percent;
-
-	next_percent = percent / num_movements;
-
-	m = &maps[depth+1];
-	if (depth > max_depth)
-		max_depth = depth;
-	if (depth > max_depth_period)
-		max_depth_period = depth;
-	if (depth < min_depth_period)
-		min_depth_period = depth;
-
-	for (i=0; i < num_movements; i++)
-	{
-		CopyMap(m, &maps[depth]);
-		force_move_box(m, movements[i]);
-		if (m->NumPlatforms == m->NumBoxesInPlatform)
-		{
-			printf("\nSolved!\n");
-			PrintMove(movements[i]);
-			return 0;
-		}
-
-		if (is_new_map(maps, depth+1))
-		{
-			num_new_movements = get_box_movements(m, new_movements);
-			assert(num_new_movements < MAX_MOVES);
-		}
-		else
-			num_new_movements = 0;
-
-		if (num_new_movements == 0)
-		{
-			percent_to_show = total_percent + next_percent*i;
-			depth_to_show = depth;
-			actual_map = &maps[depth];
-#ifdef DEBUG		/* to be out */
-			show_percent_callback(0);
-#endif
-	
-		}
-		else
-		{
-			if (depth+1 < MAX_STEPS)
-			{
-				if(search_depth(maps, depth+1, new_movements,
-					num_new_movements, next_percent,
-					total_percent + next_percent*i) == 0)
-				{
-					PrintMove(movements[i]);
-					return 0;
-				}
-			}
-		}
-	}
-	return 1;
-}
-
-
-
-
-void program_alarm()
-{
-        struct sigaction my_action;
-        int result;
-
-        my_action.sa_handler = show_percent_callback;
-        my_action.sa_flags = 0;
-        memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask));
-
-        result = sigaction(SIGALRM, &my_action, NULL);
-        assert(result == 0);
-
-	alarm(1);
-}
-
-int main(int argn, char **argv)
-{
-	struct Map Morigin;
-	struct Map maps[MAX_STEPS+1];
-	struct BoxMove new_movements[MAX_MOVES];
-	int num_new_movements;
-
-
-	if (argn != 2)
-	{
-		printf("Usage: %s <mapfile>\n", argv[0]);
-		exit(3);
-	}
-	ReadMap(&Morigin, argv[1]);
-
-	// Reget the original map
-	CopyMap(&maps[0], &Morigin);
-
-	assert(maps[0].NumPlatforms > maps[0].NumBoxesInPlatform);
-
-	num_new_movements = get_box_movements(&maps[0], new_movements);
-	assert(num_new_movements < MAX_MOVES);
-	assert(num_new_movements > 0);
-
-#ifndef DEBUG
-	program_alarm();
-#endif
-	search_depth(maps, 0, new_movements,
-		num_new_movements, 100. / num_new_movements,
-		0);
-
-	return 0;
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosol.c
--- a/sokosol.c	Fri May 05 23:18:24 2006 +0200
+++ b/sokosol.c	Fri May 05 23:20:33 2006 +0200
@@ -1,42 +1,121 @@
 #include <stdio.h>
 #include <string.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <signal.h>
 
-#define BOX '*'
+#define BOX '$'
 #define WALL '#'
-#define MAN '8'
-#define PLATFORM '+'
-#define BOXINPLATFORM 'O'
+#define MAN '@'
+#define PLATFORM '.'
+#define BOXINPLATFORM '*'
 #define MANINPLATFORM 'E'
 #define BLANK ' '
+#define CORNER '-'
+#define MANCANMOVE '+'
 
-#define DIR_LEFT 'A'
-#define DIR_RIGHT 'B'
-#define DIR_UP 'C'
-#define DIR_DOWN 'D'
+#define NBOX(n) ((n)<<2)
+
+//#define DEBUG
+
+enum
+{
+	ALARM_SECONDS=1
+};
+
 
-#define MAX_X 500
-#define MAX_Y 500
-#define MAX_MOVES 100
+enum logic
+{
+	TRUE=1,
+	FALSE=0,
+};
+
+#define MAX_X 50
+#define MAX_Y 50
+#define MAX_MOVES 50
+#define MAX_STEPS 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.
+ * 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 Position
+{
+	int x;
+	int y;
+};
 
 struct Map
 {
-	char Cells[MAX_X][MAX_Y];
+	char Cells[MAX_Y][MAX_X];
+	char cells_boxes[MAX_Y][MAX_X];
+	char man_moves[MAX_Y][MAX_X];
 	int SizeX, SizeY;
-	int ManX, ManY;
+	struct Position Man;
 	int NumPlatforms;
 	int NumBoxesInPlatform;
+	struct Position Box[MAX_BOXES];
+	int NumBoxes;
 };
 
 
 
+enum e_direction
+{
+	DIR_LEFT,
+	DIR_RIGHT,
+	DIR_DOWN,
+	DIR_UP
+};
+const struct Position move_vectors[4] = {
+	{0, 1},
+	{0, -1},
+	{1, 0},
+	{-1, 0}};
+
+struct BoxMove
+{
+	int box;
+	struct Position dir;
+};
+
+float percent_to_show = 0;
+int depth_to_show = 0;
+
+int max_depth = 0;
+int min_depth_period = 0;
+int max_depth_period = 0;
+struct Map * actual_map;
+
+
+
+
+void CopyMap (struct Map *Mdest, const struct Map *Morig)
+{
+	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
+}
+
+
 void ReadMap(struct Map *M, char *FileName)
 {
 	FILE *Fitxer;
@@ -52,330 +131,726 @@
 	M->SizeY=0;
 	while (!feof(Fitxer))
 	{
-		fgets(M->Cells[M->SizeY++], MAX_X, 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; }
-			else if (M->Cells[j][i] == PLATFORM)
+			{ 
+				M->Man.x = i; M->Man.y = j; 
+				M->Cells[M->Man.y][M->Man.x] = 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->Box[M->NumBoxes].x = i;
+				M->Box[M->NumBoxes].y = j;
+				M->NumBoxes++;
+			} else if (M->Cells[j][i] == BOX)
+			{
+				M->Cells[j][i] = BLANK;
+
+				M->Box[M->NumBoxes].x = i;
+				M->Box[M->NumBoxes].y = j;
+				M->NumBoxes++;
+			} else if (M->Cells[j][i] == CORNER)
+			{
+				M->Cells[j][i] = CORNER;
+			} 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] = CORNER;
 			}
+				
 		}
+
 }
 
 
-void ShowMap (struct Map *M)
+void ShowMap (const struct Map *M)
 {
+	struct Map Temp;
 	int i,j;
-	for (j = 0; j<M->SizeY; j++)
+
+	CopyMap(&Temp, M);
+
+	Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN;
+
+	for (i = 0; i < Temp.NumBoxes; i++)
 	{
-		for (i=0; i<M->SizeX; i++)
-			printf("%c", M->Cells[j][i]);
+		if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM)
+			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM;
+		else
+			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX;
+	}
+
+	for (j = 0; j<Temp.SizeY; j++)
+	{
+		for (i=0; i<Temp.SizeX; i++)
+			fprintf(stderr,"%c", Temp.Cells[j][i]);
+		fprintf(stderr,"\n");
+	}
+
+#if 0
+	// 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", M->ManX, M->ManY);
-	printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms,
-			M->NumBoxesInPlatform);
+#endif
+
+	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
+	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
+			Temp.NumBoxesInPlatform);
+
 }
 
 
 
-void CopyMap (struct Map *Mdest, struct Map *Morig)
+int InverseMove(char Dir1, char Dir2)
+{
+	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
+		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
+		return 1;
+	return 0;
+}
+
+
+void PrintCombination(int Moves[], int NumMoves)
 {
-	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
+	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 MoveMan (struct Map *M, int Direction)
+#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
+ Situation:
+    
+  ->@$ #
+      $
+*/
+int box_will_be_blocked(const struct Map * m, const struct Position mov,
+	const struct Position box_pos)
 {
-	int NewX, NewY;
+	struct Position next_pos2, tmp, tmp2[2];
+	int i;
+
+	next_pos2.x = box_pos.x + mov.x;
+	next_pos2.y = box_pos.y + mov.y;
 
-/*
-	// Check if man is where it should be
-	if (M->Cells[M->ManY][M->ManX] != MAN &&
-		M->Cells[M->ManY][M->ManX] != MANINPLATFORM)
+	tmp.x = next_pos2.x + mov.x;
+	tmp.y = next_pos2.y + mov.y;
+	tmp2[0].x = next_pos2.x + mov.y;
+	tmp2[0].y = next_pos2.y + mov.x;
+	tmp2[1].x = next_pos2.x - mov.y;
+	tmp2[1].y = next_pos2.y - mov.x;
+	for (i=0; i < 2; i++)
 	{
-		printf("Man isn't where it should be!\n");
-		exit(2);
+		if (m->man_moves[tmp.y][tmp.x] == WALL &&
+			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
+		{
+			return TRUE;
+		}
+		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
+			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)
+		{
+			return TRUE;
+		}
+		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
+			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
+		{
+			return TRUE;
+		}
 	}
-*/
+
+	return FALSE;
+}
 
-	// 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 if (Direction == DIR_DOWN)		// if not needed
-	{ NewX = M->ManX; NewY = M->ManY + 1; }
-
+int is_corner_area(const struct Map * m, const struct Position p,
+	const struct Position box, const struct Position new_box)
+{
+	int NumMoves, NewMoves;
+	struct Position pos[MAX_MOVES];
+	struct Position new_pos[MAX_MOVES];
+	char corners[MAX_Y][MAX_X];
+	int i,j;
+	struct Position next_pos;
+	char *next_cell;
 
 
-	// What's in front of the man?
+	/* Blank the garden */
+	for (j = 0; j<m->SizeY; j++)
+		for (i=0; i<m->SizeX; i++)
+			corners[j][i] = m->Cells[j][i];
+
+	/* Let's put the boxes */
+	for (i = 0; i<m->NumBoxes; i++)
+		corners[m->Box[i].y][m->Box[i].x] = BOX;
 
-	if (M->Cells[NewY][NewX] == WALL)
+	/* Let's put our box - it can be simply added */
+	corners[new_box.y][new_box.x] = BOX;
+	/* Let's remove the original box. */
+	corners[box.y][box.x] = BLANK;
+
+	NewMoves = 1;
+	new_pos[0] = p;
+	while (NewMoves > 0)
 	{
-		return 0;	// ILLEGAL MOVE
-	}
-	else if (M->Cells[NewY][NewX] == BOX)
-	{
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-			BLANK)
+		/* The before named "New Moves" become the moves we have
+		   to analyze */
+		NumMoves = NewMoves;
+		for (i=0; i<NewMoves; i++)
+		{
+			pos[i] = new_pos[i];
+		}
+
+		/* Search new positions for each position */
+		NewMoves = 0;
+		for (i=0; i<NumMoves; i++)
 		{
-			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;
+			/* For each direction */
+			for (j=0; j<4; j++)
+			{
+				next_pos.x = pos[i].x + move_vectors[j].x;
+				next_pos.y = pos[i].y + move_vectors[j].y;
+				next_cell = &corners[next_pos.y][next_pos.x];
+				if(*next_cell == BLANK ||
+					*next_cell == PLATFORM)
+				{
+					return FALSE;
+				}
+				else if(*next_cell == CORNER)
+				{
+					new_pos[NewMoves] = next_pos;
+					*next_cell = MANCANMOVE;
+					NewMoves++;
+				}
 			}
-			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 TRUE;
+}
+
+int does_box_close_corners(const struct Map * m, const struct Position mov,
+	const struct Position box_pos)
+{
+	struct Position p, p2;
+
+	p.x = box_pos.x + mov.x;
+	p.y = box_pos.y + mov.y;
+	
+	/* Let's plan the checks */
+	/* The point will be marked with a MANCANMOVE */
+	p2.x = p.x + mov.x;
+	p2.y = p.y + mov.y;
+	if (m->Cells[p2.y][p2.x] == CORNER)
+	{
+		if (is_corner_area(m, p2, box_pos, p))
+			return TRUE;
+	}
+
+	p2.x = p.x + mov.y;
+	p2.y = p.y + mov.x;
+	if (m->Cells[p2.y][p2.x] == CORNER)
+	{
+		if (is_corner_area(m, p2, box_pos, p))
+			return TRUE;
+	}
+
+	p2.x = p.x - mov.y;
+	p2.y = p.y - mov.x;
+	if (m->Cells[p2.y][p2.x] == CORNER)
+	{
+		if (is_corner_area(m, p2, box_pos, p))
+			return TRUE;
+	}
+	return FALSE;
+}
+#endif
+
+/*
+Catch the situation where a box is moved next to a corner, where the box
+next to it will not be able to be moved.
+*/
+int is_dead1(const struct Map * m, const struct Position mov,
+	const struct Position new_pos)
+{
+	struct Position opposite1, opposite2;
+
+	/* The wall corners must exist */
+	opposite1.x = -mov.y;
+	opposite1.y = -mov.x;
+	opposite2.x = mov.y;
+	opposite2.y = mov.x;
+
+#ifdef DEBUG
+	ShowMap(m);
+#endif
+
+	/* Test the first corner */
+	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
+		== WALL)
+	{
+		/* Test wall at opposites 1*/
+		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
+			== WALL &&
+			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
+		{
+				return TRUE;
+		}
+		else
+		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
+			== BOX &&
+			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
+		{
+				return TRUE;
+		}
+		/* Test wall at opposites 2 */
+		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
+			== WALL &&
+			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
+		{
+				return TRUE;
+		}
+		else
+		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
+			== BOX &&
+			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
+		{
+				return TRUE;
+		}
+	}
+
+	/* Test the second corner */
+	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
+		== WALL)
+	{
+		/* Test wall at opposites 1*/
+		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
+			== WALL &&
+			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
+		{
+				return TRUE;
+		}
+		else
+		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
+			== BOX &&
+			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
+		{
+				return TRUE;
+		}
+		/* Test wall at opposites 2 */
+		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
+			== WALL &&
+			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
+		{
+				return TRUE;
 		}
 		else
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-				PLATFORM)
+		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
+			== BOX &&
+			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
 		{
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOXINPLATFORM;
+				return TRUE;
+		}
+	}
+
+	return FALSE;
+}
+
+/*
+Catch the situation where a corner gets surrounded by boxes.
+*/
+int is_dead2(const struct Map * m, const struct Position mov,
+	const struct Position new_pos)
+{
+	struct Position next, next2, opposite1, opposite2;
+
+	next.x = new_pos.x+mov.x;
+	next.y = new_pos.y+mov.y;
+
+	/* The corner must exist */
+	if (m->Cells[next.y][next.x] != CORNER)
+		return FALSE;
+
+
+	/* The wall corners must exist */
+	opposite1.x = next.x -mov.y;
+	opposite1.y = next.y -mov.x;
+	opposite2.x = next.x + mov.y;
+	opposite2.y = next.y + mov.x;
+
+	if (m->man_moves[opposite1.y][opposite1.x] == BOX)
+	{
+		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL
+		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)
+		   return TRUE;
+	}
+
+	if (m->man_moves[opposite2.y][opposite2.x] == BOX)
+	{
+		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL
+		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)
+		   return TRUE;
+	}
+	return FALSE;
+}
+
+int is_box_movable(const struct Map * m, const struct Position mov,
+	const struct Position box_pos)
+{
+	struct Position next_pos2;
+
+	next_pos2.x = box_pos.x + mov.x;
+	next_pos2.y = box_pos.y + mov.y;
+
+	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&
+		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||
+		m->man_moves[next_pos2.y][next_pos2.x] == BOX)
+	{
+		return FALSE;
+	}
+	else if (is_dead1(m, mov, next_pos2) == TRUE)
+	{
+		return FALSE;
+	}
+	else if (is_dead2(m, mov, next_pos2) == TRUE)
+	{
+		return FALSE;
+	}
+	return TRUE;
+}
+
+/* It modifies m->man_moves */
+int get_box_movements(struct Map * m,
+	struct BoxMove movements[])
+{
+	struct Position pos[MAX_MOVES];
+	struct Position new_pos[MAX_MOVES];
+	int NumMoves, NewMoves;
+	int j, i;
+	struct Position next_pos;
+	char *next_cell;
+	int num_box_movements = 0;
+	
+	/* Let's  the map with only walls in man_moves - other, blanks */
+	for (j = 0; j<m->SizeY; j++)
+		for (i=0; i<m->SizeX; i++)
+		{
+			if (m->Cells[j][i] == WALL)
+				m->man_moves[j][i] = WALL;
+			else
+				m->man_moves[j][i] = BLANK;
+		}
+
+	/* Let's put the boxes */
+	for (i = 0; i<m->NumBoxes; i++)
+	{
+		m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;
+		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
+	}
+
+	NewMoves = 1;
+	new_pos[0].x = m->Man.x;
+	new_pos[0].y = m->Man.y;
+	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;
+	while (NewMoves > 0)
+	{
+		/* The before named "New Moves" become the moves we have
+		   to analyze */
+		NumMoves = NewMoves;
+		for (i=0; i<NewMoves; i++)
+		{
+			pos[i] = new_pos[i];
+		}
+
+		/* Search new positions for each position */
+		NewMoves = 0;
+		for (i=0; i<NumMoves; i++)
+		{
+			/* For each direction */
+			for (j=0; j<4; j++)
+			{
+				next_pos.x = pos[i].x + move_vectors[j].x;
+				next_pos.y = pos[i].y + move_vectors[j].y;
+				next_cell = &m->man_moves[next_pos.y][next_pos.x];
+				if(*next_cell == BLANK)
+				{
+					new_pos[NewMoves] = next_pos;
+					*next_cell = MANCANMOVE;
+					NewMoves++;
+				}
+				else if (*next_cell == BOX)
+				{
+						
+					/* Check if the box is movable */
 
-			if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
-			{	// Man is over Platform
-				M->Cells[M->ManY][M->ManX] = PLATFORM;
-				M->Cells[NewY][NewX] = MAN;
+					if (is_box_movable(m, move_vectors[j],
+						next_pos ))
+					{
+						{
+					movements[num_box_movements].box =
+					m->cells_boxes[next_pos.y][next_pos.x];
+					movements[num_box_movements].dir =
+					move_vectors[j];
+					num_box_movements++;
+						}
+					}
+					
+				}
+
 			}
-			else	// Man is over Blank
-			{
-				M->Cells[M->ManY][M->ManX] = BLANK;
-				M->Cells[NewY][NewX] = MAN;
-			}
-			M->ManX = NewX; M->ManY = NewY;
+		}
+	}
+
+	return num_box_movements;
+}
+
+void force_move_box(struct Map *m, struct BoxMove move)
+{
+	struct Position newpos;
+
+
+	/* Add coords */
+	newpos.x = m->Box[move.box].x + move.dir.x;
+	newpos.y = m->Box[move.box].y + move.dir.y;
+
+	/* Be certain the move can be done */
+	assert(m->Cells[newpos.y][newpos.x] != BOX);
+	assert(m->Cells[newpos.y][newpos.x] != WALL);
+
+	/* Control if we moved the box to a platform */
+	if(m->Cells[newpos.y][newpos.x] == PLATFORM)
+	{
+		m->NumBoxesInPlatform++;
+	}
+
+	/* Control if we moved the box from a platform */
+	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
+	{
+		m->NumBoxesInPlatform--;
+	}
+	m->Man = m->Box[move.box];
+
+	m->Box[move.box] = newpos;
+}
+
+int are_boxes_equal(const struct Position b1[], const struct Position b2[],
+	int n)
+{
+	int i;
+	char tmp[MAX_Y][MAX_X]; /* !!!argh */
+
+	memset(tmp, 0, sizeof(tmp));
+
+	for (i=0; i < n; i++)
+	{
+		tmp[b1[i].y][b1[i].x] = 1;
+	}
+	for (i=0; i < n; i++)
+	{
+		if (tmp[b2[i].y][b2[i].x] != 1)
+			return FALSE;
+	}
+	return TRUE;
+}
+
+int is_new_map(struct Map maps[], int depth)
+{
+	struct Map *m;
+	int i;
+
+	m = &maps[depth];
+
+	for(i=0; i<max_depth; i++)
+	{
+		/* No l'hem de comparar amb ell mateix */
+		if (i == depth)
+			continue;
 
-			M->NumBoxesInPlatform++;
-			return 1;
+		if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)
+			continue;
+		else
+		{
+			if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))
+				continue;
+		}
+		return FALSE;
+	}
+	return TRUE;
+}
+
+void PrintMove(struct BoxMove b)
+{
+	printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
+}
+
+void show_percent_callback(int parameter)
+{
+	fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show,
+		min_depth_period, max_depth_period);
+	ShowMap(actual_map);
+	fflush(stderr);
+	min_depth_period = MAX_STEPS;
+	max_depth_period = 0;
+#ifndef DEBUG
+	alarm(ALARM_SECONDS);
+#endif
+}
+
+int search_depth(struct Map maps[], int depth,
+	struct BoxMove movements[],
+	int num_movements, float percent, float total_percent)
+{
+	struct BoxMove new_movements[MAX_MOVES];
+	int num_new_movements;
+	struct Map *m; 
+	int i;
+	float next_percent;
+
+	next_percent = percent / num_movements;
+
+	m = &maps[depth+1];
+	if (depth > max_depth)
+		max_depth = depth;
+	if (depth > max_depth_period)
+		max_depth_period = depth;
+	if (depth < min_depth_period)
+		min_depth_period = depth;
+
+	for (i=0; i < num_movements; i++)
+	{
+		CopyMap(m, &maps[depth]);
+		force_move_box(m, movements[i]);
+		if (m->NumPlatforms == m->NumBoxesInPlatform)
+		{
+			printf("\nSolved!\n");
+			PrintMove(movements[i]);
+			return 0;
+		}
+
+		if (is_new_map(maps, depth+1))
+		{
+			num_new_movements = get_box_movements(m, new_movements);
+			assert(num_new_movements < MAX_MOVES);
+		}
+		else
+			num_new_movements = 0;
+
+		if (num_new_movements == 0)
+		{
+			percent_to_show = total_percent + next_percent*i;
+			depth_to_show = depth;
+			actual_map = &maps[depth];
+#ifdef DEBUG		/* to be out */
+			show_percent_callback(0);
+#endif
+	
 		}
 		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
+			if (depth+1 < MAX_STEPS)
 			{
-				M->Cells[M->ManY][M->ManX] = BLANK;
-				M->Cells[NewY][NewX] = MANINPLATFORM;
+				if(search_depth(maps, depth+1, new_movements,
+					num_new_movements, next_percent,
+					total_percent + next_percent*i) == 0)
+				{
+					PrintMove(movements[i]);
+					return 0;
+				}
 			}
-			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;
 }
 
+
+
+
+void program_alarm()
+{
+        struct sigaction my_action;
+        int result;
+
+        my_action.sa_handler = show_percent_callback;
+        my_action.sa_flags = 0;
+        memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask));
+
+        result = sigaction(SIGALRM, &my_action, NULL);
+        assert(result == 0);
+
+	alarm(1);
+}
+
 int main(int argn, char **argv)
 {
-	struct Map Morigin, M[MAX_MOVES];
-	char Moves[MAX_MOVES];
-	int NumMoves;
-	int OldMaps;
-	int IllegalMove;
-	int Carry;
+	struct Map Morigin;
+	struct Map maps[MAX_STEPS+1];
+	struct BoxMove new_movements[MAX_MOVES];
+	int num_new_movements;
 
-	int i, j;
 
 	if (argn != 2)
 	{
-		printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]);
+		printf("Usage: %s <mapfile>\n", argv[0]);
 		exit(3);
 	}
-
 	ReadMap(&Morigin, argv[1]);
-	sscanf(argv[2], "%i", &NumMoves);
-
-	ShowMap(&Morigin);
-
-	CopyMap(&M, &Morigin);
-
-	IllegalMove = NumMoves - 1;
-
-	for (i = 0; i < NumMoves; i++)
-		Moves[i] = DIR_LEFT;
 
 	// Reget the original map
-	CopyMap(&M[0], &Morigin);
+	CopyMap(&maps[0], &Morigin);
 
-	OldMaps = 0;
+	assert(maps[0].NumPlatforms > maps[0].NumBoxesInPlatform);
 
-	IllegalMove = NumMoves - 1;
-	// Process the combination
-	for (i = 0; i < NumMoves; i++)
-	{
-		CopyMap(&M[i+1], &M[i]);
-		// Could we use OldMaps for indexing, as faster than i+1?
-		if (!MoveMan(&M[i+1], Moves[i]))
-		{
-			IllegalMove = i;
-			break;
-		}
-	}
+	num_new_movements = get_box_movements(&maps[0], new_movements);
+	assert(num_new_movements < MAX_MOVES);
+	assert(num_new_movements > 0);
 
-	// Process the combinations.
-	// Order: Left, Right, Up, Down
-	while (M.NumPlatforms != M.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]++;
-				if (Moves[i] == DIR_DOWN + 1)
-				{ Moves[i] = DIR_LEFT; Carry = 1; }
-			}
-			OldMaps = i;	// Sure?
-			// 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;
-				printf("Provant %i moviments...\n", NumMoves);
-			}
-		}
-
-/*
-		// Print the combination
+#ifndef DEBUG
+	program_alarm();
+#endif
+	search_depth(maps, 0, new_movements,
+		num_new_movements, 100. / num_new_movements,
+		0);
 
-		for (i=0; i < NumMoves; i++)
-		{
-			printf("%c", Moves[i]);
-		}
-		printf("\n");
-*/
-
-		IllegalMove = NumMoves - 1;
-		// Process the combination
-		for (i = 0; i < NumMoves; i++)
-		{
-			if (i>=OldMaps)
-			{
-				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;
 
 }
diff -r 415159228618 -r 29cc57a9678e sokosol2.c
--- a/sokosol2.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,311 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-
-#define BOX '*'
-#define WALL '#'
-#define MAN '8'
-#define PLATFORM '+'
-#define BOXINPLATFORM 'O'
-#define MANINPLATFORM 'E'
-#define BLANK ' '
-
-#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 100
-
-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 if (Direction == DIR_DOWN)		// if not needed
-	{ 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;
-		}
-		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++;
-		}
-		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--;
-		}
-		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;
-		}
-		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;
-	}
-	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;
-}
-
-int main()
-{
-	struct Map Morigin, M;
-	char Moves[MAX_MOVES];
-	int NumMoves;
-	int IllegalMove;
-	int Carry;
-	int Arrel;
-
-	int i, j;
-
-	ReadMap(&Morigin, "model");
-
-	ShowMap(&Morigin);
-
-	CopyMap(&M, &Morigin);
-
-	printf("Numero de moviments a provar: ");
-	scanf("%i", &NumMoves);
-	printf("Arrel: ");
-	scanf("%i", &Arrel);
-	srand(Arrel);
-
-	// Process the combinations.
-	// Order: Left, Right, Up, Down
-	while (M.NumPlatforms != M.NumBoxesInPlatform)
-	{
-		// Reget the original map
-		CopyMap(&M, &Morigin);
-
-/*
-		// Print the combination
-
-		for (i=0; i < NumMoves; i++)
-		{
-			printf("%c", Moves[i]);
-		}
-		printf("\n");
-*/
-
-		// Process the combination
-		for (i = 0; i < NumMoves; i++)
-		{
-			if (!MoveMan(&M, Moves[i]=rand()%4))
-				break;
-		}
-					
-	}
-
-	// Print the combination
-	for (i=0; i < NumMoves; i++)
-	{
-		printf("%c", Moves[i]+48);
-	}
-	printf("\n");
-
-/*
-	// Print The Steps
-	strcpy(Moves, "DDDRUU");
-
-	for (i=0; i < 6; i++)
-	{
-		printf("%i", MoveMan(&M, Moves[i]));
-		ShowMap(&M);
-	}
-*/
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosol3.c
--- a/sokosol3.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,375 +0,0 @@
-#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;
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosol4.c
--- a/sokosol4.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,366 +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 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
-
-#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.
- */
-
-
-struct Map
-{
-	char Cells[MAX_X][MAX_Y];
-	int SizeX, SizeY;
-	int ManX, ManY;
-	int NumPlatforms;
-	int NumBoxesInPlatform;
-	char BoxMoved;		// Boolean
-};
-
-
-
-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; }
-			if (M->Cells[j][i] == PLATFORM)
-				M->NumPlatforms++;
-			else if (M->Cells[j][i] == BOXINPLATFORM)
-			{
-				M->NumPlatforms++;
-				M->NumBoxesInPlatform++;
-			} 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;
-		}
-
-	M->Cells[M->ManY][M->ManX] = BLANK;
-	M->BoxMoved = 0;	// Needed?
-}
-
-
-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 MOVE_ILLEGAL;	// ILLEGAL MOVE
-	}
-	else if (M->Cells[NewY][NewX] == BOX)
-	{
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-			BLANK)
-		{
-			M->Cells[NewY][NewX] = BLANK;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOX;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-				PLATFORM)
-		{
-			M->Cells[NewY][NewX] = BLANK;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOXINPLATFORM;
-
-			M->ManX = NewX; M->ManY = NewY;
-
-			M->NumBoxesInPlatform++;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		{
-			return MOVE_ILLEGAL;	// ILLEGAL MOVE
-		}
-	}else
-	if (M->Cells[NewY][NewX] == BOXINPLATFORM)
-	{
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-			BLANK)
-		{
-			M->Cells[NewY][NewX] = PLATFORM;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOX;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->NumBoxesInPlatform--;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
-				PLATFORM)
-		{
-			M->Cells[NewY][NewX] = PLATFORM;
-			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
-				= BOXINPLATFORM;
-
-			M->ManX = NewX; M->ManY = NewY;
-			M->BoxMoved = 1;
-			return MOVE_BOX;
-		}
-		else
-		{
-			return MOVE_ILLEGAL;	// ILLEGAL MOVE
-		}
-	}
-	else
-	{
-		M->ManX = NewX; M->ManY = NewY;
-		M->BoxMoved = 0;
-		return MOVE_OK;
-	}
-	
-	// Not Reachable
-	return MOVE_ILLEGAL;
-}
-
-int InverseMove(char Dir1, char Dir2)
-{
-	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
-		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
-		return 1;
-	return 0;
-}
-
-int main(int argn, char **argv)
-{
-	struct Map Morigin;
-	struct Map M[MAX_MOVES+1];
-	char Moves[MAX_MOVES];
-	int NumMoves;
-	int OldMaps;
-	int IllegalMove;
-	int Carry;
-	int MoveResult;
-
-	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] = 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 - 1; i++)
-		{
-			CopyMap(&M[i+1], &M[i]);
-			if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
-			{
-				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;
-			}
-				
-		}
-		// Here i = NumMoves - 1
-		CopyMap(&M[i+1], &M[i]);
-		if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
-			IllegalMove = i;
-					
-	}
-
-	// Print the combination
-	for (i=0; i < NumMoves; i++)
-	{
-		if (Moves[i] == DIR_LEFT)
-			printf("L");
-		else if (Moves[i] == DIR_RIGHT)
-			printf("R");
-		else if (Moves[i] == DIR_UP)
-			printf("U");
-		else if (Moves[i] == DIR_DOWN)
-			printf("D");
-	}
-	printf("\n");
-
-/*
-	// Print The Steps
-	for (i=0; i < NumMoves; i++)
-	{
-		ShowMap(&M[i]);
-	}
-*/
-	return 0;
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosol5.c
--- 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;
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosold.c
--- a/sokosold.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,445 +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
- *
- * 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;
-
-}
diff -r 415159228618 -r 29cc57a9678e sokosold2.c
--- a/sokosold2.c	Fri May 05 23:18:24 2006 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,543 +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_MANMOVES 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!)
- *
- * Diria que el programa no es deixa cap branca de l'arbre de backtracking
- */
-
-
-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;
-			}
-				
-		}
-
-	if(M->NumBoxes > M->NumPlatforms)
-	{
-		printf("More boxes than platforms!\n");
-		exit(2);
-	}
-}
-
-
-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("%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_MANMOVES], Y[MAX_MANMOVES];
-	int NewX[MAX_MANMOVES], NewY[MAX_MANMOVES];
-	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;
-	M->ManMoves[M->ManY][M->ManX] = MANCANMOVE;
-	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++;
-			}
-		}
-	}
-}
-
-
-/* Returns bool */
-char IsStupidPos(struct Map *M, int X, int Y)
-{
-	struct Map MTemp;
-	int NumBoxes, NumWalls, NumBoxesInPlatform;
-	int j, i;
-
-	CopyMap(&MTemp, M);
-
-
-	for (i = 0; i<MTemp.NumBoxes; i++)
-		if (MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] == PLATFORM)
-			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] =
-			BOXINPLATFORM;
-		else
-			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] = BOX;
-
-//	ShowMap(&MTemp);
-
-	/* We don't verify if j<=Y or i<=X is outside the map. It shouldn't
-	 * be, as it will be called with X,Y pair beeing the coordinates of a
-	 * Box!
-	 */
-	for (j = Y-1; j<=Y; j++)
-		for (i=X-1; i<=X; i++)
-		{
-			NumBoxes = NumWalls = NumBoxesInPlatform = 0;
-			/* Up-Left Cell */
-			if (MTemp.Cells[j][i] == WALL)
-				NumWalls++;
-			else if (MTemp.Cells[j][i] == BOX)
-				NumBoxes++;
-			else if (MTemp.Cells[j][i] == BOXINPLATFORM)
-				NumBoxesInPlatform++;
-			/* Up-Right Cell */
-			if (MTemp.Cells[j][i+1] == WALL)
-				NumWalls++;
-			else if (MTemp.Cells[j][i+1] == BOX)
-				NumBoxes++;
-			else if (MTemp.Cells[j][i+1] == BOXINPLATFORM)
-				NumBoxesInPlatform++;
-			/* Down-Right Cell */
-			if (MTemp.Cells[j+1][i+1] == WALL)
-				NumWalls++;
-			else if (MTemp.Cells[j+1][i+1] == BOX)
-				NumBoxes++;
-			else if (MTemp.Cells[j+1][i+1] == BOXINPLATFORM)
-				NumBoxesInPlatform++;
-			/* Down-Left Cell */
-			if (MTemp.Cells[j+1][i] == WALL)
-				NumWalls++;
-			else if (MTemp.Cells[j+1][i] == BOX)
-				NumBoxes++;
-			else if (MTemp.Cells[j+1][i] == BOXINPLATFORM)
-				NumBoxesInPlatform++;
-
-			if ((NumBoxesInPlatform + NumBoxes + NumWalls == 4) &&
-				(NumBoxes >= 1)) 
-				return MOVE_ILLEGAL;
-		}
-
-	return MOVE_OK;
-}
-
-
-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) )
-			{
-				if(InPlatform)
-					M->NumBoxesInPlatform--;
-				M->BoxX[NumBox]--;
-				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
-					PLATFORM)
-					M->NumBoxesInPlatform++;
-				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
-			}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->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]+1]
-				!= CANTO) )
-			{
-				if(InPlatform)
-					M->NumBoxesInPlatform--;
-				M->BoxX[NumBox]++;
-				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
-					PLATFORM)
-					M->NumBoxesInPlatform++;
-				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
-			}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->Cells[M->BoxY[NumBox]-1][M->BoxX[NumBox]]
-				!= CANTO) )
-			{
-				if(InPlatform)
-					M->NumBoxesInPlatform--;
-				M->BoxY[NumBox]--;
-				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
-					PLATFORM)
-					M->NumBoxesInPlatform++;
-				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
-			}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->Cells[M->BoxY[NumBox]+1][M->BoxX[NumBox]]
-				!= CANTO) )
-			{
-				if(InPlatform)
-					M->NumBoxesInPlatform--;
-				M->BoxY[NumBox]++;
-				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==
-					PLATFORM)
-					M->NumBoxesInPlatform++;
-				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);
-			}else return 0;
-			break;
-	}
-	/* Check for stupid movement */
-	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);
-
-	//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(&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;
-		}
-	}
-
-	// Main solution finder loop
-	while (!(M[NumMoves].NumPlatforms == M[NumMoves].NumBoxesInPlatform && 
-	IllegalMove == -1))
-	{
-		// Increase the Counter
-		{
-			Carry = 1;
-			// If last combination was legal
-			if (IllegalMove == -1)
-				IllegalMove = NumMoves -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);
-				fflush(stdout);
-			}
-		}
-
-
-		// First assume combination is legal
-		IllegalMove = -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;
-			}*/
-			// For next map:
-			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;
-		//ShowMap(&M[i+1]);
-
-		//printf("IM: %i\n", IllegalMove);
-					
-	}
-
-	// Print the combination
-	PrintCombination(Moves, NumMoves);
-/*
-	// Print The Steps
-	for (i=0; i < NumMoves; i++)
-	{
-		ShowMap(&M[i]);
-	}
-*/
-	return 0;
-
-}