Universität Ulm, Fakultät für Mathematik und Wirtschaftswissenschaften, SAI

Lösung zu Blatt 6 der Systemnahe Software I (WS 97/98)

9 Schach

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

#define MIN(a,b) ((a) < (b) ? (a) : (b))

typedef short int BOOL;

typedef struct {
   short int board[4][5];
} data;

data end;

typedef struct node *nodePtr;
struct node {
   data userStuff;
   nodePtr next;
} nodeList;

typedef struct {
   nodePtr p;
} hashtable;

/* Just read the board as a 20 digit base 3 number */
int data2key(data userStuff, int m) {
   int i, j, res = 0;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 res = (res * 3 + userStuff.board[i][j]) % m;
   return res;
}

/* compare two board configurations */
BOOL isEqual(data x, data y) {
   int i, j;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 if (x.board[i][j] != y.board[i][j]) return FALSE;
   return TRUE;
}

/* Mainly for debugging */
void printData(data x) {
   int i, j;
   for (j = 0; j < 5; j++) {
      for (i = 0; i < 4; i++)
	 printf("%d ", x.board[i][j]);
      printf(" ");
   }
   printf("\n");
}

void buildTable(hashtable **p, int m) {
   int i;
   *p = (hashtable*)calloc(m, sizeof(**p));
   if (*p == NULL) { fprintf(stderr, "Cannot allocate memory\n"); exit(1); }
   for (i = 0; i < m; i++) (*p + i)->p = NULL;
}

/* To free used memory */
void delete_all(hashtable *p, int m) {
   nodePtr np, np2;
   int i;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      while (np != NULL) {
	 np2 = np;
	 np = np->next;
	 free(np2);
      }
   }
   free(p);
}

void printTable(hashtable *p, int m) {
   nodePtr np;
   int i;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      while (np != NULL) {
	 printData(np->userStuff);
	 np = np->next;
      }
      printf("\n");
   }
}

/* insert one element into table p */
void insert(hashtable *p, int m, data x) {
   int pos = data2key(x, m);
   nodePtr temp = (nodePtr)calloc(1, sizeof(nodeList));
   if (temp == NULL) { fprintf(stderr, "Cannot allocate memory\n"); exit(2); }
   temp->next = (p + pos)->p;
   temp->userStuff = x;
   (p + pos)->p = temp;
}

/* check if x is in table p which is of size m */
nodePtr search(hashtable *p, int m, data x) {
   nodePtr np = (p + (data2key(x, m)))->p;
   while (np != NULL) {
      if (isEqual(x, np->userStuff)) return np;
      np = np->next;
   }
   return np;
}

BOOL delete_one(hashtable *p, int m, data x) {
   nodePtr np = (p + (data2key(x, m)))->p;
   if (search(p, m, x) == NULL) return FALSE; /* no such element */
   if (isEqual(x, np->userStuff)) {
      (p + (data2key(x, m)))->p = np->next;
      free(np);
      return TRUE;
   }
   while (np->next != NULL) {
      if (isEqual(x, np->next->userStuff)) {
	 nodePtr temp = np->next;
	 np->next = np->next->next;
	 free(temp);
	 return TRUE;
      }
      np = np->next;
   }
   return FALSE;
}

void utilization(hashtable *p, int m) {
   nodePtr np;
   int max = 0, sum = 0, i, j;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      for (j = 1; np != NULL; np = np->next, j++) {
	 max = (max < j)?j:max;
	 sum++;
      }
   }
   printf("Avg: %5.2f, Max: %d.\n",(double)sum/m,max);
}

rehash(hashtable **p, int m1, int m2) {
   hashtable *newt;
   nodePtr np;
   int i;
   buildTable(&newt, m2);
   for (i = 0; i < m1; i++) {
      np = (*p+i)->p;
      while (np != NULL) {
	 insert(newt, m2, np->userStuff);
	 np = np->next;
      }
   }
   delete_all(*p, m1);
   *p = newt;
}

