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