A cleaner version, split between different files.
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>
#include "general.h"
#define NBOX(n) ((n)<<2)
/* SOKOBAN Solution Finder
*
* Input File Format: XSB
*
* XSB Format definition:
* Character matrix of:
* @ MAN
* # WALL
* $ BOX
* * BOX over PLATFORM
* + PLATFORM
* - CORNER (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.
*/
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;
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;
}