A minimum working (hope so!) version of the algorithm is working, although
authorviric@llimona
Sun, 07 May 2006 01:31:50 +0200
changeset 12 a2c334a71a6b
parent 11 dcfe4d2d4387
child 13 c2b272938a1f
A minimum working (hope so!) version of the algorithm is working, although
it says levels/02 is unsolvable.
Now the solution is printed map by map.
algorithm.c
general.h
os.c
--- a/algorithm.c	Sun May 07 01:30:29 2006 +0200
+++ b/algorithm.c	Sun May 07 01:31:50 2006 +0200
@@ -1,5 +1,6 @@
 #include <assert.h>
 #include <string.h>
+#include <stdio.h> /**********************************PROVA */
 #include "general.h"
 
 /* Variables related to the showing of information by os */
@@ -11,6 +12,15 @@
 extern int max_depth_period;
 extern struct Map * actual_map;
 
+/* Prototipes */
+static Bool are_there_fixed_boxes(struct Map *m,
+	struct BoxMove movements[MAX_MOVES], int *num_movements);
+static void force_move_box(struct Map *m, const struct BoxMove move);
+static Bool search_did_found(struct Map maps[], int depth,
+	struct BoxMove movements[],
+	int num_movements, float percent, float total_percent);
+static void fill_deps(struct Map *m);
+
 #if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
  Situation:
     
@@ -157,162 +167,119 @@
 }
 #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.
-*/
-static int is_dead1(const struct Map * m, const struct Position mov,
-	const struct Position new_pos)
+
+static void force_move_box(struct Map *m, const struct BoxMove move)
 {
-	struct Position opposite1, opposite2;
+	struct Position newpos;
 
-	/* 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);
+	/* 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;
+}
+
+
+
+static Bool search_did_found(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]);
+		/* Let's see if we finished */
+		if (m->NumPlatforms == m->NumBoxesInPlatform)
+		{
+			PrintMove(movements[i]);
+			actual_map = &maps[depth+1];
+			show_percent_and_map();
+			return TRUE;
+		}
+
+		if (is_new_map(maps, depth+1))
+		{
+			actual_map = &maps[depth+1];
+#ifdef DEBUG		/* to be out */
+			show_percent_and_map();
 #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;
+			fill_deps(m);
+			if (are_there_fixed_boxes(m,
+				new_movements, &num_new_movements))
+			{
+				/* That means that the map is illegal */
+				/* Maybe we could update the percent here... */
+				return FALSE;
+			}
+			/* the assert should be IN the function before,
+			   before OVERfilling new_movements */
+			assert(num_new_movements < MAX_MOVES);
 		}
 		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)
+			num_new_movements = 0;
+
+		if (num_new_movements == 0)
 		{
-				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;
+			percent_to_show = total_percent + next_percent*i;
+			depth_to_show = depth;
 		}
 		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;