/* Check if pos is an allowed configuration */
/* In other words: are two different bishops facing each other */
/* logic or == 3   <=>   two bishops are facing each other */
BOOL isPossible(data pos) {
   int i, x, y, or;
   for (i = 0; i < 8; i++) {
      or = 0;
      for (y = MIN(i,4), x = i - MIN(i,4); (y >= 0) && (x < 4); y--, x++)
	 or |= pos.board[x][y]; 
      if (or == 3) return FALSE;
      or = 0;
      for (y = 4 - MIN(i,4), x = i - MIN(i,4); (y < 5) && (x < 4); y++, x++)
	 or |= pos.board[x][y]; 
      if (or == 3) return FALSE;
   }
   /* printf("Is possible: "); printData(pos); */
   return TRUE;
}

/* check if a move from (x0, y0) to (x1, y1) is legal */
/* absolute values of delta x and delta y have to be equal */
BOOL isMove(int x0, int y0, int x1, int y1, data actual) {
   int i, j, di, dj;
   if (actual.board[x0][y0]) return FALSE;
   if (x0 == x1) return FALSE;
   di = (x1 > x0)?1:-1;
   dj = (y1 > y0)?1:-1;
   for (i = x0 + di, j = y0 + dj; i != x1; i += di, j += dj)
      if (actual.board[i][j]) return FALSE;
   return TRUE;
}

BOOL testIt(hashtable **p, int m, data actual) {
   int i, j, x, y;
   if (!isEqual(actual, end)) { /* goal not reached */
      if (search(*p, m, actual)) printf("Bug\n"); /* error in hash table */
      insert(*p, m, actual);    /* insert actual configuration into table */
      for (i = 0; i < 4; i++)
	 for (j = 0; j < 5; j++)
	    if (actual.board[i][j]) { /* a bishop on tested field */
	       for (x = i - MIN(i,j), y = j - MIN(i,j); (x < 4) && (y < 5);
		  x++, y++) {
		  if (isMove(x, y, i, j, actual)) {
		     actual.board[x][y] = actual.board[i][j];
		     actual.board[i][j] = 0;
		     if(!search(*p, m, actual) && isPossible(actual))
			if (testIt(p, m, actual)) {
			   actual.board[i][j] = actual.board[x][y];
			   actual.board[x][y] = 0;
			   printf("Von (%d,%d) nach (%d,%d).\n", x, y, i, j);
			   return TRUE;
			}
		     actual.board[i][j] = actual.board[x][y];
		     actual.board[x][y] = 0;
		  }
	       }
	       for (x = i - MIN(i,4-j), y = j + MIN(i,4-j); (x < 4) && (y >= 0);
		  x++, y--) {
		  if (isMove(x, y, i, j, actual)) {
		     actual.board[x][y] = actual.board[i][j];
		     actual.board[i][j] = 0;
		     if(!search(*p, m, actual) && isPossible(actual))
			if (testIt(p, m, actual)) {
			   actual.board[i][j] = actual.board[x][y];
			   actual.board[x][y] = 0;
			   printf("Von (%d,%d) nach (%d,%d).\n", x, y, i, j);
			   return TRUE;
			}
		     actual.board[i][j] = actual.board[x][y];
		     actual.board[x][y] = 0;
		  }
	       }
	    }
   } else {
      return TRUE;
   }
   return FALSE;
}

void main() {
   hashtable *pt;
   int m = 997, i, j, x, y; /* 101 is good, too */
   data actual;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++) {
	 actual.board[i][j] = end.board[i][j] = 0;
	 if (j == 0)  { actual.board[i][j] = 1; end.board[i][j] = 2; }
	 if (j == 4)  { actual.board[i][j] = 2; end.board[i][j] = 1; }
      }
   buildTable(&pt, m);
   testIt(&pt, m, actual);
   utilization(pt, m);
   delete_all(pt, m);

   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 actual.board[i][j] = end.board[i][j] = 0;
   actual.board[0][0] = end.board[2][0] = 1;
   actual.board[0][4] = end.board[2][4] = 2;
   buildTable(&pt, m);
   testIt(&pt, m, actual);
   delete_all(pt, m);
   for (i = 0; i < 4; i++)
      for (j = 4; j >= 0; j--) {
	 actual.board[i][j] = end.board[i][j] = 0;
	 if ((!j) && (i & 1))  { 
	    actual.board[i][0] = 1; end.board[i][0] = 2;
	    actual.board[i][4] = 2; end.board[i][4] = 1;
	 }
      }
   buildTable(&pt, m);
   testIt(&pt, m, actual);
   delete_all(pt, m);

   exit(0);
}

Universität Fakultät SAI

Ingo Melzer, 09. Dezember 1997