--- 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;
-
-}