+			if (depth+1 < MAX_STEPS)
+			{
+				if(search_did_found(maps, depth+1, new_movements,
+					num_new_movements, next_percent,
+					total_percent + next_percent*i) == TRUE)
+				{
+					PrintMove(movements[i]);
+					actual_map = &maps[depth+1];
+					show_percent_and_map();
+					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.
-*/
-static int is_dead2(const struct Map * m, const struct Position mov,
-	const struct Position new_pos)
-{
-	struct Position next, 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;
 }
 
-static 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 */
-static int get_box_movements(struct Map * m,
-	struct BoxMove movements[])
+/* It only fills the m->man_moves structure */
+static void paint_mancanmove(struct Map *m)
 {
 	struct Position pos[MAX_MOVES];
 	struct Position new_pos[MAX_MOVES];
@@ -320,8 +287,7 @@
 	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++)
@@ -335,8 +301,7 @@
 	/* 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;
+		m->man_moves[m->Box[i].y][m->Box[i].x] = WALL;
 	}
 
 	NewMoves = 1;
@@ -369,126 +334,265 @@
 					*next_cell = MANCANMOVE;
 					NewMoves++;
 				}
-				else if (*next_cell == BOX)
+			}
+		}
+	}
+}
+
+/* Returns TRUE if there are fixed boxes that should be moved, FALSE otherwise*/
+/* For 'm' it modifies only m->boxes[][] */
+static Bool are_there_fixed_boxes(struct Map *m,
+	struct BoxMove movements[MAX_MOVES], int *num_movements)
+{
+	int i,j;
+	enum e_direction d;
+
+	/* Box dependencies. The first depends on seconds. */
+	struct
+	{
+		Bool box[MAX_BOXES][MAX_BOXES];
+		int ndeps[MAX_BOXES];
+	} dep;
+
+	/* Free boxes' arrays */
+	struct
+	{
+		Bool box_is_free[MAX_BOXES]; /* This is only used in 'free' */
+		int box[MAX_BOXES];
+		int n;
+	} free,			/* List of all boxes free-to-move */
+		new_free,	/* List of boxes for the next loop (code) */
+		tfree;	/* List of boxes of the loop (code) */
+
+	struct Position tpos;
+
+	Bool is_not_set_free;
+
+	/* Initialize to 0 the dependency structures */
+	memset((void *) &dep, 0, sizeof(dep));
+	for(i=0; i<m->NumBoxes; i++)
+	{
+		new_free.box[i] = FALSE;
+	}
+
+	/* Let's fill the structure */
+	for(i=0; i<m->NumBoxes; i++)
+	{
+		/* See if the box is blocked. That could be
+		   done in fill_deps */
+		if (m->box_deps[i].dep_dir[0] == BLOCKED &&
+			m->box_deps[i].dep_dir[1] == BLOCKED &&
+			m->box_deps[i].dep_dir[2] == BLOCKED &&
+			m->box_deps[i].dep_dir[3] == BLOCKED )
+		{
+			if (m->Cells[m->Box[i].y][m->Box[i].x] !=
+				PLATFORM)
+				return TRUE;
+			/* This is not used actually 
+			else
+				m->boxes[m->Box[i].y][m->Box[i].x] =
+					WALL;
+			*/
+		}
+		/* Let's take note of the dependencies */
+		is_not_set_free = TRUE;
+		for(d=0; d<4; d++)
+		{
+			if(m->box_deps[i].dep_dir[d] > 0)
+			{
+				dep.box[i][m->box_deps[i].dep_dir[d]] =
+					TRUE;
+				dep.ndeps[i]++;
+			} else
+			if(m->box_deps[i].dep_dir[d] == FREE)
+			{
+				if (is_not_set_free)
 				{
-						
-					/* 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++;
-						}
-					}
-					
+					new_free.box[new_free.n++] = i;
+					is_not_set_free = FALSE;
 				}
-
 			}
 		}
 	}
 
-	return num_box_movements;
-}
+	/* Let's analyze if the free boxes can really be moved, and
+	   set them as dependant, if they're dependant.
+	   If some can be really moved, we should know _where to_. */
 
-static void force_move_box(struct Map *m, const 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)
+	/* Paint MANCANMOVE at each cell the man can reach */
+	paint_mancanmove(m);
+	
+	/* For each free movable box, let's see if the man can reach them
+	   fine. If we can, add it to the possible movements. */
+	*num_movements=0;
+	for(i=0; i<new_free.n; i++)
 	{
-		m->NumBoxesInPlatform++;
+		/* For each direction, try if the box can be moved */
+		for(d=0; d<4; d++)
+		{
+			if(m->box_deps[i].dep_dir[d] == FREE)
+			{
+				add_position3(tpos, m->Box[i], move_vectors[OPPOSITE_DIR(d)])
+				if (m->man_moves[tpos.y][tpos.x] == MANCANMOVE)
+				{
+					movements[*num_movements].box = i;
+					movements[*num_movements].dir =
+						move_vectors[d];
+					(*num_movements)++;
+				}
+				/* ELSE - we should catch those cases,
+				where free boxes cannot be moved. Will they
+				ever be movable? 
+				THIS HAS TO BE IMPROVED */
+			}
+		}
 	}
 
-	/* Control if we moved the box from a platform */
-	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
+
+	/* ---------------- The next possible movements have been calculated --
+	We can still find that this map is illegal. We need to find
+	further more if there are boxes unmovable (due to dependencies) */
+
+	/* Let's take out all dependencies from 'free' boxes */
+	/* Prepare the 'free' list */
+	for(i=0; i<m->NumBoxes;i++)
+		free.box_is_free[i] = FALSE;
+	free.n = new_free.n;
+	for(i=0; i<new_free.n; i++)
 	{
-		m->NumBoxesInPlatform--;
+		free.box[i] = new_free.box[i];
+		free.box_is_free[i] = TRUE;
 	}
-	m->Man = m->Box[move.box];
 
-	m->Box[move.box] = newpos;
-}
+	/* KACXO-loop  */
+	while (new_free.n > 0)
+	{
+		/* Copy new_free into free */
+		tfree.n = new_free.n;
+		for(i=0; i<new_free.n; i++)
+			tfree.box[i] = new_free.box[i];
+		new_free.n = 0;
 
-
-
-static 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)
+		for(i=0; i<tfree.n; i++)
 		{
-			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)
+			for(j=0; j<m->NumBoxes; j++)
 			{
-				if(search_depth(maps, depth+1, new_movements,
-					num_new_movements, next_percent,
-					total_percent + next_percent*i) == 0)
+				/* The box j no more depends on
+				   the box tfree[i] */
+				if(dep.box[j][tfree.box[i]])
 				{
-					PrintMove(movements[i]);
-					return 0;
+					dep.box[j][tfree.box[i]] = FALSE;
+					dep.ndeps[j]--;
+					assert(dep.ndeps[j] >= 0);
+					if (dep.ndeps[j] == 0 &&
+						!free.box_is_free[i])
+					{
+						new_free.box[new_free.n++]=j;
+						free.box[free.n++]=j;
+					}
 				}
 			}
 		}
 	}
-	return 1;
+
+	/* Now are left only boxes which depend on others-non-free */
+	for(i=0; i<m->NumBoxes; i++)
+	{
+		for(j=0; j<m->NumBoxes; j++)
+		{
+			/* We only do one-level search !!! */
+			/* If the box only depends on another,
+			   which also only depends on this... */
+			if (dep.box[i][j] && dep.ndeps[i] == 1
+				&& dep.box[j][i] && dep.ndeps[j] == 1)
+			{
+				if (m->Cells[m->Box[i].y][m->Box[i].x]!=
+					PLATFORM)
+				{
+					return TRUE;
+				}
+				/* We don't set any wall here, they're not
+				   important */
+			}
+		}
+	}
+
+	return FALSE;
+}
+
+static void init_cell_boxes(struct Map *m)
+{
+	int i,j;
+
+	/* 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++)
+			m->cells_boxes[j][i] = -1;
+
+	for(i=0; i<m->NumBoxes; i++)
+	{
+		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
+	}
+}
+
+/* It fills only m->box_deps */
+static void fill_deps(struct Map *m)
+{
+	int i;
+	enum e_direction dir;
+	struct Position n; /* Position next to the box */
+
+	/* TO BE OPTIMIZED - get into force_move_box */
+	init_cell_boxes(m);
+
+	for(i=0; i<m->NumBoxes; i++)
+	{
+		/* Initialize the move freedom */
+		for(dir=0;dir<4; dir++)
+		{
+			m->box_deps[i].dep_dir[dir] = FREE;
+		}
+
+		/* Limit the freedom */
+		for(dir=0;dir<4; dir++)
+		{
+			add_position3(n,m->Box[i],move_vectors[dir]);
+			if(m->Cells[n.y][n.x] == WALL)
+			{
+				/* IMPROVEMENT: The fixed-box detection
+				could be done here */
+				m->box_deps[i].dep_dir[dir] = BLOCKED;
+				m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
+					BLOCKED;
+				continue;
+			}
+
+			/* if there is Wall limit, we don't want to set box
+			   dependency */
+			if(m->box_deps[i].dep_dir[dir] == WALL)
+				continue;
+
+			/* Put the box dependency in the list */
+			if(m->cells_boxes[n.y][n.x] >= 0)
+			{
+				m->box_deps[i].dep_dir[dir] =
+					m->cells_boxes[n.y][n.x];
+				/* If the other site is not limited by another
+				   box, we set it up too. */
+
+				/* *** MAYBE IT'S BETTER NOT TO SET IT */
+				if(m->box_deps[i].dep_dir[dir] == FREE)
+				{
+				m->box_deps[i].dep_dir[OPPOSITE_DIR(dir)] =
+					m->cells_boxes[n.y][n.x];
+				}
+				continue;
+			}
+			if(m->Cells[n.y][n.x] == CORNER)
+				m->box_deps[i].dep_dir[dir] = BLOCKED;
+				
+		}
+	}
 }
 
 
@@ -500,14 +604,10 @@
 
 	CopyMap(&maps[0], &origin);
 
-	num_new_movements = get_box_movements(&maps[0], new_movements);
-	assert(num_new_movements < MAX_MOVES);
-	assert(num_new_movements > 0);
+	fill_deps(&maps[0]);
+	assert(!are_there_fixed_boxes(&maps[0], new_movements,
+		&num_new_movements));
+	search_did_found(maps, 0, new_movements, num_new_movements, 100, 0);
 
-	init_os();
-
-	return search_depth(maps, 0, new_movements,
-		num_new_movements, 100. / num_new_movements,
-		0);
-
+	return 0;
 }
--- a/general.h	Sun May 07 01:30:29 2006 +0200
+++ b/general.h	Sun May 07 01:31:50 2006 +0200
@@ -8,7 +8,7 @@
 #define CORNER '-'
 #define MANCANMOVE '+'
 
-/* #define DEBUG */
+/*#define DEBUG */
 
 enum
 {
@@ -21,11 +21,12 @@
 };
 
 
-enum logic
+enum eBool
 {
-	TRUE=1,
+	TRUE=!0,
 	FALSE=0
 };
+typedef enum eBool Bool;
 
 struct Position
 {
@@ -33,34 +34,55 @@
 	int y;
 };
 
+#define add_position2(a, b) {a.x += b.x; a.y += b.y;}
+#define add_position3(dest, a, b) {(dest).x = (a).x + (b).x; \
+				   (dest).y = (a).y + (b).y;}
+
+enum box_freedom
+{
+	FREE=-1,
+	BLOCKED=-2
+};
+
+struct tbox_free
+{
+	/* -1, without dependency in that direction. */
+	/* -2, without dependency in that direction. */
+	enum box_freedom dep_dir[4];
+};
+
 struct Map
 {
-	char Cells[MAX_Y][MAX_X];
-	char cells_boxes[MAX_Y][MAX_X];
-	char man_moves[MAX_Y][MAX_X];
+	char Cells[MAX_Y][MAX_X]; /* Stores WALLs and PLATFORMs */
+	char cells_boxes[MAX_Y][MAX_X]; /* Stores the box number in that cell */
+					/* -1 is NO BOX there */
+	char man_moves[MAX_Y][MAX_X]; /* Stores boxes, walls, MANCANMOVEs */
+/*	int boxes[MAX_Y][MAX_X]; */
 	int SizeX, SizeY;
 	struct Position Man;
-	int NumPlatforms;
-	int NumBoxesInPlatform;
-	struct Position Box[MAX_BOXES];
+	int NumPlatforms;	/* This and the next determine when the game */
+	int NumBoxesInPlatform;	/* finished */
 	int NumBoxes;
+	struct Position Box[MAX_BOXES];	/* The box positions */
+	struct tbox_free box_deps[MAX_BOXES];	/* The dependencies for each
+						box*/
 };
 
 
-
 enum e_direction
 {
-	DIR_LEFT,
+	DIR_DOWN,
 	DIR_RIGHT,
-	DIR_DOWN,
-	DIR_UP
+	DIR_UP,
+	DIR_LEFT
 };
 
 static const struct Position move_vectors[4] = {
 	{0, 1},
+	{1, 0},
 	{0, -1},
-	{1, 0},
 	{-1, 0}};
+#define OPPOSITE_DIR(a) ((a+2)%4)
 
 struct BoxMove
 {
@@ -80,6 +102,7 @@
 void ShowMap (const struct Map *M);
 void init_os();
 void PrintMove(struct BoxMove b);
+void show_percent_and_map();
 
 /* Functions related to map solution
  * algorithm.c */
--- a/os.c	Sun May 07 01:30:29 2006 +0200
+++ b/os.c	Sun May 07 01:31:50 2006 +0200
@@ -123,18 +123,18 @@
 	}
 #endif
 
-	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
-	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
+	fprintf(stderr,"Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
+	fprintf(stderr,"Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
 			Temp.NumBoxesInPlatform);
 
 }
 
 void PrintMove(const struct BoxMove b)
 {
-	printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
+	fprintf(stderr,"Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
 }
 
-static void show_percent_callback(const int parameter)
+void show_percent_and_map()
 {
 	fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show,
 		min_depth_period, max_depth_period);
@@ -142,9 +142,12 @@
 	fflush(stderr);
 	min_depth_period = MAX_STEPS;
 	max_depth_period = 0;
-#ifndef DEBUG
+}
+
+static void show_percent_callback(const int parameter)
+{
+	show_percent_and_map();
 	alarm(ALARM_SECONDS);
-#endif
 }
 
 static void program_alarm()
@@ -164,5 +167,8 @@
 
 void init_os()
 {
+#ifndef DEBUG
 	program_alarm();
+#endif
 }
+