\datethis @*Introduction. This program solves a fairly general kind of sliding block puzzle. Indeed, it emphasizes generality over speed, although it does try to implement breadth-first search on large graphs in a reasonably efficient way. (I~plan to write a program based on more advanced techniques later, with this one available for doublechecking the results.) I apologize for not taking time to prepare a fancy user interface; all you'll find here is a shortest-path-to-solution-of-a-sliding-block-puzzle engine. @ The puzzle can have up to 15 different kinds of pieces, named in hexadecimal from \.1 to~\.f. These pieces are specified in the standard input file, one line per piece, by giving a rectangular pattern of 0s and~1s, where 0 means `empty' and 1~means `occupied'. Rows of the pattern are separated by slashes as in the examples below. The first line of standard input is special: It should contain the overall board size in the form `\\{rows} \.x \\{columns}', followed by any desired commentary (usually the name of the puzzle). This first line is followed by piece definitions of the form `\\{piecename} \.= \\{pattern}'. Two more lines of input should follow the piece definitions, one for the starting configuration and one for the stopping configuration. (I may extend this later to allow several ways to stop.) Each configuration is specified in a shorthand form by telling how to fill in the board, repeatedly naming the piece that occupies the topmost and leftmost yet-unspecified cell, or \.0 if that cell is empty, or \.x if that cell is permanently blocked. Trailing zeros may be omitted. For example, here's how we could specify a strange (but easy to solve) $5\times5$ puzzle that has four pieces of three kinds: $$\vbox{\halign{\tt#\hfill\cr 5 x 5 (a silly example)\cr 1 = 111/01\cr 2 = 101/111\cr 3 = 1\cr 1xx200000000033\cr 000xx00033001002\cr }}$$ The same puzzle can be illustrated more conventionally as follows: $$\setbox0=\hbox to 0pt{\hss\vrule height8.5pt depth3.5pt\hss} \setbox1=\hbox{\smash{\lower3.7pt\vbox{\hrule width 12pt}}} \catcode`\!=\active \def!{\copy0} \def\\#1{\hbox to 12pt{\hss#1\hss}} \def\_#1{\hbox to 12pt{\copy1\kern-12pt\hss#1\hss}} \vbox{\offinterlineskip\halign{\strut\tt#\hfil\cr \hidewidth\hfil\rm Starting position\hidewidth\cr \noalign{\vskip-6pt} \_{}\_{}\_{}\cr !\_1\\1\_1!\_{}\_{}\cr !\\2!\_1!\\2!\_0!\_0!\cr !\_2\_2\_2!\_0!\_0!\cr !\_0!\_0!\_0!\_0!\_0!\cr !\_3!\_3!\_0!\_0!\_0!\cr}} \hskip10em \vbox{\offinterlineskip\halign{\strut\tt#\hfil\cr \hidewidth\hfil\rm Stopping position\hidewidth\cr \noalign{\vskip-6pt} \_{}\_{}\_{}\cr !\_0!\_0!\_0!\_{}\_{}\cr !\_0!\_0!\_0!\_3!\_3!\cr !\_0!\_0!\_1\\1\_1!\cr !\_0!\_0!\\2!\_1!\\2!\cr !\_0!\_0!\_2\_2\_2!\cr}} $$ The two `\.3' pieces are indistinguishable from each other. If I had wanted to distinguish them, I would have introduced another piece name, for example by saying `\.{4 = 1}'. @ Six different styles of sliding-block moves are supported by this program, and the user should specify the desired style on the command line. \smallskip \def\sty#1. {\par\noindent\hangindent 30pt\hbox{\bf Style #1.\enspace}} \sty0. Move a single piece one step left, right, up, or down. The newly occupied cells must previously have been empty. \sty1. Move a single piece one or more steps left, right, up, or down. (This is a sequence of style-0 moves, all applied to the same piece in the same direction, counted as a single move.) \sty2. Move a single piece one or more steps. (This is a sequence of style-0 moves, all applied to the same piece but not necessarily in the same direction.) \sty3. Move a subset of pieces one step left, right, up, or down. (This is like style~0, but several pieces may move as if they were a single ``superpiece.'') \sty4. Move a subset of pieces one or more steps left, right, up, or down. (This is the superpiece analog of style~1.) \sty5. Move a subset of pieces one or more steps. (The superpiece analog of style~2.) \smallskip\noindent The subsets of pieces moved in styles 3, 4, and 5 need not be connected to each other. Indeed, an astute reader will have noticed that our input conventions allow individual pieces to have disconnected components. The silly puzzle specified above can, for example, be solved in respectively (20, 10, 4, 10, 4, 2) moves of styles (0, 1, 2, 3, 4, 5). Notice that a small change to that puzzle would make certain positions impossible without superpiece moves; thus, superpiece moves are not simply luxuries, they might be necessary when solving certain puzzles. @ OK, here now is the general outline of the program. There are no surprises yet, except perhaps for the fact that we prepare to make a |longjmp|. @d verbose Verbose /* avoid a possible 64-bit-pointer glitch in \.{libgb} */ @c #include #include #include #include "gb_flip.h" /* GraphBase random number generator */ typedef unsigned int uint; jmp_buf success_point; int style; int verbose; @@; @@; main(int argc, char *argv[]) { register int j,k,t; volatile int d; @; @; @; @; hurray: @; } @ If the style parameter is followed by another parameter on the command line, the second parameter causes verbose output if it is positive, or suppresses the solution details if it is negative. @= if (!(argc>=2 && sscanf(argv[1],"%d",&style)==1 &&@| (argc==2 || sscanf(argv[2],"%d",&verbose)==1))) { fprintf(stderr,"Usage: %s style [verbose]\n",argv[0]); exit(-1); } if (style<0 || style>5) { fprintf(stderr, "Sorry, the style should be between 0 and 5, not %d!\n",style); exit(-2); } @* Representing the board. An $r\times c$ board will be represented as an array of $rc+2c+r+1$ entries. The upper left corner corresponds to position $c+1$ in this array; moving up, down, left, or right corresponds to adding $-(c+1)$, $(c+1)$, $-1$, or $1$ to the current board position. Boundary marks appear in the first $c+1$ and last $c+1$ positions, and in positions $c+k(c+1)$ for $1\le k= int board[boardsize]; /* main board for analyzing configurations */ int aboard[boardsize]; /* auxiliary board */ int rows; /* the number of rows in the board */ int cols; /* the number of columns in the board */ int colsp; /* |cols+1| */ int ul,lr; /* location of upper left and lower right corners in the board */ int delta[4]={1,-1}; /* offsets in |board| for moving right, left, down, up */ @ Every type of piece is specified by a list of board offsets from the piece's topmost/leftmost cell, terminated by zero. For example, the offsets for the piece named \.1 in the silly example are $(1, 2, 7, 0)$ because there are five columns. If there had been six columns, the same piece would have had offsets $(1,2,8,0)$. The following code is executed when a new piece is being defined. @d boardover() { fprintf(stderr,"Sorry, I can't handle that large a board;\n"); fprintf(stderr," please recompile me with more maxsize.\n"); exit(-3); } @= { register char *p; for (t=-1,j=k=0,p=&buf[4];;p++) switch (*p) { case '1':@+ if (t<0) t=k;@+else off[curo++]=k-t; if (curo>=maxsize) boardover(); case '0': j++,k++;@+break; case '/': k+=colsp-j,j=0;@+break; case '\n': goto offsets_done; default: fprintf(stderr, "Bad character `%c' in definition of piece %c!\n",*p,buf[0]); exit(-4); } offsets_done:@+ if (t<0) { fprintf(stderr,"Piece %c is empty!\n",buf[0]);@+exit(-5); } off[curo++]=0; if (curo>=maxsize) boardover(); } @ @d bufsize 1024 /* maximum length of input lines */ @= int off[maxsize]; /* offset lists for pieces */ int offstart[16]; /* starting points in the |off| table */ int curo; /* the number of offsets stored so far */ char buf[bufsize]; /* input buffer */ @ A board position is specified by putting block numbers in each occupied cell. The number of blocks on the board might exceed the number of piece types, since different blocks can have the same type; we assign numbers arbitrarily to the blocks. For example, the |board| array might look like this in the ``silly'' starting position: $$\vbox{\halign{\hfil#\hfil&&\quad\hfil#\hfil\cr |bdry|&|bdry|&|bdry|&|bdry|&|bdry|&|bdry|\cr 4&4&4&|obst|&|obst|&|bdry|\cr 3&4&3&0&0&|bdry|\cr 3&3&3&0&0&|bdry|\cr 0&0&0&0&0&|bdry|\cr 2&1&0&0&0&|bdry|\cr |bdry|&|bdry|&|bdry|&|bdry|&|bdry|\cr}}$$ Any permutation of the numbers $\{1,2,3,4\}$ would be equally valid. @ Here is a subroutine that fills the board from a specification in the input buffer. It returns |-1| if too many cells are specified, or |-2| if an illegal character is found. Otherwise it returns the number of conflicts found, namely the number of cells that were erroneously filled more than once. @= int fill_board(int board[],int piece[],int place[]) { register int j,c,k,t; register char *p; for (j=0;j=0) if (++j>lr) return -1; if (*p=='0') board[j]=t=0; else if (*p>='1' && *p<='9') t=*p-'0'; else if (*p>='a' && *p<='f') t=*p-('a'-10); else if (*p=='x') t=0,board[j]=obst; else return -2; if (t) { bcount++; piece[bcount]=t; place[bcount]=j; board[j]=bcount; for (k=offstart[t];off[k];k++) if (j+off[k]
    lr || board[j+off[k]]>=0) c++; else board[j+off[k]]=bcount; } j++; } for (;j<=lr;j++) if (board[j]<0) board[j]=0; return c; } @ @= int bcount; /* the number of blocks on the board */ int piece[maxsize], apiece[maxsize]; /* the piece names of each block */ int place[maxsize], aplace[maxsize]; /* the topmost/leftmost positions of each block */ @ The next subroutine prints a given board on standard output, in a somewhat readable format that shows connections between adjacent cells of each block. The starting position specified by the ``silly'' input would, for example, be rendered thus: $$\catcode`\!=\active \chardef!="7C % vertical bar \obeyspaces \vbox{\baselineskip=9pt\halign{\tt#\hfill\cr 1-1-1\cr {} !\cr 2 1 2 0 0\cr ! !\cr 2-2-2 0 0\cr \cr 0 0 0 0 0\cr \cr 3 3 0 0 0\cr}}$$ @d cell(j,k) board[ul+(j)*colsp+k] @= void print_board(int board[],int piece[]) { register int j,k; for (j=0;j= @; @; @; @; @ @= fgets(buf,bufsize,stdin); if (sscanf(buf,"%d x %d",&rows,&cols)!=2 || rows<=0 || cols<=0) { fprintf(stderr,"Bad specification of rows x cols!\n"); exit(-6); } if (rows*cols>maxsize) boardover(); colsp=cols+1; delta[2]=colsp, delta[3]=-colsp; ul=colsp; lr=(rows+1)*colsp-2; @ @= for (j=1;j<16;j++) offstart[j]=-1; while (1) { if (!fgets(buf,bufsize,stdin)) { buf[0]='\n';@+ break; } if (buf[0]=='\n') continue; if (buf[1]!=' ' || buf[2]!='=' || buf[3]!=' ') break; if (buf[0]>='1' && buf[0]<='9') t=buf[0]-'0'; else if (buf[0]>='a' && buf[0]<='f') t=buf[0]-('a'-10); else { printf("Bad piece name (%c)!\n",buf[0]); exit(-7); } if (offstart[t]>=0) printf("Warning: Redefinition of piece %c is being ignored.\n", buf[0]); else { offstart[t]=curo; @; } } @ @= t=fill_board(board,piece,place); printf("Starting configuration:\n"); print_board(board,piece); if (t) { if (t>0) if (t==1) fprintf(stderr,"Oops, you filled a cell twice!\n"); else fprintf(stderr,"Oops, you overfilled %d cells!\n",t); else fprintf(stderr,"Oops, %s!\n", t==-1? "your board wasn't big enough": "the configuration contains an illegal character"); exit(-8); } if (bcount==0) { fprintf(stderr,"The puzzle doesn't have any pieces!\n"); exit(-9); } @ @= fgets(buf,bufsize,stdin); t=fill_board(aboard,apiece,aplace); printf("\nStopping configuration:\n"); print_board(aboard,apiece); if (t) { if (t>0) if (t==1) fprintf(stderr,"Oops, you filled a cell twice!\n"); else fprintf(stderr,"Oops, you overfilled %d cells!\n",t); else fprintf(stderr,"Oops, %s!\n", t==-1? "your board wasn't big enough": "the configuration contains an illegal character"); exit(-10); } for (j=0;j<16;j++) balance[j]=0; for (j=ul;j<=lr;j++) { if ((board[j]= int balance[16]; /* counters used to ensure that no pieces are lost */ @*Breadth-first search. Now we're ready for the heart of the calculation, which is conceptually very simple: If we have found all configurations reachable in fewer than $d$ moves, those reachable in $d$ moves are obtained by making one more move from each of those that are reachable in $d-1$. In other words, we want to proceed essentially as follows. $$\vbox{\halign{#\hfil\cr $c_1={}$starting position;\cr $m_0=1$; \ $k=2$;\cr {\bf for} $(d=1;$\ ;\ |d++|)\ $\{$\cr \quad$m_d=k$;\cr \quad{\bf for} $(j=m_{d-1};\ j= int pack(int board[],int piece[]) { register int i,j,k,p,s,t; for (j=ul;j<=lr;j++) xboard[j]=0; for (i=s=0,p=28,j=ul,t=bcount;t;j++) if (board[j]= char xboard[boardsize]; /* places filled ahead of time */ uint config[maxsize/8]; /* a packed configuration */ @ @= void print_config(uint config[], int n) { register int j,t; for (j=0;j>=4; printf("%0*x",j,t); /* we omit the trailing zeros */ } @ Conversely, we can reconstruct a board from its packed representation. @= int unpack(int board[],int piece[],int place[],uint config[]) { register int i,j,k,p,s,t; for (j=ul;j<=lr;j++) xboard[j]=0; for (p=i=0,j=ul,t=bcount;t;j++) if (board[j]>p)&0xf; if (k) { board[j]=t, piece[t]=k, place[t]=j; for (k=offstart[k];off[k];k++) xboard[j+off[k]]=1,board[j+off[k]]=t; t--; }@+else board[j]=0; } for (;j<=lr;j++) if (board[j]= gb_init_rand(0); for (j=0;j<4;j++) for (k=1;k<256;k++) uni[j][k]=gb_next_rand(); @ The number of hash chains, |hashsize|, should be a power of 2, and it deserves to be chosen somewhat carefully. If it is too large, we'll interfere with our machine's cache memory; if it is too small, we'll spend too much time going through hash chains. At present I've decided to assume that |hashsize| is at most $2^{16}$, so that the |uni| table entries are |short| (16-bit) quantities. The total number of configurations might be huge, so I allow 64 bits for the main hash table pointers. (Programmers in future years will chuckle when they read this code, having blissfully forgotten the olden days when people like me had to fuss over 32-bit numbers.) @d hashsize (1<<13) /* should be a power of two, not more than |1<<16| */ @d hashcode(x) (uni[0][x&0xff]+uni[1][(x>>8)&0xff]+ uni[2][(x>>16)&0xff]+uni[3][x>>24]) @= short uni[4][256]; /* bits for universal hashing */ uint hash[hashsize]; /* hash table pointers (low half) */ uint hashh[hashsize]; /* hash table pointers (high half) */ @ @= void print_big(uint hi, uint lo) { printf("%.15g",((double)hi)*4294967296.0+(double)lo); } @# void print_bigx(uint hi, uint lo) { if (hi) printf("%x%08x",hi,lo); else printf("%x",lo); } @ Of course I don't expect to keep all configurations in memory simultaneously, except on simple problems. Instead, I keep a table of |memsize| integers, containing variable-size packets that represent individual configurations. An address into this table is conceptually a 64-bit number, but we actually use the address mod |memsize| because stale data is discarded. The value of |memsize| is a power of~2 so that this reduction is efficient. The first word of a packet is a pointer to the previous packet having the same hash code. This pointer is {\it relative\/} to the current packet, so that it needs to contain only 32 bits at most. The second word of a packet |p| is a (relative) pointer to the configuration from which |p| was derived. This word could be omitted in the interests of space, but it is handy if we want to see an actual solution to the puzzle instead of merely knowing the optimum number of moves. The remaining words of a packet are the packed encoding of a configuration. If the packet begins near the end of the |pos| array, it actually extends past |pos[memsize]|; enough extra space has been provided there to avoid any need for wrapping packets around the |memsize| boundary. @d memsize (1<<25) /* space for the configurations we need to know about */ @d maxmoves 1000 /* upper bound on path length */ @= uint pos[memsize+maxsize/8+1]; /* currently known configurations */ uint cutoff; /* pointer below which we needn't search (low half) */ uint cutoffh; /* pointer below which we needn't search (high half) */ uint curpos; /* pointer to first unused configuration slot (low half) */ uint curposh; /* pointer to first unused configuration slot (high half) */ uint source; /* pointer to the configuration we're moving from (low half) */ uint sourceh; /* pointer to the configuration we're moving from (high half) */ uint nextsource, nextsourceh; /* next values of |source| and |sourceh| */ uint maxpos; /* pointer to first unusable configuration slot (low half) */ uint maxposh; /* pointer to first unusable configuration slot (high half) */ uint configs; /* total number of configurations so far (low half) */ uint configsh; /* total number of configurations so far (high half) */ uint oldconfigs; /* value of |configs| when we began working at distance |d| */ uint milestone[maxmoves]; /* value of |curpos| at various distances */ uint milestoneh[maxmoves]; /* value of |curposh| at various distances */ uint shortcut; /* |milestone[d]-cutoff| */ int goalhash; /* hash code for the stopping position */ uint goal[maxsize/8]; /* packed version of the stopping position */ uint start[maxsize/8]; /* packed version of the starting position */ @ The |hashin| subroutine looks for a given |board| configuration in the master table, inserting it if it is new. The value returned is 0 unless the |trick| parameter is nonzero. In the latter case, which is used for moves of style 2 or style 5, special processing needs to be done; we'll explain it later. @= int hashin(int trick) { register int h,j,k,n,bound; n=pack(board,piece); for (h=hashcode(config[0]),j=1;j; return 0; nope: bound-=pos[j]; if (bound<0) break; } newguy: @; if (h==goalhash) @; return trick; } @ If the current configuration achieves the goal, |hashin| happily terminates the search process, and sends control immediately to the external label called `|hurray|'. @= { for (k=0;k= if (setjmp(success_point)) goto hurray; /* get ready for |longjmp| */ @ @= j=curpos&(memsize-1); pos[j]=curpos-hash[h]; if (pos[j]>memsize || curposh>hashh[h]+(pos[j]>curpos)) pos[j]=memsize; /* relative link that exceeds all cutoffs */ pos[j+1]=curpos-source; /* relative link to previous position */ for (k=0;k; @; @ When we encounter a new configuration, we print it if it's the first to be found at the current distance, or if |verbose| is set. @= if (configs==oldconfigs || verbose>0) { print_config(config,n); if (verbose>0) { printf(" ("); print_big(configsh,configs); printf("=#"); print_bigx(curposh,curpos); printf(", from #"); print_bigx(sourceh,source); printf(")\n"); } } configs++; if (configs==0) configsh++; @ @= curpos+=n+2; if (curpos= printf("\n(using moves of style %d)\n",style); @; restart:@; @; for (d=1;d; if (configs==oldconfigs) exit(0); /* no solution */ if (verbose<=0) printf(" and %d more.\n",configs-oldconfigs-1); } printf("No solution found yet (maxmoves=%d)!\n",maxmoves); exit(0); @ @= t=pack(aboard,apiece); for (k=goalhash=0;k= t=pack(board,piece); for (k=0;k= curpos=cutoff=milestone[0]=1, curposh=cutoffh=milestoneh[0]=0; source=sourceh=configs=configsh=oldconfigs=d=0; maxposh=1; printf("*** Distance 0:\n"); hashin(0); if (verbose<=0) printf(".\n"); @ @= if (d>1) cutoff=milestone[d-2], cutoffh=milestoneh[d-2]; shortcut=curpos-cutoff; maxpos=cutoff+memsize, maxposh=cutoffh+(maxpos; } @* The answer. We've found a solution in |d| moves. @= if (d==0) { printf("\nYou're joking: That puzzle is solved in zero moves!\n"); exit(0); } printf("... Solution!\n"); if (verbose<0) exit(0); @; @; @ Going backward, we can reconstruct the winning line, as long as the data appears in the top |memsize| positions of our configuration list. @= if (curposh || curpos>memsize) { maxpos=curpos-memsize; maxposh=curposh-(maxpos>curpos); }@+else maxpos=maxposh=0; for (j=0;j<=lr+colsp;j++) aboard[j]=board[j]; while (sourceh>maxposh || (sourceh==maxposh && source>=maxpos)) { d--; if (d==0) exit(0); printf("\n%d:\n",d); k=source&(memsize-1); unpack(aboard,apiece,aplace,&pos[k+2]); print_board(aboard,apiece); if (source= printf("(Unfortunately I've forgotten how to get to level %d,\n", d); printf(" so I'll have to reconstruct that part. Please bear with me.)\n"); for (j=0;j= if (style<3) for (j=0;j<4;j++) for (k=1;k<=bcount;k++) move(k,delta[j],delta[j]); else @; @ In the |move| subroutine, parameter |k| is a block number, parameter |del| is a displacement, and parameter |delo| is such that we've recently considered a board with displacement |del-delo|. @= void move(int k, int del, int delo) { register int j,s,t; s=place[k], t=piece[k]; for (j=offstart[t];;j++) { /* we remove the piece */ board[s+off[j]]=0; if (!off[j]) break; } for (j=offstart[t];;j++) { /* we test if it fits in new position */ if (board[s+del+off[j]]) goto illegal; if (!off[j]) break; } for (j=offstart[t];;j++) { /* if so, we move it */ board[s+del+off[j]]=k; if (!off[j]) break; } if (hashin(style==2) || style==1) @@; else { for (j=offstart[t];;j++) { /* remove the shifted piece */ board[s+del+off[j]]=0; if (!off[j]) break; } illegal: for (j=offstart[t];;j++) { /* replace the unshifted piece */ board[s+off[j]]=k; if (!off[j]) break; } } } @ Style 1 is straightforward: We keep moving in direction |delo| until we bump into an obstacle. But style~2 is more subtle, because we need to explore all reachable possibilities. I thank Gary McDonald for pointing out a serious blunder in my first attempt to find all of the style-2 moves. The basic idea we use, to find all configurations that are reachable by moving a single piece any number of times, is the well-known technique of depth-first search. But there's a twist, because such a sequence of moves might go through configurations that already exist in the hash table; we can't simply stop searching when we encounter an old configuration. For example, consider the starting board \.{0102}, from which we can reach \.{0120} or \.{0012} or \.{1002} in a single move. A~second move, from \.{0120}, leads to \.{1020}. And then when we're considering possible second moves from \.{1002}, we dare not stop at the ``already seen'' \.{1020}, lest we fail to discover the move to \.{1200}. We can, however, argue that every valid style-2 move at distance~$d$ can be reached by a path that begins at distance $d-1$ and stays entirely at distance~$d$ after the first step. (The shortest path to that move clearly has this property.) Suppose we're exploring the style-2 moves at distance $d$ that are successors of configuration $\alpha$ at distance $d-1$. If we encounter some configuration~$\beta$ that has already been seen, there are two cases: The predecessor of~$\beta$ might be~$\alpha$, or it might be some other configuration, $\alpha'$. In the former case, we needn't explore any further past~$\beta$, because the depth-first search procedure will already have been there and done that. (Only one piece has moved, when changing from $\alpha$ to~$\beta$, so it must be the same as the piece we're currently trying to move.) On the other hand if $\alpha\ne\alpha'$, the example above shows that we need to look past~$\beta$ into potentially unknown territory, or we might miss some legal moves from~$\alpha$. In this second case we need a way to avoid encountering $\beta$ again and again, endlessly. To resolve this dilemma without adding additional ``mark bits'' to the data structure, we will {\it rename\/} the predecessor of~$\beta$, by changing it from $\alpha'$ to~$\alpha$. This change is legitimate, since $\beta$ is reachable in one move from both $\alpha'$ and~$\alpha$, which both are at distance~$d-1$. Then if we encounter $\beta$ again, we won't have to reconsider it; infinite looping will be impossible. This strategy tells us how to implement the unfinished ``tricky'' part of the |hashin| routine. When the following code is encountered, we've just found a known configuration~$\beta$ that begins at $j$ in the |pos| array. @= { if (bound= { for (j=offstart[t];;j++) { /* remove the shifted piece */ board[s+del+off[j]]=0; if (!off[j]) break; } for (j=offstart[t];;j++) { /* replace the unshifted piece */ board[s+off[j]]=k; if (!off[j]) break; } if (style==1) move(k,del+delo,delo); else for (j=0;j<4;j++) if (delta[j]!=-delo) move(k,del+delta[j],delta[j]); } @*Supermoving. The remaining job is the most interesting one: How should we deal with the possibility of sliding several blocks simultaneously? A puzzle with $m$ blocks has $2^m-1$ potential superpieces, and one can easily construct examples in which that upper limit is achieved. Fortunately, however, reasonable puzzles have only a reasonable number of superpiece moves; our job is to avoid examining unnecessary cases. The following algorithm is sort of a cute way to do that. First, we prepare for future calculations by making |aboard| an edited copy of |board|. In the process, we change |bdry| and |obst| items to zero, considering the zeros now to be a special kind of ``stuck'' block, and we link together all cells belonging to each block. This linking will be more efficient than the offset-oriented method used before. @= for (j=0;j<=bcount;j++) head[j]=-1; for (j=0;j<=lr+colsp;j++) { k=board[j]; if (k) { if (k>=obst) k=0; aboard[j]=k; link[j]=head[k]; head[k]=j; }@+else aboard[j]=-1; } @ Elementary graph theory helps now. Consider the digraph whose vertices are blocks, with arcs $u\to v$ whenever $u$ would bump into $v$ when block $u$ is shifted by a given amount. The superpieces are {\it ideals\/} of this graph, namely they have the property that if $u$ is in the superpiece and $u\to v$ then $v$ is also in the superpiece. Indeed, every ideal that is nonempty and does not contain the stuck block is a superpiece, and conversely. So the problem that faces us is equivalent to generating all such ideals in a given digraph. The complement of an ideal is an ideal of the dual digraph (the digraph in which arcs are reversed). And the digraph for sliding left is the dual of the digraph for sliding right. So the problem of generating all superpieces for left/right slides is equivalent to generating all ideals of the digraph that corresponds to moving from $k-1$ to $k$. If such an ideal doesn't contain the stuck block, it defines a superpiece for sliding right; otherwise its complement defines a superpiece for sliding left. We can construct that digraph by running through the links just made: After the following code has been executed, the arcs leading from~$u$ will be to |aboard|$[l]$, |aboard|$[l']$, |aboard|$[l'']$, etc., where $l=|out[u]|$, $l'=|olink|[l]$, $l''=|olink|[l']$, etc.; the arcs leading into~$u$ will be similar, with |in| and |ilink| instead of |out| and |olink|. @= for (j=0;j<=bcount;j++) out[j]=in[j]=-1; for (j=0;j<=bcount;j++) for (k=head[j];k>=ul;k=link[k]) { /* |aboard[k]=j| */ t=aboard[k-1]; if (t!=j && t>=0 && (out[t]<0 || aboard[out[t]]!=j)) { olink[k]=out[t], out[t]=k; ilink[k-1]=in[j], in[j]=k-1; } } @ And the problem of generating all superpieces for up/down slides is equivalent to generating all ideals of a very similar digraph. @= for (j=0;j<=bcount;j++) out[j]=in[j]=-1; for (j=0;j<=bcount;j++) for (k=head[j];k>=ul;k=link[k]) { /* |aboard[k]=j| */ t=aboard[k-colsp]; if (t!=j && t>=0 && (out[t]<0 || aboard[out[t]]!=j)) { olink[k]=out[t], out[t]=k; ilink[k-colsp]=in[j], in[j]=k-colsp; } } @ @= int head[maxsize+1], out[maxsize+1], in[maxsize+1]; /* list heads */ int link[boardsize], olink[boardsize], ilink[boardsize]; /* links */ @ The following subroutine for ideals of a digraph maintains a permutation of the vertices in an array |perm|, with the inverse permutation in |iperm|. Elements |inx[l]| through |inx[l+1]-1| of this array are known to be simultaneously either in or out of the ideal, according as |decision[l]=1| or |decision[l]=0|, based on the decision made on level~|l| of a backtrack tree. The basic invariant relation is that we could obtain an ideal by either excluding or including all elements of index $\ge|inx[l]|$ in |perm|. This property holds when $l=0$ because |inx[0]=0|. To raise the level, we decide first to exclude vertex |perm[inx[l]]|; this also excludes all vertices that lead to it, and we rearrange |perm| in order to bring those elements into their proper place. Afterwards, we decide to include vertex |perm[inx[l]]|; this also includes all vertices that lead from it, in a similar way. Vertex 0 corresponds to an artificial piece that is ``stuck,'' as explained above. If this vertex is excluded from the ideal, we create a list of all board positions for vertices that are included; this will define a superpiece for shifts by |del|. But if the stuck vertex is included in the ideal, we create a list of all board positions for vertices that are excluded; the list in that case will define a superpiece for shifts by |-del|. The list contains |lstart[l]| entries at the beginning of level~|l|. @= void supermove(int,int); /* see below */ void ideals(int del) { register int j,k,l,p,u,v,t; for (j=0;j<=bcount;j++) perm[j]=iperm[j]=j; l=p=0; excl: decision[l]=0, lstart[l]=p; for (j=inx[l],t=j+1;j; if (t>bcount) { @;@+goto incl; } inx[++l]=t;@+goto excl; incl: decision[l]=1, p=lstart[l]; for (j=inx[l],t=j+1;j; if (t>bcount) { @;@+goto backup; } inx[++l]=t;@+goto excl; backup:@+ if (l) { l--; if (decision[l]) goto backup; goto incl; } } @ @= { v=perm[j]; for (k=in[v];k>=0;k=ilink[k]) { u=aboard[k]; if (iperm[u]>=t) { register int uu=perm[t], tt=iperm[u]; perm[t]=u, perm[tt]=uu, iperm[u]=t, iperm[uu]=tt; t++; } } if (decision[0]==1) for (v=head[v];v>=0;v=link[v]) super[p++]=v; } @ @= { u=perm[j]; for (k=out[u];k>=0;k=olink[k]) { v=aboard[k]; if (iperm[v]>=t) { register int vv=perm[t], tt=iperm[v]; perm[t]=v, perm[tt]=vv, iperm[v]=t, iperm[vv]=tt; t++; } } if (decision[0]==0) for (u=head[u];u>=0;u=link[u]) super[p++]=u; } @ @= int perm[maxsize+1], iperm[maxsize+1]; /* basic permutation and its inverse */ char decision[maxsize]; /* decisions */ int inx[maxsize], lstart[maxsize]; /* backup values at decision points */ int super[maxsize]; /* offsets for the current superpiece */ @ @= if (p) { super[p]=0; /* sentinel at end of the superpiece */ if (decision[0]==0) supermove(del,del); else supermove(-del,-del); } @ The |supermove| routine is like |move|, but it uses the superpiece defined in |super| instead of using block~|k|. @= void supermove(int del, int delo) { register int j,s,t; for (j=0;super[j];j++) { /* we remove the superpiece */ board[super[j]]=0; } for (j=0;super[j];j++) { /* we test if it fits in new position */ if (board[del+super[j]]) goto illegal; } for (j=0;super[j];j++) { /* if so, we move it */ board[del+super[j]]=aboard[super[j]]; } if (hashin(style==5) || style==4) @@; else { for (j=0;super[j];j++) { /* remove the shifted superpiece */ board[del+super[j]]=0; } illegal: for (j=0;super[j];j++) { /* replace the unshifted superpiece */ board[super[j]]=aboard[super[j]]; } } } @ After we've moved a superpiece once, the digraph changes and so do the ideals. But that's OK; the |supermove| routine checks that we aren't blocked at any step of the way. @= { for (j=0;super[j];j++) { /* remove the shifted superpiece */ board[del+super[j]]=0; } for (j=0;super[j];j++) { /* replace the unshifted superpiece */ board[super[j]]=aboard[super[j]]; } if (style==4) supermove(del+delo,delo); else for (j=0;j<4;j++) if (delta[j]!=-delo) supermove(del+delta[j],delta[j]); } @ The program now comes to a glorious conclusion as we put the remaining pieces of code together. @= { @; @; ideals(colsp); head[0]=lr+1; /* I apologize for this tricky optimization */ @; ideals(1); } @* Index.