--- /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);
+ }
+*/
+
+}