Moving the files to appropiate locations.
--- 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
--- /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;
+*/
+
+}
--- /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);
+ }
+*/
+
+}
--- /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);
+ }
+*/
+
+}
--- /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;
+
+}
--- /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;
+
+}
--- /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;
+
+}
--- /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;
+
+}
--- /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;
+
+}
--- 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;
-*/
-
-}
--- 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;
-
-}
--- 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;
}
--- 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);
- }
-*/
-
-}
--- 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;
-
-}
--- 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;
-
-}
--- 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;
-
-}
--- 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;
-
-}
--- 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;
-
-}