/* * Program to brute-force solutions to Ricochet Robots problems. * * Ricochet Robots is a commercial game which turns a puzzle into a * multiplayer game. This program is about the underlying puzzle, not * the game. * * The physical equipment of the game consists of a game board which * comes in four double-sided pieces, each of which can be placed * either side up and has one distinguished corner. The four * distinguished corners are placed together to form the centre of the * board. Considering rotations as identical, this can be done in 96 * ways: 4! (orderings of the pieces) times 2^4 (each piece either * side up) divided by 4 (the reduction factor for rotations being * considered identical - the resulting board is square). The * resulting 16x16 board has walls printed around the outside edge, * two unit walls projecting in from each side, and 17 interior * squares with two adjacent walls printed and a coloured goal symbol * on the square. The other squares are blank. There is also a * plastic piece which has no game function; all it does is to hold * the board together by the centre - the distinguished corners have * holes in them which the plastic piece fits into. There are five * plastic shapes (red, green, blue, yellow, and silver), representing * robots, and five small chips of matching colours, suitable for * placing in a square and placing a robot on. There are then * seventeen small circular chips, with one side identical and the * other bearing copies of the symbols on the 17 goal squares. 16 of * these symbols are coloured red, green, blue, and yellow, matching * four of the robots' colours; the 17th is a swirl made up of all the * colours - the documentation calls it the `vortex' and the graphic * is appropriate to the name. There is also a timer, which serves no * purpose when viewing the thing as a puzzle; it has function only in * the conversion of that puzzle to a multiplayer game. In order to * arrange that all 17 goal squares appear regardless of how the board * is built, each board piece has the same goal squares on each side, * just with them, and the walls, arranged differently. * * The puzzle consists of turning up a chip and finding a way to get * the robot of that colour to the goal square which matches the chip, * preferably in as few moves as possible. (The way this is converted * to a multiplayer game, while clever, is not relevant to the puzzle * point of view and I will thus ignore it here.) There are, of * course, constraints on robots' motions, or there would be no * puzzle. * * Robots move orthogonally only, somewhat like the chess rook. * However, they cannot move through walls or other robots, and, once * they start moving, they cannot stop until they run into a wall or * another robot - it is not possible for them to stop before that. * So, from a given position, each robot has at most four moves, one * in each of the four cardinal directions. (It may have fewer, if * it's immediately blocked by a wall or robot in some or all of those * directions.) There are two additional restrictions: the target * robot (the one of the colour turned) must make at least one * 90-degree turn before reaching the goal, and a robot may not make a * 180-degree turn without another robot moving in between. (The * former is apparently designed to deal with cases where a robot can * move directly to its goal; the latter, to deal with a possible * reaction to the former.) This program ignores the former; given * that, the latter is completely pointless and is ignored too. * * For example, as a much-smaller example, consider this mini-puzzle, * where * is the goal spot, R is the target robot, and a and b are * other robots: * * +---+---+---+---+---+ * | a | | * + + + + + + * | | * | * + +---+ +---+ + * | | | * +---+ + + + + * | R b | * + + + + +---+ * | | | * +---+---+---+---+---+ * * This particular puzzle has a fairly easy solution in 4 moves: b up, * R right, R up, R left. (It has other solutions; for example, it * can be solved in 7 moves without moving either a or b - move R * right, up, right, up, left, down, left - or 6 by moving a but not * b, with a right, R up, R left, R up, R right, R down.) * * We do simple breadth-first search. A board position is represented * as a 40-bit number, with four bits each representing X and Y * coordinates for each of the five robots. (There is a little * redundancy in this representation, in that it can represent * multiple robots on the same square, which is impossible, and that * it can represent robots on the inaccessible four centre cells. The * actual number of possible positions is 252*251*250*249*248, or * 976484376000, as compared to 2^40=1099511627776 possible * representations, for about 11% wastage - about 11% of the possible * representations represent impossible positions. We ignore this * waste, especially since it is much less than one bit, and allows us * to support the game's choice of not using the silver robot by * including the four walls interior to the centre and placing the * silver robot on one of those squares, so it is never able to move.) * The walls are represented separately, since they do not change when * working on any particular puzzle; only the robots' positions * change, so that is the only part we care about storing compactly. * * The puzzle is compiled into the program. This is for coding * convenience rather than because it's actually required; I didn't * want to bother defining an input puzzle representation and writing * a parser for it until I knew whether the technique were actually * workable. The wall locations are kept in binit[] (except for the * outer border of 64 walls, which are generated algorithmically in * setup_board()); the robot starting locations and goal cell are * specified in the arguments to do_search(), in main(). * * Breadth-first search like this requires that we know when we've * found a position again. We store a maximum of MAXPOSN positions, * keeping them in a hash table of HTSIZE entries; however, positions * are moderately large (13 bytes of persistent storage; in the queue * of nodes to searc, either 20 or 24 bytes each (on amd64) depending * on whether the compiler decides to pad struct pq), so the hash * table just contains int indices into the posn[], pdepth[], and * pfrom[] arrays. (In a sense, these should be an array of structs, * but either it'd have to be packed and pay big performance penalties * or be non-packed and pay big padding wastage penalties.) * * Ideally MAXPOSN and HTSIZE would be dynamic, but then we have to * deal with rehashing and suchlike. */ #include #include #include #include #include extern const char *__progname; #define MAXPOSN 16777216 #define HTSIZE 33554467 typedef struct binit BINIT; typedef struct pq PQ; typedef struct rshift RSHIFT; struct rshift { int s; unsigned char fill; char c; } ; struct binit { unsigned char x; unsigned char y; unsigned char bit; } ; typedef unsigned long long int POSN; #define POSN_S_R_R 0 #define POSN_S_R_G 8 #define POSN_S_R_B 16 #define POSN_S_R_Y 24 #define POSN_S_R_S 32 #define POSN_S_L_X 0 #define POSN_S_L_Y 4 #define POSN_MASK ((POSN)0xf) struct pq { PQ *link; POSN p; int from; } ; static unsigned char board[16][16]; #define WALLS 0xf0 #define WALL_L 0x10 #define WALL_U 0x20 #define WALL_R 0x40 #define WALL_D 0x80 #define CONTENTS 0x0f #define C_EMPTY 0x00 #define C_R_R 0x01 #define C_R_G 0x02 #define C_R_B 0x03 #define C_R_Y 0x04 #define C_R_S 0x05 static unsigned char pdepth[MAXPOSN]; static int pfrom[MAXPOSN]; static POSN posn[MAXPOSN]; static int nposn; static int htbl[HTSIZE]; static PQ *freepq = 0; static RSHIFT rsv[] = { { POSN_S_R_R, C_R_R, 'R' }, { POSN_S_R_G, C_R_G, 'G' }, { POSN_S_R_B, C_R_B, 'B' }, { POSN_S_R_Y, C_R_Y, 'Y' }, { POSN_S_R_S, C_R_S, 'S' } }; static BINIT binit[] = { /* edge-projecting walls */ { 4, 0, WALL_R }, { 9, 0, WALL_R }, { 15, 1, WALL_D }, { 0, 4, WALL_D }, { 15, 9, WALL_D }, { 0, 10, WALL_D }, { 4, 15, WALL_R }, { 11, 15, WALL_R }, /* centre square */ { 7, 7, WALL_L }, { 7, 7, WALL_U }, { 7, 8, WALL_L }, { 7, 8, WALL_D }, { 7, 7, WALL_R }, { 7, 7, WALL_D }, { 8, 7, WALL_R }, { 8, 7, WALL_U }, { 8, 8, WALL_R }, { 8, 8, WALL_D }, { 7, 7, WALL_L }, { 7, 7, WALL_U }, /* interior walls */ { 2, 1, WALL_L }, { 2, 1, WALL_U }, { 13, 1, WALL_R }, { 13, 1, WALL_D }, { 6, 3, WALL_L }, { 6, 3, WALL_D }, { 9, 3, WALL_L }, { 9, 3, WALL_U }, { 14, 4, WALL_R }, { 14, 4, WALL_U }, { 4, 5, WALL_R }, { 4, 5, WALL_U }, { 1, 6, WALL_R }, { 1, 6, WALL_D }, { 12, 6, WALL_L }, { 12, 6, WALL_D }, { 4, 9, WALL_L }, { 4, 9, WALL_D }, { 6, 10, WALL_L }, { 6, 10, WALL_U }, { 8, 10, WALL_R }, { 8, 10, WALL_D }, { 13, 11, WALL_L }, { 13, 11, WALL_U }, { 7, 12, WALL_R }, { 7, 12, WALL_U }, { 1, 13, WALL_R }, { 1, 13, WALL_U }, { 9, 13, WALL_L }, { 9, 13, WALL_D }, { 3, 14, WALL_R }, { 3, 14, WALL_D }, { 14, 14, WALL_R }, { 14, 14, WALL_U }, { 0, 0, 0 } }; static void setwall(int x, int y, unsigned char bit) { board[x][y] |= bit; switch (bit) { case WALL_L: if (x == 0) abort(); board[x-1][y] |= WALL_R; break; case WALL_R: if (x == 15) abort(); board[x+1][y] |= WALL_L; break; case WALL_U: if (y == 0) abort(); board[x][y-1] |= WALL_D; break; case WALL_D: if (y == 15) abort(); board[x][y+1] |= WALL_U; break; default: abort(); break; } } static void setup_board(void) { int i; int j; for (i=16-1;i>=0;i--) { for (j=16-1;j>=0;j--) { board[i][j] = C_EMPTY; } } for (i=16-1;i>=0;i--) { board[i][0] |= WALL_U; board[i][15] |= WALL_D; board[0][i] |= WALL_L; board[15][i] |= WALL_R; } for (i=0;binit[i].bit;i++) setwall(binit[i].x,binit[i].y,binit[i].bit); } static void setup_search(void) { int i; for (i=HTSIZE-1;i>=0;i--) htbl[i] = -1; nposn = 0; } static void fill_from_posn(POSN p, int ps, unsigned char fill) { unsigned char *bp; if (fill & ~CONTENTS) abort(); bp = &board[(p>>(ps+POSN_S_L_X))&POSN_MASK][(p>>(ps+POSN_S_L_Y))&POSN_MASK]; *bp = (*bp & ~CONTENTS) | fill; } static PQ *new_pq(void) { static int npq = -1; PQ *p; if (! freepq) { void *mmrv; int i; if (npq < 0) npq = 16777216 / sizeof(PQ); mmrv = mmap(0,npq*sizeof(PQ),PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE,-1,0); if (mmrv == MAP_FAILED) { fprintf(stderr,"%s: mmap anonymous memory: %s\n",__progname,strerror(errno)); exit(1); } p = mmrv; for (i=npq;i>0;i--) { p->link = freepq; freepq = p; p ++; } } p = freepq; freepq = p->link; return(p); } static void old_pq(PQ *p) { p->link = freepq; freepq = p; } static int htfind(POSN p) { unsigned int h; int x; h = p % HTSIZE; while (1) { x = htbl[h]; if (x < 0) return(-1); if (posn[x] == p) return(x); h ++; if (h >= HTSIZE) h = 0; } } static int htenter(POSN p, int depth, int from) { unsigned int h; int x; if (nposn >= MAXPOSN) { fprintf(stderr,"%s: out of position room\n",__progname); exit(1); } posn[nposn] = p; pfrom[nposn] = from; pdepth[nposn] = depth; h = p % HTSIZE; while (1) { x = htbl[h]; if (x < 0) break; h ++; if (h >= HTSIZE) h = 0; } htbl[h] = nposn; return(nposn++); } static void attempt_moves(POSN p, void (*each)(POSN)) { int csx; int x0; int y0; int x; int y; int dir; static struct { unsigned char wall; int dx; int dy; } dirs[4] = { { WALL_L, -1, 0 }, { WALL_R, 1, 0 }, { WALL_U, 0, -1 }, { WALL_D, 0, 1 } }; for (csx=5-1;csx>=0;csx--) { x0 = (p >> (rsv[csx].s+POSN_S_L_X)) & POSN_MASK; y0 = (p >> (rsv[csx].s+POSN_S_L_Y)) & POSN_MASK; for (dir=4-1;dir>=0;dir--) { x = x0; y = y0; while (1) { if (board[x][y] & dirs[dir].wall) break; x += dirs[dir].dx; y += dirs[dir].dy; if ( (x < 0) || (x >= 16) || (y < 0) || (y >= 16) || ((board[x][y] & CONTENTS) != C_EMPTY) ) { x -= dirs[dir].dx; y -= dirs[dir].dy; break; } } if ((x != x0) || (y != y0)) (*each)( ( p & ~( (POSN_MASK<<(rsv[csx].s+POSN_S_L_X)) | (POSN_MASK<<(rsv[csx].s+POSN_S_L_Y)) ) ) | (((POSN)x)<<(rsv[csx].s+POSN_S_L_X)) | (((POSN)y)<<(rsv[csx].s+POSN_S_L_Y)) ); } } } static void place_robots(POSN p) { fill_from_posn(p,POSN_S_R_R,C_R_R); fill_from_posn(p,POSN_S_R_G,C_R_G); fill_from_posn(p,POSN_S_R_B,C_R_B); fill_from_posn(p,POSN_S_R_Y,C_R_Y); fill_from_posn(p,POSN_S_R_S,C_R_S); } static void unplace_robots(POSN p) { fill_from_posn(p,POSN_S_R_R,0); fill_from_posn(p,POSN_S_R_G,0); fill_from_posn(p,POSN_S_R_B,0); fill_from_posn(p,POSN_S_R_Y,0); fill_from_posn(p,POSN_S_R_S,0); } static void done(int px, POSN last) { POSN prev; void stepto(POSN p, unsigned char depth) { if (prev) { int i; for (i=5-1;i>=0;i--) { if ((p ^ prev) & (((POSN_MASK << POSN_S_L_X) | (POSN_MASK << POSN_S_L_Y)) << rsv[i].s)) { if ( ((p >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) < ((prev >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) ) printf("%c < ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) > ((prev >> (rsv[i].s+POSN_S_L_X)) & POSN_MASK) ) printf("%c > ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) < ((prev >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) ) printf("%c ^ ",rsv[i].c); if ( ((p >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) > ((prev >> (rsv[i].s+POSN_S_L_Y)) & POSN_MASK) ) printf("%c v ",rsv[i].c); } } } else { printf(" "); } printf("R(%d,%d) G(%d,%d) B(%d,%d) Y(%d,%d) S(%d,%d) %d\n", (int)((p >> (POSN_S_R_R+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_R+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_G+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_G+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_B+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_B+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_Y+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_Y+POSN_S_L_Y)) & POSN_MASK), (int)((p >> (POSN_S_R_S+POSN_S_L_X)) & POSN_MASK), (int)((p >> (POSN_S_R_S+POSN_S_L_Y)) & POSN_MASK), depth ); prev = p; } void printdone(int x) { if (x < 0) abort(); if (pdepth[x]) printdone(pfrom[x]); stepto(posn[x],pdepth[x]); } prev = 0; printdone(px); stepto(last,pdepth[px]+1); } static void do_search(POSN root, POSN gmask, POSN gval) { PQ *q; PQ *nextq; PQ *qe; int qex; int qdepth; int qlen; int any; void mvto(POSN p) { PQ *e; if ((p & gmask) == gval) { if (any) printf("\n"); any = 1; done(qex,p); fflush(0); } if (any) return; e = new_pq(); e->link = nextq; nextq = e; e->p = p; e->from = qex; qlen ++; } nextq = new_pq(); nextq->link = 0; nextq->p = root; nextq->from = -1; qdepth = -1; qlen = 1; any = 0; while (nextq) { if (any) break; q = nextq; nextq = 0; qdepth ++; printf("depth %d qlen %d nposn %d\n",qdepth,qlen,nposn); fflush(0); qlen = 0; if (! q) { printf("failure\n"); exit(0); } while (q) { qe = q; q = q->link; if (htfind(qe->p) < 0) { qex = htenter(qe->p,qdepth,qe->from); place_robots(qe->p); attempt_moves(qe->p,&mvto); unplace_robots(qe->p); } old_pq(qe); } } } int main(void); int main(void) { setup_board(); setup_search(); do_search( ( ((POSN) 7) << (POSN_S_R_S+POSN_S_L_X) ) | ( ((POSN) 1) << (POSN_S_R_S+POSN_S_L_Y) ) | ( ((POSN) 2) << (POSN_S_R_B+POSN_S_L_X) ) | ( ((POSN) 5) << (POSN_S_R_B+POSN_S_L_Y) ) | ( ((POSN)12) << (POSN_S_R_Y+POSN_S_L_X) ) | ( ((POSN) 8) << (POSN_S_R_Y+POSN_S_L_Y) ) | ( ((POSN)11) << (POSN_S_R_G+POSN_S_L_X) ) | ( ((POSN)11) << (POSN_S_R_G+POSN_S_L_Y) ) | ( ((POSN) 2) << (POSN_S_R_R+POSN_S_L_X) ) | ( ((POSN)12) << (POSN_S_R_R+POSN_S_L_Y) ), ( POSN_MASK << (POSN_S_R_Y+POSN_S_L_X) ) | ( POSN_MASK << (POSN_S_R_Y+POSN_S_L_Y) ), ( ((POSN) 8) << (POSN_S_R_Y+POSN_S_L_X) ) | ( ((POSN)10) << (POSN_S_R_Y+POSN_S_L_Y) ) ); return(0); } /* S 7,1 B 2,5 Y 12,8 G 11,11 R 2,12 goal Y 8,10 +-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+ | | | | | | | | | | | | + + +-------+ + + + + + + + + + + + + + | | --- | | | | Y a | S | G b | | | | --- | | + + + + + + + + + + + + + +-------+ +-------+ | | | | | | + + + + + + + + + +-------+ + + + + + + | | | | | | B b | B d | | | | | + + + + + + +-------+ + + + + + + +-------+ + | | | | R a | | | | | +-------+ + + +-------+ + + + + + + + + + + + | --- | | | | B | R d | | | --- | | + + + + + + + + + + + + + + + + + | | | | | G c | | Y c | | | | | + +-------+ + + + + +-------+-------+ + + +-------+ + + + | | | | | | | | | | | | + + + + + + + + + + + + + + + + + | | | --- | | | | | Y | | | | | --- | + + + + + + + +-------+-------+ + + + + + + + | | | | | Y b | | | | + + + + +-------+ +-------+ + + + + + + + +-------+ | | | | | | B a Y d | | | | | | +-------+ + + + + + + +-------+ + + + +-------+ + + | --- | | | | G | | B c | | --- | | + + + + + + + +-------+ + + + + + + + + | --- | | | | R | Vtx | | | --- | | + +-------+ + + + + + + + + + + + + + + | | | | | R c | | G a | | | | | + + + + + + + + + +-------+ + + + +-------+ + | | | | | G d | R b | | | | | | + + + +-------+ + + + + + + + + + + + + | | | | | | | | | | | | +-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+ Playing Yd 26: R <^> S >^v> R ^<^>v> B v< Y v< 11: R >v B >v Y >v^> */