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