@; This file is a template. It is not directly usable on its own. @; gensolve.c takes this and massages it, interpreting the at signs as @; indicating directives, generating C source for a solver. #include #include #include @C #define HTSIZE 16777216 typedef unsigned char CELL; #define CELL_MARBLE 0x07 #define CELL_MARBLE_S 0 #define CELL_MARBLE_M 7 #define CELL_FIXED 0x38 #define CELL_F_EMPTY 0x00 #define CELL_F_WALL 0x08 #define CELL_F_BREAK 0x10 #define CELL_F_TPORT 0x18 #define CELL_F_DIODE 0x20 #define CELL_F_DBARS 0x28 #define CELL_F_AUX 0xc0 #define CELL_F_AUX_S 6 #define CELL_F_AUX_M 3 #define CELL_F_LF 0x00 #define CELL_F_UP 0x40 #define CELL_F_RT 0x80 #define CELL_F_DN 0xc0 static const int deltas[4][2] = { [CELL_F_RT>>CELL_F_AUX_S] = { 1, 0 }, [CELL_F_DN>>CELL_F_AUX_S] = { 0, 1 }, [CELL_F_LF>>CELL_F_AUX_S] = { -1, 0 }, [CELL_F_UP>>CELL_F_AUX_S] = { 0, -1 } }; typedef struct marble MARBLE; struct marble { unsigned char colour; unsigned char x; unsigned char y; } ; typedef struct board BOARD; struct board { CELL b[SIZEX][SIZEY]; MARBLE m[NMARBLES]; unsigned char depth; unsigned int hash; int dm; BOARD *link; BOARD *hlink; const BOARD *parent; } ; @B static unsigned int crctbl[256]; static BOARD *htable[HTSIZE]; static BOARD *dlist; @G static void panic(void) { fflush(0); (void)*(volatile char *)0; abort(); } static void build_crctbl(void) { unsigned int h; int i; int j; for (i=256-1;i>=0;i--) { h = i; for (j=8;j>0;j--) h = (h >> 1) ^ ((h & 1) ? 0xedb88320 : 0); crctbl[i] = h; } } static void init_hash(void) { int i; for (i=HTSIZE-1;i>=0;i--) htable[i] = 0; } static void hashboard(BOARD *b) { unsigned int h; int x; int y; h = 0x12345678; for (x=SIZEX-1;x>=0;x--) for (y=SIZEY-1;y>=0;y--) h = (h >> 8) ^ crctbl[(h^b->b[x][y])&0xff]; b->hash = h; } static void hash_insert(BOARD *b) { b->hlink = htable[b->hash%HTSIZE]; htable[b->hash%HTSIZE] = b; } static BOARD *hash_find(BOARD *b) { BOARD *t; for (t=htable[b->hash%HTSIZE];t;t=t->link) { if ((t->hash == b->hash) && (t->dm == b->dm) && !bcmp(&t->b[0][0],&b->b[0][0],SIZEX*SIZEY)) return(t); } return(0); } static void dumpboard(const BOARD *b) { int x; int y; char c; for (y=0;yb[x][y] & CELL_MARBLE) { c = 'A' + (b->b[x][y] & CELL_MARBLE) - 1; } else { switch (b->b[x][y] & CELL_FIXED) { case CELL_F_EMPTY: c = '.'; break; case CELL_F_WALL: c = 'X'; break; case CELL_F_BREAK: c = '1'; break; case CELL_F_TPORT: c = "O@@Ø©"[(b->b[x][y]>>CELL_F_AUX_S)&CELL_F_AUX_M]; break; case CELL_F_DIODE: switch (b->b[x][y] & CELL_F_AUX) { default: panic(); break; case CELL_F_LF: c = '<'; break; case CELL_F_RT: c = '>'; break; case CELL_F_UP: c = '^'; break; case CELL_F_DN: c = 'v'; break; } break; case CELL_F_DBARS: switch (b->b[x][y] & CELL_F_AUX) { default: panic(); break; case CELL_F_LF: c = '«'; break; case CELL_F_RT: c = '»'; break; case CELL_F_UP: c = '~'; break; case CELL_F_DN: c = '_'; break; } break; default: c = '?'; break; } } if (x) putchar(' '); putchar(c); } if (y == 0) { printf(" %d",b->depth); if (b->dm >= 0) printf(" %d=(%d,%d)",b->dm,b->m[b->dm].x,b->m[b->dm].y); } printf("\n"); } } static void dumpsolution(const BOARD *b) { if (b->parent) { dumpsolution(b->parent); printf("----\n"); } dumpboard(b); } static void try_marble_in(const BOARD *b, int mx, int d, int forced) { static BOARD *n = 0; BOARD *hf; int x; int y; int dx; int dy; int xx; int yy; int tx; int ty; CELL c; int barred; if (! n) n = malloc(sizeof(BOARD)); *n = *b; n->dm = -1; x = b->m[mx].x; y = b->m[mx].y; dx = deltas[d][0]; dy = deltas[d][1]; xx = x; yy = y; #ifdef DETAIL printf("moving (%d,%d)=%d (%d,%d)\n",x,y,(b->b[x][y]>>CELL_MARBLE_S)&CELL_MARBLE_M,dx,dy); #endif while <"move"> (1) { if ((xx < 0) || (yy < 0) || (xx >= SIZEX) || (yy >= SIZEY)) panic(); c = n->b[xx+dx][yy+dy]; if (c & CELL_MARBLE) break <"move">; switch (c & CELL_FIXED) { case CELL_F_EMPTY: break; case CELL_F_WALL: break <"move">; case CELL_F_BREAK: n->b[xx+dx][yy+dy] = CELL_F_EMPTY; break <"move">; case CELL_F_TPORT: tx = tportto[xx+dx][yy+dy][0]; ty = tportto[xx+dx][yy+dy][1]; if ((tx < 0) || (ty < 0) || (tx >= SIZEX) || (ty >= SIZEY)) panic(); if ((n->b[tx][ty] & CELL_MARBLE) == 0) { xx = tx - dx; yy = ty - dy; } break; case CELL_F_DIODE: barred = 0; if (0) { case CELL_F_DBARS: barred = 1; } switch (c & CELL_F_AUX) { default: panic(); break; case CELL_F_LF: tx = -1; ty = 0; break; case CELL_F_RT: tx = 1; ty = 0; break; case CELL_F_UP: tx = 0; ty = -1; break; case CELL_F_DN: tx = 0; ty = 1; break; } if ((tx == dx) && (ty == dy)) break; if ((tx == -dx) && (ty == -dy)) break <"move">; if (barred) break <"move">; xx += dx; yy += dy; n->dm = mx; break <"move">; } xx += dx; yy += dy; } if ((xx == x) && (yy == y) && !forced) return; n->depth = b->depth + 1; n->parent = forced ? b->parent : b; n->m[mx].x = xx; n->m[mx].y = yy; n->b[x][y] &= ~CELL_MARBLE; n->b[xx][yy] |= b->b[x][y] & CELL_MARBLE; if ((n->dm < 0) && goal(n)) { printf("goal reached\n"); dumpsolution(n); exit(0); } hashboard(n); hf = hash_find(n); if (hf) { #ifdef DETAIL printf("already present %p\n",(void *)hf); #endif } else { hash_insert(n); n->link = dlist; dlist = n; #ifdef DETAIL printf("saving new %p\n",(void *)n); dumpboard(n); #endif n = 0; } } static void allmoves(const BOARD *b) { int m; int x; int y; int d; #ifdef DETAIL printf("testing moves from %p\n",(const void *)b); dumpboard(b); #endif if (b->dm < 0) { for (m=NMARBLES-1;m>=0;m--) { for (d=4-1;d>=0;d--) { try_marble_in(b,m,d,0); } } } else { x = b->m[b->dm].x; y = b->m[b->dm].y; switch (b->b[x][y] & CELL_FIXED) { default: panic(); break; case CELL_F_DIODE: case CELL_F_DBARS: break; } try_marble_in(b,b->dm,(b->b[x][y]>>CELL_F_AUX_S)&CELL_F_AUX_M,1); } } static void deepen(void) { BOARD *b; if (! dlist) { printf("no solution found\n"); exit(0); } b = dlist; dlist = 0; for (;b;b=b->link) allmoves(b); } int main(void); int main(void) { build_crctbl(); init_hash(); initboard.link = 0; initboard.depth = 0; initboard.parent = 0; initboard.dm = -1; hashboard(&initboard); hash_insert(&initboard); dlist = &initboard; while (1) { deepen(); } }