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