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);
}
Ingo Melzer, 09. Dezember 1997