/********************************************************************* trecram.c: tile a rectangle with a given polyomino. This is the ram version, when you have enough ram to solve the problem. Trecdisk.c consumes less ram, but more disk. Copyright (c) Karl Dahlke, 2001. eklhad@home.com http://www.eklhad.net This software, and the patterns it generates, may be freely distributed, electronically or on paper, to anyone, in whole or in part, provided this notice is included. The author reserves all rights regarding the application of these patterns to commercial products such as recreational puzzles. The polyomino, and other options for the running program, are specified in the config file. Thus the config file is the only argument. You can pass a bitmap as an option to the program, but that is only for debugging/tuning. Here is an overview of the algorithm. Consider a 5×2 piece such as f860. If there is a rectangular tiling based on this piece, break it at row 50 (i.e. between rows 50 and 51). Course we don't want to cut any pieces in half, so there are some rules. If a piece extends farther down into the lower half than the upper, include it in the lower half. That settles things if our gun is oriented vertically. If the piees exactly straddles the border, and the heavier end, as measured by the number of squares, or perhaps its center of mass, hangs down, include the piece in the lower section. Now the break is implemented, and gives the same pattern whether approached from below or above. This pattern is stored in a node. The depth of the node is the number of complete rows before the break is evident. In our case the depth may be 50, 49, or 48. Not 47, since a piece that extends 3 rows down would be included in the lower section. In general the depth could be flush with the breakline, or (at worst) pieceLength/2 rows below. In rare cases the depth could be above the breakLine. If the pieceLength is at least 4, and all pieces hang below, they could extend up across the breakLine and completely cover the next row, while some extend into the row after that. As I say, this is rare, but we must consider it. The pattern gap is the distance between the depth and the highest piece. Since the depth is no more than pieceLength/2 from the breakLine, the gap is no more than pieceLength/2*2, which basically rounds pieceLength down to the nearest even number. Each column of a pattern is stored in a bitmap, designating the squares that are occupied, as the pattern is viewed from one side or the other. We only consider pieces that span 9 squares, so the gap is no more than 8, and the bits can always be stored in a byte. We first generate the nodes at depth 1, then 2, then 3, and so on, always looking for a node that exactly complements a previously generated node. This assumes we remember each node we generate, which is why you really need lots of memory, or virtual memory, to run this program. Imagine a long array of nodes, initially seeded with the node of all zeros, the floor of the rectangle. New nodes are appended to this array as they are generated. Set curDepth = 0 to start. Repeat the following procedure for higher and higher values of curDepth. By assumption, the array contains nodes at depth curDepth. These were generated by expanding nodes at earlier depths. Start at the beginning of the array and expand each curDepth node in turn. This expansion may add more nodes to the end of the array, and some of these nodes may be at the same depth, curDepth, but we'll run into them as we move through the array, and when we're done, all nodes at depth curDepth will be expanded. What does it mean to expand a node? Since we only remember the pattern, we don't really know where the breakline was that lead to this pattern, nor can we reconstruct this information, since we don't know the orientations of the pieces that built the pattern when the break was made. But we know the breakLine that made this node was no more than pieceLength/2 above curDepth. Any higher and the depth of the node would be greater. We're interested in generating a new node from this one. We can definitely accomplish this as follows. Increment the maximal breakLine, tile all squares up to the new breakLine, and partition the pieces, according to the new breakLine, to produce a new pattern at a possibly higher depth. We want to generate all possible nodes, so we run an exhaustive search, a push and pop algorithm. Start with breakLine 1 greater than curDepth + pieceLength/2. advance: Push the stack, ready to place another piece. Consider all the empty squares in the first row that have pieces filled in to the west. If there are no empty squares, consider the next row, on up through breakLine rows. If there are no empty squares in the first breakLine rows, goto complete. Assuming there are empty squares to populate, select the best empty square, probably the one with the fewest viable orientations. next: Try the next orientation of the polyomino in this location. If there are no valid orientations remaining, goto backup. Place the piece on the board. Find the lowest breakline that will include this piece. After all, if we don't include any new pieces, we haven't made a new node. If this new breakline is less than the previous value of breakLine, downgrade it. goto advance. backup: Pop the stack - we are now looking at the previous piece placed on the board. If the stack is empty, return, this node has been expanded. Take the piece off the board. Resurrect the old value of breakLine. goto next. complete: Break the board at breakLine. Compute the depth of this new node; call it newDepth. If(we've seen this node before) { if(newDepth is less than the preestablished depth for this node) { Mark the node with this (lower) depth. If the lower depth is curDepth, move the node to the end of the array, so we can process it in this pass. } goto backup. } Place the new node on the end of the array. Compute the complement of the node and see if we have generated it before. If we have { We have tiled a rectangle. Compute the size of this rectangle. If it's bettern than our best so far, crank out the new tiled rectangle and remember it as our best. } goto backup. Finally the depth limit is reached and the program stops. *********************************************************************/ #ifdef MSDOS @program must be compiled under Windows or Unix #endif #include #include #include #include #include #include #ifndef _WIN32 #include #else #include #endif #include #ifndef O_BINARY #define O_BINARY 0 #endif #ifdef _WIN32 #define inline #endif extern int errno; /* debugging modes for this program */ #define PERFORMCHECK 0x1 #define ORIENTCHECK 0x2 #define NODECHECK 0x4 #define SOLVECHECK 0x8 #define LOOKALLCHECK 0x10 static int checkBits = 0; /********************************************************************* Useful typedefs. Often the Unix header files define ushort for you - but the Windows headers don't. *********************************************************************/ #ifdef _WIN32 typedef unsigned short ushort; typedef unsigned long ulong; #endif typedef unsigned char uchar; typedef ushort shapebits; typedef uchar bool; #define true 1 #define false 0 /* short highbit macros */ #define HIGHBIT 0x8000 #define isHighbit(word) ((short)(word) < 0) #define isNotHighbit(word) ((short)(word) >= 0) /********************************************************************* This program considers polyominoes that fit into a 16×16 grid. This fact is hardcoded in several ways. In particular, the bitmap image of a piece is stored in shorts, one short per row. Also, each bitmap has no more than 16 shorts. In reality the diameter is limited to 9, because the patterns that are stored in each node are represented by byte arrays. A piece of diameter 9 can only extend 8 up from its anchoring square, so we can get away with bytes. If we ever want to analyze larger shapes, a lot of code will have to change. *********************************************************************/ #define REPDIAMETER 16 /* represent pieces this large */ #define ANADIAMETER 9 /* analyze pieces this large */ #define NSQ 80 /* number of squares in largest polyomino */ #define SETSIZE 10 /* number of pieces in the set */ #define BOARDWIDTH 256 /********************************************************************* Useful shape manipulation routines. Rotate and reflect a polyominoe in position. *********************************************************************/ static void clockwise(shapebits *base) { int i, j; int min_x = REPDIAMETER-1, min_y = REPDIAMETER-1; bool board[REPDIAMETER][REPDIAMETER]; memset(board, false, sizeof(board)); for(i=0; i= w, and assume we are looking for a solution with n rows. I can break the rectangle at any point. That is, I choose any breakline b. this produces a bottom and top "half" of the rectangle. Actually I'll call them left and right halves. Each piece along the breakline hangs left or right, according to its center of mass, and that determines the split. The number of complete rows in the left half is l, and the number of complete rows in the right half is r. Note that l+r+h > n, and l+r < n. If l is at least b, all the pieces that straddle the breakline hang left. How else could all the rows, up to the breakline, be complete? In fact l could exceed b, as described earlier. Of course such a node was generated by some other node with depth less than the breakline. Numbers are a bit easier to understand than variables, so suppose we are in the midst of expanding, or about to expand, the nodes at depth 26. All nodes at depth <= 25 have been expanded, and they and their expansions crossmatched. All nodes at depth 26 have been generated and crossmatched, except those that are produced by expanding some other node at depth 26. This can only happen if the breakline is at least 26+(w+1)/2. Lower breaklines may indeed produce nodes at depth 26, or even higher, but they've been generated by expanding a node at an earlier depth, hence they're in our database. Consider solutions with n = 52 + w - 1 rows. Set the breakline b at n/2 = 26 + (w-1)/2. If l < 26, we've already got the node in the database. If l >= 26, the breakline is strictly less than 26 + (w+1)/2, so that node has been generated. Take the case where n is even, hence w is odd. When viewed from the right edge, the breakLine has the same bound, hence we can make the same conclusions about r. We've seen both nodes before, so this solution has already been discovered. If we want a solution with exactly 52+w rows, the breakLine, when viewed from the right, is 26+(w+1)/2. If the right pattern hasn't been seen yet, it comes from a node at depth 26, adding a few pieces oriented parallel with the breakLine. We need to expand the nodes at depth 26, and crossmatch the results, but we don't need to store the results. A solution of 52+w always matches a newly generated node with a preexisting node. Now let n be odd, whence w is even. All solutions up to order n-1 have been discovered, using the reasoning in the last paragraph. Returning to n, set the breakLine at n/2, whence the left node has been generated. If we haven't found the solution, r is at least 26. Now r could be generated from a node at depth 26, not 27, so indeed we must expand nodes at depth 26, but we don't have to store the results. There's another criterion for generate-but-don't-store. If twice curDepth + pattern gap exceeds our best height, then the complementary node, if it exists, is below curDepth, and has already been generated. In this program, bestRow represents n, the largest solution we are interested in. If w is odd, set stopgap = w. If 2*curDepth+stopgap exceeds bestRow, we can stop, and if it equals bestRow, we can generate nodes without storing them. When w is even, set stopgap = w - 1. If bestRow is belo 2*curDepth + stopgap, we can stop, and equality means we can generate nodes without storing them. Here is an interesting corrilary. If we are still expanding nodes at 26, we must be looking for solutions of 52+stopgap or higher. Earlier solutions would have been found. Note that stopgap is odd. Set the breakline at n/2, at least 26 + stopgap/2. Remember that l and r are no more than h/2 from the breakline. Thus we can "forget" any nodes below 26 + stopgap/2 - h/2. This saves space in the cache, and we won't miss a tiling. However, we may reintroduce a node at a higher depth that appeared at an earlier depth, simply because we didn't find it. This wastes disk space and cpu cycles, as we will eventually re-analyze that node, but it does keep the cache small - entirely in memory - and that's probably worth it. *********************************************************************/ static int stopgap, forgetgap; #define stopsearch (2*curDepth + stopgap > bestRow) #define stopstore(x) (2*curDepth + stopgap == bestRow || curDepth + x.depth + x.gap > bestRow) /********************************************************************* A simple routine calculates bestRow, as described above. Clearly bestRow times the current width must be divisible by the area of the polyomino, and the resulting order must lie within the bound bestOrder. We may also have constraints on the dimensions and/or the order. For instance, we often know the order is even, hence ordFactor = 2. This will disallow a bestRow that would produce an odd order, so we decrement bestRow and try again. It is possible to skip a few rows in your search, and find a rectangle whose height is less than its width. Consider f8e0e0, a shape with order 270. If we march straight through, we'll find the answer at width = 54. But after ruling out 1 through 44, we know something has to be divisible by 11, so why not jump straight to 55? The program thinks it is looking for a 55×h rectangle, where h is at least 55, but it still looks for solutions all along the way, and sure enough, it stumbles on the one at h = 54. Then it sets bestRow = 53 and makes sure there are none better, with width 55. Now you didn't check 45×66, but that solution, if it exists, is no better than 55×54. And 46×66 is even worse, and so on. So you've found the order of the piece - 270. Note that you can't run this program with width 55 and order 270. Then it *knows* your width will be higher than your height, and it stops. But if you tell it you are looking for something bigger, it will run, checking all the way, and find the smaller rectangle at h = 54. *********************************************************************/ static int nsq; /* number of squares in the polyomino */ static int curWidth; /* current width of rectangle being tiled */ static int curWidth1; /* curWidth + 1 */ static int curDepth; /* depth of nodes being expanded */ static int reachup; /* greatest reach of node so far */ static int bestOrder; /* what is the largest rectangle we are interested in? */ static long ordFactor; /* order must be a multiple of this */ static long dimFactor; /* each dimension must be a multiple of this */ /* rows in the biggest rectangle circumscribed by the above criteria */ static int bestRow, leastRow; static bool noincrease; static void setBestRow(void) { int quotient = nsq * ordFactor; bestRow = bestOrder*nsq/curWidth; do { if(bestRow%dimFactor) continue; if(((long)bestRow*curWidth) % quotient) continue; break; } while(--bestRow); leastRow = 2*curDepth + stopgap; if(curWidth > leastRow) leastRow = curWidth; do { if(leastRow%dimFactor) continue; if(((long)leastRow*curWidth) % quotient) continue; break; } while(++leastRow); } /* setBestRow */ /********************************************************************* In order to tile a rectangle with a given polyominoe, we "compile" said polyominoe for efficiency. This entails finding all the unique orientations of the piece (up to 8), and writing down a bitmap for each one. We also establish the border of the piece. This program assumes that a piece placed on the floor can never comspire with its neighbors to trap a hole below. Such a hole would be smaller than the polyomino, hence unfillable. In practice you have to prove this for each polyomino, but only the most pathological shapes fail this test. All the ones we are interested seem to follow this "hole" rule. *********************************************************************/ struct ORIENT { /* describe an orientation */ shapebits pattern[REPDIAMETER]; shapebits under[REPDIAMETER]; char maxUnder; char h, w; /* height and width */ char breakLine; /* the row with more than half the piece below it */ bool ambig; /* ambiguous indicator */ uchar pno; /* piece number */ uchar ono; /* orientation number */ bool thick; short x, y; /* offset of bottom left square */ }; #ifdef MANYORIENTS #define O_MAX 96 #define clearOrientBits(olist) (olist[0] = olist[1] = olist[2] = 0) #define copyOrientBits(l1, l2) (l1[0] = l2[0], l1[1] = l2[1], l1[2] = l2[2]) #define testOrientBit(o, bit) (o[(bit)>>5] & (1<<((bit)&0x1f))) #define setOrientBit(o, bit) (o[(bit)>>5] |= (1<<((bit)&0x1f))) #else #define O_MAX 32 #define clearOrientBits(olist) (*olist = 0) #define copyOrientBits(l1, l2) (*l1 = *l2) #define testOrientBit(o, bit)((*o)&(1<<(bit))) #define setOrientBit(o, bit)((*o)|=(1<<(bit))) #endif static struct ORIENT o_leftlist[O_MAX]; static struct ORIENT o_rightlist[O_MAX]; static struct ORIENT o_midlist[O_MAX]; static struct ORIENT o_l1list[O_MAX]; static struct ORIENT o_r1list[O_MAX]; static struct ORIENT o_l2list[O_MAX]; static struct ORIENT o_r2list[O_MAX]; static const struct ORIENT *o_whichlist[] = { o_leftlist, o_rightlist, o_midlist, o_l1list, o_r1list, o_l2list, o_r2list, }; static int o_sizes[7]; static int o_max; /* number of orientations */ static bool isconvex = true; static bool carlike = false; static shapebits anytab = 0xffff; static int pieceMinDimension, pieceMaxDimension, pieceMinMax, pieceLocalMax; static int setSize; /* for sets of polyominoes */ static int goodEnough; /* place a piece with this many orientations or less. */ static bool cbflag; /* checkerboard flag */ static const shapebits revNibble[] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}; static inline shapebits reverseBits(shapebits v) { return revNibble[v>>12] | (revNibble[(v>>8)&0xf]<<4) | (revNibble[(v>>4)&0xf]<<8) | (revNibble[v&0xf]<<12); } /* reverseBits */ static inline uchar reverseByte(uchar v) { return revNibble[v>>4] | (revNibble[v&0xf]<<4); } /* reverseByte */ /* reflect a compiled piece, left to right */ static void reflectCompiledPiece(void) { int i, j; shapebits v; bool change; struct ORIENT *o = o_leftlist + o_max; struct ORIENT *p = o_rightlist + o_max; static const uchar href[8] = {4,7,6,5,0,3,2,1}; if(o->pattern[0]&1) anytab &= o->pattern[0]; o->thick = false; if(o->x < o->w-1 && o->pattern[o->x+1] & (1<<(o->y))) o->thick = true; p->h = o->h, p->w = o->w, p->ambig = o->ambig; p->thick = o->thick; p->pno = o->pno; p->ono = href[o->ono]; p->x = o->w-1 - o->x; p->y = o->y, p->breakLine = o->breakLine; o->maxUnder = 0; for(i=0; iw; ++i) { for(v=1, j=0; !(v&o->pattern[i]); v<<=1, ++j) ; o->under[i] = v-1; if(j > o->maxUnder) o->maxUnder = j; } /* now we worm our way around, in case the shape isn't convex. * This is real inefficient, but who cares. */ if(o->maxUnder) { change = true; while(change) { change = false; for(i=0; iw; ++i) { for(j=0, v=1; jh; ++j, v<<=1) { if(o->under[i]&v) continue; if(o->pattern[i]&v) continue; if(i && o->under[i-1]&v || i < o->w-1 && o->under[i+1]&v) { o->under[i] |= v; if(j > o->maxUnder) o->maxUnder = j; change = true; } } } } } p->maxUnder = o->maxUnder; for(i=0; iw; ++i) { p->pattern[o->w-1-i] = o->pattern[i]; p->under[o->w-1-i] = o->under[i]; } ++o_max; } /* reflectCompiledPiece */ /* Rotation established, record the shape. */ /* Pass the width and height, just so we don't have to recompute it. */ static void compilePiece(const shapebits *new, int bx, int by, int ono) { struct ORIENT *o = o_leftlist + o_max; struct ORIENT *q; int i, j, k; shapebits mask; if(o_max == O_MAX) bailout("too many orientations, limit %d", O_MAX); /* Let's do a convex check first */ for(i=0; i>=1) { if(mask&1) { if(k == 1) continue; if(++k == 3) { isconvex = false; break; } } else if(k == 1) k = 2; } } if(bx <= by && isHighbit(new[0]) && isHighbit(new[by-1]) && isNotHighbit(new[0]<<(bx-1)) && isNotHighbit(new[by-1]<<(bx-1))) carlike = true; for(j=0; jh = bx; o->w = by; o->ambig = false; o->x = j; o->y = 0; o->pno = setSize; o->ono = ono; for(j=0; jpattern[j] = reverseBits(new[j]); /* compute the break level */ o->breakLine = (o->h-1)/2; if(!(o->h&1)) { /* even, requires further refinement */ /* see which half is "heavier" */ long bottom = 0, top = 0; int shift; for(j=0; j>=1) { if(!(v&mask)) continue; k = shift - o->breakLine; if(k <= 0) --k; if(k < 0) bottom += k*k; else top += k*k; } } if(bottom == top) o->ambig = true; if(bottom < top) ++o->breakLine; } /* even straddle */ reflectCompiledPiece(); /* Find all the other lower left corners. */ for(i=0; iw; ++i) { if(i == o->x) continue; /* we already did this one */ for(j=0; jh; ++j) { mask = 1<pattern[i]&mask) break; } if(j == o->h) bailout("j bit not found at column %d", i); if(i && o->pattern[i-1]&mask) continue; /* we just found another lower left corner */ if(o_max == O_MAX) bailout("too many orientations, limit %d", O_MAX); q = o_leftlist + o_max; *q = *o; /* structure copy */ q->x = i; q->y = j; q->breakLine -= j; reflectCompiledPiece(); } } /* compilePiece */ /* find all the orientations of a piece */ static void compileRotations(shapebits *new, int bx, int by) { int swap; /* to swap bx and by */ int i, j, k; int npat = 0; shapebits patterns[8][REPDIAMETER]; static const uchar make_ono[8] = {7,4,5,6,1,2,3,0}; for(j=0; j<2; ++j) { /* 2 reflections */ for(i=0; i<4; ++i) { /* 4 rotations */ if(by > pieceMaxDimension) pieceMaxDimension = by; if(by > pieceLocalMax) pieceLocalMax = by; if(by < pieceMinDimension) pieceMinDimension = by; for(k=0; ky < b->y) continue; if(a->y == b->y && a->w - a->x <= b->w - b->x) continue; swap = *a, *a = *b, *b = swap; a = o_rightlist + i; b = a+1; swap = *a, *a = *b, *b = swap; change = true; } } for(i=0; iono = 1<ono; a = o_rightlist + i; a->ono = 1<ono; } o_sizes[0] = o_sizes[1] = o_max; j = 0; for(i=0; ix) { y = a->y; s = a->pattern[a->x-1]; t = a->pattern[a->x]; ++y; s >>= y; t >>= y; while(t&1) { if(s&1) goto hangingleft; s>>=1, t>>=1; } } s = a->pattern[a->x] >> a->y; t = (1<x < a->w-1 && a->pattern[a->x+1] & (1<<(a->y))) continue; b = o_midlist + j; *b = *a; ++j; } o_sizes[2] = j; j = 0; for(i=0; ipattern[a->x]>>a->y) & 2) continue; b = o_l2list + j; *b = *a; a = o_rightlist + i; b = o_r2list + j; *b = *a; ++j; } o_sizes[5] = o_sizes[6] = j; } /* sortOrientations */ /********************************************************************* Here is the structure for the node. *********************************************************************/ struct NODE { long parent; /* where this node came from */ long hash; /* has value of this pattern */ short depth; /* the depth of this node */ char gap; /* the gap of this pattern */ bool dead; uchar pattern[BOARDWIDTH]; }; static int nodeSize; /* adjusted for the actual width */ static long nodesDisk; /* nodes stored on disk */ static long nodesPending; /* nodes to process */ static long nodesCache; /* nodes stored in cache */ static int hwm; /* high water mark on the cache */ static long mon_idx; /* for markOldNodes() */ static long *workList; /* the list of nodes to expand */ static int workEnd, workAlloc; /********************************************************************* When a node is generated, we want to determine, quickly, whether we have seen it before. Or whether we have seen its complement. A linear search is hardly appropriate. We use a hash lookup. This function computes the hash value for a pattern. By selecting a cannonical direction to scan the pattern, the hash value is the same for a pattern and its reflection. Thus computeHash() may reverse your pattern. As always, the hash has about 10% slop. If we allow 40 meganodes, we might have an array of 45 million hash indexes. *********************************************************************/ static int megaNodes; /* millions of nodes that can be cached */ static int startMega; /* specified by the config file */ static long maxNodes; /* megaNodes times a million */ static long slopNodes; /* maxNodes plus some slop, for the randomness of the hash */ static long *hashIdx; /* array of hashed indexes */ typedef uchar hashconfirm; static hashconfirm *hashVal; /* array of partial hash values */ static bool reversableHash = true; static long computeHash(uchar *p) { int j, k, direction; ulong hash = 0; shapebits v; uchar swap; ulong prime = 2147483629; ulong m_factor = (ulong)0x80000000 - prime; direction = 1; if(reversableHash) { k = curWidth-1; for(j=0; j+j>15)*m_factor); hash += v; if(hash >= prime) hash -= prime; } if(hash >= prime) bailout("hash value too large", 0); /* 0 hash value is not allowed */ if(!hash) hash = 1; return (long)hash; } /* computeHash */ /********************************************************************* In Linux, the best operating system in the world, disk and memory are almost indistinguishable. Disk blocks are cached using a first-rate algorithm, and if you've got a swap partition active, memory is swapped out to disk as needed. I store nodes on disk, and a cache in memory, but Linux is smart enough to interchange these resources as appropriate. All I need do is minimize the number of active blocks, be they disk blocks or memory blocks, at any given time. I support up to 26 data files, each 2 gig - that's 52 gig of data. This can hold as many as a billion nodes. *********************************************************************/ static int fd[26] = /* the file descriptors */ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,}; static char filename[] = "dotile/data-x"; static long nodesInFile; static int restart = 0; /* depth when restarting the program */ static int restartParent; static void recache(void); static void readNode(long idx, struct NODE *buf) ; static void initFiles(void) { int flags; int i, j; static char *xptr; if(!xptr) xptr = strchr(filename, 'x'); if(workList) free(workList); workAlloc = 60; workList = emalloc(4*workAlloc); workEnd = 0; nodeSize = sizeof(struct NODE) - BOARDWIDTH + curWidth; nodeSize = (nodeSize + 3) & ~3; nodesInFile = 0x7fff0000 / nodeSize; megaNodes = startMega; maxNodes = megaNodes * 0x100000; slopNodes = maxNodes / 8 * 9; reachup = 0; if(restart) { /* resume program */ long l; struct NODE buf; int cutoff = restart + forgetgap; nodesDisk = 0; for(i=0; i<26; ++i) { flags = O_RDWR|O_BINARY; *xptr = 'a' + i; fd[i] = open(filename, flags, 0666); if(fd[i] < 0) bailout("cannot reopen data file, errno %d", errno); l = lseek(fd[i], 0, 2); if(l%nodeSize) bailout("data file has bad length %ld", l); nodesDisk += l/nodeSize; } /* loop over files */ readNode(nodesDisk-1, &buf); restartParent = buf.parent; if(!restartParent) bailout("restartParent is 0", 0); readNode(restartParent, &buf); if(buf.depth != restart) { if(buf.depth != restart-1) bailout("last depth was %d", buf.depth); printf("last depth was %d\n", buf.depth); restartParent = 0; } mon_idx = 0; nodesPending = 0; for(j=1; j= restartParent) ++nodesPending; if(buf.depth > restart) ++nodesPending; if(buf.depth > cutoff && !mon_idx) mon_idx = j; if(buf.depth + buf.gap > reachup) reachup = buf.depth + buf.gap; } printf("Restart with %d nodes, %d pending\n", nodesDisk, nodesPending); curDepth = restart; recache(); return; } /* resume program */ if(hashIdx && megaNodes > startMega) { free(hashIdx); free(hashVal); hashIdx = 0; hashVal = 0; } if(!hashIdx) hashIdx = emalloc(slopNodes * sizeof(long)); if(!hashVal) hashVal = emalloc(slopNodes *sizeof(hashconfirm)); memset(hashIdx, 0, slopNodes*sizeof(long)); nodesCache = 0; hwm = 0; nodesDisk = 1; /* the initial node of all zeros is at location 0 */ mon_idx = 1; nodesPending = 1; curDepth = 0; for(i=0; i<26; ++i) { if(fd[i] > 0) close(fd[i]); flags = O_CREAT|O_TRUNC|O_RDWR|O_BINARY; *xptr = 'a' + i; fd[i] = open(filename, flags, 0666); if(fd[i] < 0) bailout("cannot create data file, errno %d", errno); } /* loop over files */ } /* initFiles */ /********************************************************************* Read the config file. This file is line oriented. Everything from # to end-of-line is ignored (comment). Each of the first seven lines must be present, and syntactically correct. The first line gives the polyomino, using the hex format described in even.html. We also allow a + to set the ninth bit. Thus ff+fcfc is a long version of Oklahoma, with a row of 9 squares and two rows of 6 squares. You can specify a set of polyominoes on the first line, using / as delimiter. Thus 70d0/e070 describes a pair of hexominoes that have order 130, as a set, even though neither tiles a rectangle on its own. At present, all the shapes in a set must have the same number of squares. You can add a ~ modifier to the end of a shape. This prohibits certain orientations when the shape is on the floor. We rotate things to prohibit the corresponding orientations against the left and right walls. ~n prohibits the normal orientation, as the piece is written. ~u prohibits the upsidedown orientation. ~l prohibits the left orientation, counterclocwise turn. ~r prohibits the right orientation, clocwise turn. Thus you might write the earlier set as 70d0~u/80f020~nu Then again, you might not, because the extra code needed to make these checks often makes the program run slower. Often, but not always. This feature isn't too helpful when an orientation would be ruled out anyways, by the next piece. However, there are times when the orientation seems fine, even after several more pieces have been placed. In the set f08080~u/c06030~nulr You'd think stairs could be placed on the floor. But you always have to slide more stairs beneath those stairs, and that continues forever, so we disallow any stairs on the floor, in any orientation. This makes a *big* difference. Instead of wasting time on all those patterns with stairs propagating up the left and right walls, the program soon finds the order 363 solution, 33×66. The second line sets the initial width. We search for a rectangle with this width, then increase the width, until we find a solution. This line can also be used to resume the program after a power failure (or whatever). If you were analyzing rectangles of width 40, and the last thing you saw was @27, put 40@27 in the second line of the config file. This resumes the program at width 40, depth 27, using the files that were present when the computer crashed (hopefully they weren't corrupted). The program starts at the very same node that was being analyzed before. The third line is a bound on the order. Don't look for larger solutions than this. If this is zero, the program doesn't look for rectangles at all. Instead, it tiles a strip of the given width up the left wall, without worrying about the stuff hanging off to the right. I call this a ragged strip, as the right edge is ragged, and ill-defined. If you can't tile such a strip, you certainly can't tile a rectangle. Many shapes are ruled out by this technique. For instance, fcf8c0 tiles a quadrant, but will not tile a finite ragged strip of width 12. The fourth line determines the number of nodes, in millions of nodes, that will be maintained in cache. You can specify up to 100 million nodes, but that's probably not a good idea. Forty million is comfortable for a quarter gig of ram. Basically, multiply the number by 5 meg for ram consumed. If the cache overflows, this program increases the cache by 12 million and tries again. You only want to rely on this racaching as a last resort. Perhaps you have invested several days of cycles, and being almost done with that width, we can expand and finish it off. But it's not efficient, especialy if you use it at the outset. If you start small and grow, you'll be forgetting past nodes all along the way, because the cache will always be (almost) full. And you'll be rediscovering and reprocessing these nodes again and again. If you think you'll need a cache of 50 million, and you know your disk starts to thrash at 40 million, set this value to 40, and put up with the disk thrashing near the end. The fifth line tells the program how many rows to tile. Normally the program tiles up to the breakline, and then calls it a node. But there's no sense wasting cache and disk space on a dead-end node. So sometimes we want to tile beyond the breakline, to make sure the node is valid. Then again, it takes extra time to tile more rows on top of each node. You'll have to trade space against time. Set lookahead high to conserve nodes on disk and in cache. Set lookahead = 0 for fast performance on small rectangles. I find that lookahead = 2 works well, and that's what I usually use, unless I'm trying to conserve nodes for very large rectangles. Lookahead values range from 0 to 9. 9 is always well beyond the breakline - 0 is below the breakline. We still tile up to the breakline if lookahead is less. Note that the program does some lookahead even if this value is zero. We do some spot checks to see if any pieces are forced, or if some squares can't be tiled at all. This spotchecking is separate from the lookahead parameter, which forces the program to tile additional rows, in their entirety. The sixth line is a factor on the order. Set this to 2 to force an even order. We often know the order is divisible by something. The seventh line is a factor on the dimension. Boundary conditions often force both diminsions to be divisible by something. Subsequent lines, optional, define aggregate groups of pieces that can sit on the floor. This helps jump-start the program when the board is wide and border pieces naturally group together into various complexes. Sorry to be inconsistent, but this time the low order bits are significant. You might specify the polyomino as f8f880, using the high order bits, but a group of two such pieces standing face to face on the floor is 1f1f01011f1f. You could fill in the middle: 1f3f3f3f1f1f, but that actually slows things down a lot, because each complex can now point left or write, with no lookahead checks to see if that makes any sense. So you multiply the combinations by 2^n, to be sorted out later on. Better to leave the middle piece out. You need not specify the reflection of any complex; this program reflects all patterns. Note that the nodes produced from floor patterns may have gaps that are larger than normal. This happens when tall complexes are placed next to short ones. Remember that a gap, the difference between the high and low complexes, must never exceed 8, as patterns are stored in bytes. Right now that isn't an issue, since the entire floor complex is represented in bytes, but I may change this to shorts, and if I do, you have to observe the 8-square difference, or else I'll enforce it in software. Another type of pattern line is written x=z which means a gap of width x, with walls of height at least z, is a dead end. You can also write x-y=z, for gaps of width x through y. Of course the program would find this out eventually, as it tried to tile the gap. It is still not clear whether the software needed to check for these gaps pays for itself. It does cut down on nodes, and that can help. Remember that the burden of proof is on you. If you write 5=3, then you must prove that a gap of width 5 and height 3 is unfillable. Keep in mind, there may be pieces above this gap, or even hanging down into this gap from above. The software simply looks for an empty U, of the specified width and height, without worrying about what is next to, above, or even inside this empty U, so make sure it's really a dead end under all these conditions. It usually is - I'm just trying to be clear about what is going on here. A line with a single hyphen on it marks the end of data and the beginning of comments about this shape. Perhaps a proof as to why the order or the dimension are divisible by certain numbers, or the best solution so far, or the dimensions we have already explored. Sample config file: e0f080~u # a row of 3, then a row of 4, then a single square 30 # start at 30 rows 210 # don't look for rectangles with more than 210 pieces 2 # 2 million nodes in cache 0 # no lookahead 2 # checkerboard argument implies an even order 2 # pairs of pieces on the floor consume 4|6 squares 070f0f0f08 070f03030307 - This is a performance regression test. It takes a while to determine that this shape has order 210, then 192, then 180, but not too long, as I am somewhat impatient. This doesn't test how well the program does with tens of millions of nodes, when disk thrashing becomes an issue. It merely tests the performance of the tileing algorithm. This test was done on an 800mhz processor with 256mb ram. Best time = 2m26s (user 2m10s) The floor patterns given above don't make the program run faster or slower, at least not for this shape, but I include them so the regression test exercises this feature. It does prove useful for other shapes, on wider boards. The expected output from the program is as follows. ;e0f080~u ?30 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 @15 @16 @17 @18 @19 @20 @21 @22 @23 @24 @25 *210[30x56] :90731 ?32 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 @15 @16 @17 @18 @19 @20 @21 *192[32x48] :56965 ?34 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 @15 @16 @17 @18 :142320 ?36 @0 @1 @2 @3 @4 @5 @6 @7 @8 @9 @10 @11 @12 @13 @14 @15 %10 @16 %00 %10 @17 %20 *180[36x40] :467197 *********************************************************************/ static int lookahead; /* look ahead this many rows when tiling */ static void showPoly(const shapebits *p) { int i; shapebits x; for(i=0; i>8); x &= 0xff; if(x == 0x80) printf("+"); else if(x) printf("<%02x>", x); } } /* showPoly */ /* for debugging */ static void showPattern(const shapebits *p) { int j; for(j=0; j= 'a') c -= ('a'-'9'-1); return c-'0'; } /* toHex */ static const uchar nibbleCount[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; static bool wallRestrict; static uchar bo_ok[SETSIZE], lo_ok[SETSIZE], ro_ok[SETSIZE]; /* Convert a hex-format representation of a polyomino into its bitmap, */ /* and derive all its rotations. */ static void stringPiece(const char *hexrep) { shapebits mask; const char *s; int i, j; shapebits piece[REPDIAMETER]; bool cbf; int bx, by; char c; uchar bo, lo, ro; int nsqFirst = -1; printf(";%s\n", hexrep); s = hexrep; o_max = 0; pieceMaxDimension = 0, pieceMinDimension = pieceMinMax = NSQ; setSize = 0; cbflag = true; while(*s) { if(setSize >= SETSIZE) bailout("too many pieces in the set, limit %d", SETSIZE); pieceLocalMax = 0; memset(piece, 0, REPDIAMETER*sizeof(shapebits)); nsq = 0; i = 0; mask = 0; while((c = *s) != 0 && c != '/' && c != '~') { if(!isxdigit(c)) bailout("character %c unrecognized, hex digit expected", c); if(!isxdigit(s[1])) bailout("character %c unrecognized, hex digit expected", s[1]); if(i >= REPDIAMETER) bailout("polyomino is too high, limit %d rows", REPDIAMETER); piece[i] = (toHex(c)<<4) | toHex(s[1]); piece[i] <<= 8; s += 2; if(*s == '+') ++s, piece[i] |= 0x80; else if(*s == '{') { ++s; if(!isxdigit(s[0]) || !isxdigit(s[1]) || s[2] != '}') bailout("improper {xx} sequence for the second 8 bits", 0); piece[i] |= toHex(s[0])<<4; piece[i] |= toHex(s[1]); s += 3; } if(!piece[i]) bailout("zero row in polyomino", 0); mask |= piece[i]; nsq += nibbleCount[piece[i]>>12]; nsq += nibbleCount[(piece[i]>>8)&0xf]; nsq += nibbleCount[(piece[i]>>4)&0xf]; nsq += nibbleCount[(piece[i])&0xf]; ++i; } /* loop gathering the rows in this piece */ if(nsqFirst >= 0 && nsq != nsqFirst) bailout("all polyominoes in the set must have the same number of squares", 0); if(nsq > NSQ) bailout("too many squares in the given polyomino, limit %d", NSQ); nsqFirst = nsq; by = i; for(i=0; mask; ++i, mask<<=1) ; bx = i; compileRotations(piece, bx, by); if(pieceLocalMax < pieceMinMax) pieceMinMax = pieceLocalMax; /* see if the checkerboard argument applies */ cbf = false; if(!(nsq&1)) { int total = 0; for(i=0; i 1) carlike = false; if(checkBits&ORIENTCHECK) { struct ORIENT *o = o_leftlist; for(i=0; ipno, o->ono, o->w, o->h, o->x, o->y, o->breakLine); for(j=0; jw; ++j) { printf("%x", o->pattern[j]); if(j < o->w-1) printf("."); } printf("\n"); if(o->maxUnder) { printf("under %d:", o->maxUnder); for(j=0; jw; ++j) { printf("%x", o->under[j]); if(j < o->w-1) printf("."); } printf("\n"); } } printf("setsize %d min %d max %d minmax %d anytab %d\n", setSize, pieceMinDimension, pieceMaxDimension, pieceMinMax, anytab); if(isconvex) puts("convex"); if(carlike) puts("carlike"); } stopgap = (pieceMinDimension&1) ? pieceMinDimension : pieceMinDimension - 1; forgetgap = stopgap/2 - pieceMaxDimension/2 - 1; if(forgetgap >= 0) bailout("forget gap should be negative, not %d", forgetgap); goodEnough = o_max/2; } /* stringPiece */ #define FLOOR_N 50 static shapebits floorShapes[FLOOR_N*2][BOARDWIDTH]; static int floor_n; static char bracket[BOARDWIDTH]; static bool bracket_on; static void readConfig(void) { FILE *f; char line[BOARDWIDTH+10]; int lineno = 0; int i, j; char *s; char c; f = fopen (config, "r"); if(!f) bailout("unable to open, errno %d", errno); while(fgets(line, sizeof(line), f)) { ++lineno; j = strlen(line); if(!j) bailout("line %d, fgets returned an empty string", lineno); --j; s = line + j; if(*s != '\n') bailout("line %d, line is too long", lineno); *s = 0; s = strchr(line, '#'); if(s) *s = 0; for(i=j=0; (c = line[i]) != 0; ++i) if(!isspace(c)) line[j++] = c; line[j] = 0; if(!j) bailout("line %d, no content", lineno); if(!strcmp(line, "-")) { --lineno; break; } /* check for weird characters */ for(s=line; (c = *s) != 0; ++s) { if(isxdigit(c)) continue; if(strchr("+/~nulr", c) && lineno == 1) continue; if(c == '@' && lineno == 2) continue; if(strchr("-=", c) && lineno >= 8) continue; bailout("line %d, invalid character(s)", lineno); } switch(lineno) { case 1: stringPiece(line); if(pieceMaxDimension > ANADIAMETER) bailout("polyomino is too large, limit %d rows or columns", ANADIAMETER); sortOrientations(); break; case 2: curWidth = strtol(line, &s, 10); if((*s && *s != '@') || curWidth < 4 || curWidth > 250) bailout("line %d, expected an initial width between 4 and 250", lineno); if(*s == '@') { ++s; restart = strtol(s, &s, 10); if(*s || restart <= 0 || restart > 1000) bailout("line %d, expected a restart value between 1 and 1000", lineno); } break; case 3: bestOrder = strtol(line, &s, 10); if(*s || bestOrder > 30000) bailout("line %d, expected an order between 4 and 30000", lineno); break; case 4: startMega = strtol(line, &s, 10); if(*s || startMega < 1 || startMega > 400) bailout("line %d, expected a mega-node count between 1 and 400", lineno); break; case 5: lookahead = strtol(line, &s, 10); if(*s || lookahead < 0 || lookahead > 9) bailout("line %d, expected a lookahead value between 0 and 9", lineno); break; case 6: ordFactor = strtol(line, &s, 10); if(*s || ordFactor < 1 || ordFactor > 1000) bailout("line %d, expected a factor between 1 and 1000", lineno); if(cbflag & ordFactor) { printf("checkerboard upgrade from %d to %d\n", ordFactor, ordFactor*2); ordFactor *= 2; } bestOrder -= (bestOrder%ordFactor); break; case 7: dimFactor = strtol(line, &s, 10); if(*s || dimFactor < 1 || dimFactor > 60) bailout("line %d, expected a factor between 1 and 60", lineno); curWidth += dimFactor-1; curWidth -= curWidth%dimFactor; curWidth1 = curWidth + 1; break; default: if(strchr(line, '=')) { i = j = strtol(line, &s, 10); if(*s == '-') j = strtol(s+1, &s, 10); if(i < 1 || i > BOARDWIDTH-4 || j < 1 || j > BOARDWIDTH-4 || j < i || *s != '=' || !isdigit(s[1]) || s[1] == '0' || s[2]) bailout("line %d, expected format is width=limit or width-width=limit", lineno); bracket_on = true; while(i <= j) bracket[i++] = s[1] - '0'; break; } if(floor_n == FLOOR_N) bailout("too many floor patterns, limit %d", FLOOR_N); s = line, i = 0; j = 0; while(*s) { if(!isxdigit(s[0])) bailout("floor patterns must contain only hex digits, %c is unexpected", s[0]); if(!isxdigit(s[1])) bailout("floor patterns must contain only hex digits, %c is unexpected", s[1]); if(i == BOARDWIDTH-1) bailout("floor pattern is too wide, limit %d", BOARDWIDTH-1); floorShapes[floor_n][i] = (toHex(s[0])<<4) | toHex(s[1]); j += nibbleCount[(floorShapes[floor_n][i]>>4)&0xf]; j += nibbleCount[(floorShapes[floor_n][i])&0xf]; ++i, s+=2; } ++floor_n; if(j%nsq) bailout("line %d, this pattern cannot be attained using the given polyomino(s)", lineno); } /* switch on lineno */ } /* reading lines in the config file */ fclose(f); if(!lineno) bailout("file is empty", 0); if(lineno < 7) bailout("file does not contain enough lines of configuration data, 7 lines expected", 0); if(floor_n && bestOrder) { /* add reflections */ j = floor_n; for(i=0; i= 2 && argv[1][0] == '-') { checkBits = strtol(argv[1]+1, 0, 16); ++argv, --argc; } lowEmptySet(); if(argc == 2 && argv[1][0] == '@') { /* polyomino on the command line, quadrant test */ stringPiece(argv[1]+1); quadTest(); } if(argc != 2 || argv[1][0] == '-') bailout("usage: trec config_file", 0); config = argv[1]; readConfig(); config = 0; if(!bestOrder) oenTest(); signal(SIGTERM, catchTerm); signal(SIGINT, catchInt); signal(SIGHUP, SIG_IGN); while(true) { if(curWidth*curWidth > bestOrder*nsq) break; setBestRow(); if(bestRow >= curWidth) { initFiles(); setBestRow(); printf("?%d", curWidth); if(!curDepth) expandFirstNode(); if(nodesPending) { /* we got some nodes off the floor */ do { printf(" @"); if(!restart) markOldNodes(); printf("%d", curDepth); j = nodesCache / (maxNodes/10); if(j != hwm) { hwm = j; printf(" %%%d0", j); } expandNodes(); restart = 0; restartParent = 0; ++curDepth; setBestRow(); /* resets leastRow */ if(stopsearch) break; if(bestRow < curWidth && !(checkBits&LOOKALLCHECK)) break; } while(nodesPending); } printf(" :%ld\n", nodesCache); } restart = 0; restartParent = 0; noincrease = false; curWidth += dimFactor; curWidth1 = curWidth + 1; if(curWidth > BOARDWIDTH-2) bailout("width cannot exceed %d", BOARDWIDTH-2); } return 0; } /* main */ /********************************************************************* Read and write nodes by index. Look up nodes by hash. Insert new nodes if they're not already present. *********************************************************************/ static void readNode(long idx, struct NODE *buf) { int i = idx / nodesInFile; long offset = (idx%nodesInFile) * nodeSize; elseek(fd[i], offset); eread(fd[i], buf, nodeSize); } /* readNode */ static void writeNode(long idx, const struct NODE *buf) { int i = idx / nodesInFile; long offset = (idx%nodesInFile) * nodeSize; elseek(fd[i], offset); ewrite(fd[i], buf, nodeSize); } /* writeNode */ /* Append a node to the pending queue. */ static void appendNode(long idx) { if(workEnd == workAlloc) { workAlloc = workAlloc/2 * 3; workList = erealloc(workList, 4*workAlloc); } workList[workEnd++] = idx; printf("<"); ++nodesPending; } /* appendNode */ /* Recache all the active nodes - either because we are growing the cache, * or because we had to restart the program. */ static void recache(void) { static struct NODE rebuf, redest; /* for recaching */ int cutoff = curDepth + forgetgap; int j; long n, hash, idx; long *hb; hashconfirm huc; char pass; hashIdx = emalloc(slopNodes * sizeof(long)); hashVal = emalloc(slopNodes *sizeof(hashconfirm)); memset(hashIdx, 0, slopNodes*sizeof(long)); nodesCache = 0; hwm = 0; /* Two passes; in case you've ask for a bit more virtual memory than ram. * If you're virtual memory is more than twice your ram, * you're probably in trouble in any case. * We may want to implement the same 2-pass procedure in markOldNodes(). */ for(pass=0; pass<=1; ++pass) { for(j=mon_idx; j= maxNodes) bailout("cannot recache at level %d", megaNodes); nextDisk: ; } /* loop recaching nodes on disk */ } /* two passes, cuts down on disk thrashing */ } /* recache */ /* Look for a node by hash value. */ /* Return true if the node was found. */ static bool findNode( struct NODE *look, bool insert, struct NODE *dest) { long *hb; long n, hash, idx; long empty = -1; int j; hashconfirm huc; hash = computeHash(look->pattern); huc = hash%251; n = hash % slopNodes; hb = hashIdx + n; while(true) { idx = *hb; if(!idx) break; if(idx < 0) { if(empty < 0) empty = n; if(!insert) goto nextnode; idx &= 0x7fffffff; } if(hashVal[n] != huc) goto nextnode; if((idx^hash)&0x70000000) goto nextnode; idx &= 0x0fffffff; readNode(idx, dest); if(dest->hash != hash) goto nextnode; if(memcmp(dest->pattern, look->pattern, curWidth)) goto nextnode; if(insert && look->depth < dest->depth) { dest->depth = look->depth; dest->parent = look->parent; writeNode(idx, dest); /* If we're downgrading this to curDepth, we have to move it * to the head of the pending queue. Otherwise we might * never expand this node. * That's what the workList array is for. * Keep in mind, this doesn't happen very often. * In fact this code probably hasn't been tested at all! * But it compiles. :-) */ if(look->depth == curDepth && idx < look->parent) appendNode(idx); } /* downgrading the depth */ /* We found the node, so you'd think we'd return true here, * and we usually do, however, there is one case, when the program has been * restarted, that we want to return false. * The previous run may have generated the last node, but not crossmatched it. * If we return true we won't be crossmatching it this time either. */ if(restart && insert && idx == nodesDisk-1) return false; return true; nextnode: ++n, ++hb; if(n == slopNodes) n = 0, hb = hashIdx; } if(!insert) return false; j = look->depth + look->gap; if(j > reachup) reachup = j; if(checkBits&NODECHECK) printf("insert %ld\n", n); if(nodesDisk >= 0x10000000) bailout("too many nodes, limit one quarter billion", 0); if(nodesDisk/25 > nodesInFile) bailout("too many nodes for 26 data files on disk", 0); look->hash = hash; writeNode(nodesDisk, look); if(empty >= 0) n = empty; hb = hashIdx + n; *hb = nodesDisk | (hash&0x70000000); hashVal[n] = huc; ++nodesDisk; ++nodesPending; if(++nodesCache >= maxNodes) { /* Cache overflow -- increase the cache */ printf(" ^"); free(hashIdx); free(hashVal); megaNodes += 12; maxNodes = megaNodes * 0x100000; slopNodes = maxNodes / 8 * 9; /* Thanks to virtual memory and swap partitions, the recaching * will probably work. However, if hashIdx approaches the size of your Ram, * Your disk will really start to thrash, * and your performance goes down the toilet! */ recache(); printf("%d", megaNodes); } /* recaching */ j = nodesCache / (maxNodes/10); if(j == 10) j = 9; if(j > hwm) { hwm = j; printf(" %%%d0", j); } return false; } /* findNode */ static void markOldNode(long jdx, long hash) { long *hb; long n, idx; n = hash % slopNodes; hb = hashIdx + n; while(true) { idx = *hb; if(!idx) break; if((idx&0x0fffffff) == jdx) { *hb |= 0x80000000; --nodesCache; return; /* found it */ } ++n, ++hb; if(n == slopNodes) n = 0, hb = hashIdx; } /* Apparently it was already removed from the cache. */ } /* markOldNode */ static void markOldNodes(void) { long idx; static struct NODE buf; int cutoff = curDepth + forgetgap; bool firstBigger = true; if(cutoff < 0) return; for(idx=mon_idx; idx cutoff && firstBigger) { firstBigger = false; mon_idx = idx; } if(buf.depth == cutoff) markOldNode(idx, buf.hash); } /* loop scanning all nodes on disk */ } /* markOldNodes */ /********************************************************************* Expand the node using the algorithm described at the top of this file. A stack of structures tracks the placement of the pieces on the board. *********************************************************************/ struct PLACE { short x, y; /* location of this piece */ char o; /* orientation */ char whichlist; char breakLine; /* before we placed this piece */ char min_y; ulong orients[3]; /* bitmap of viable orientations */ short choices; }; static struct PLACE placeTry[BOARDWIDTH]; /* find the lowest empty bit in a short */ static char lowEmpty[65536]; static void lowEmptySet(void) { ushort mask; int j, k; for(j=0; j<65536; ++j) { mask = j; for(k=0; mask&1; ++k, mask>>=1) ; lowEmpty[j] = k; } } /* lowEmptySet */ /* This makes up for the fact that Windows doesn't have a ^z suspend feature. */ static char inPause = 0, inTerm = 0; static void catchInt(int n) { inPause = 1; if(!isatty(0)) exit(0); if(n != SIGINT) exit(0); /* should never happen */ printf(" pause"); } /* catchInt */ static void catchTerm(int n) { inTerm = 1; } /* special code to keep certain pieces and/or orientations away from the wall */ static bool wallTest(const struct ORIENT *o, int x0, int dy) { if(!curDepth && !dy && !(o->ono&bo_ok[o->pno])) goto fail; if(x0 == 1 && !(o->ono&lo_ok[o->pno])) goto fail; if(x0+o->w == curWidth1 && !(o->ono&ro_ok[o->pno])) goto fail; return true; fail: return false; } /* wallTest */ static bool inletTest(const shapebits *b) { int lastlev = 50, thislev; int lasti; int lastdrop = 0, thisdrop, mindrop; int i, j; shapebits mask; for(i=1, ++b; i<=curWidth1; ++i, ++b, lastlev = thislev) { if(i==curWidth1) thislev = 50; else thislev = lowEmpty[*b]; if(thislev == lastlev) continue; if(thislev < lastlev) { lasti = i; lastdrop = lastlev - thislev; continue; } /* going up */ if(!lastdrop) continue; /* up from a valley */ thisdrop = thislev - lastlev; mindrop = ((lastdrop < thisdrop) ? lastdrop : thisdrop); lastdrop = 0; j = bracket[i-lasti]; if(!j) continue; if(j > mindrop) continue; /* Make sure nothing's hanging into our gap */ /* That means the entire gap is represented on the board */ if(mindrop + lastlev > REPDIAMETER) continue; mask = (1<w; pat = o->under; dymask = (1<= pieceMinMax); if(understate == 0) { ++understate; if(b > b_start) under_l = b-1; } } else if(understate == 1) ++understate, under_r = b; } while(++pat, ++b != b_end); if(understate == 2 && (*b&mask) == mask) return (b-under_r >= pieceMinMax); if(!under_l && !under_r) return true; /* Place the piece, try to place the second piece, * then unplace the first piece. */ b = b_start; pat = o->pattern; do *b |= (*pat<>y) & 2) { o2 = o_l2list; o_end = o_l2list + o_sizes[5]; if(o_end == o2) { rc = false; goto unplace; } } else { o2 = o_l1list; o_end = o_l1list + o_sizes[3]; } do { dy2 = y - o2->y; if(dy2 < min_y) break; b = under_r - o2->x; if(*b & (o2->pattern[0]<pattern[1]<w > 2) { b2_end = b + o2->w; b += 2; pat = o2->pattern + 2; do if(*b & (*pat<w > b_end) { b_mark = 0; pat = o2->pattern + o2->x; qat = o->under + (under_r-b_start); do { mask = (*qat< min_y || o2->maxUnder) && dy2 + o2->h - min_y <= pieceMinMax && dy2 + o2->maxUnder < REPDIAMETER) { #if 1 b_mark = 0; dy2mask = (1<w - o2->x; pat = o2->under + o2->x; ++b, ++pat; do { mask = (*pat<x, dy2, min_y, min_y_bit)) goto nextOrientR; #endif } goto afterright; /* this orientation works! */ nextOrientR: ; } while(++o2 != o_end); rc = false; /* no valid orientations */ goto unplace; } /* right overhang */ afterright: if(under_l) { y = lowEmpty[*under_l]; if((*under_l>>y) & 2) { o2 = o_r2list; o_end = o_r2list + o_sizes[6]; if(o_end == o2) { rc = false; goto unplace; } } else { o2 = o_r1list; o_end = o_r1list + o_sizes[4]; } do { dy2 = y - o2->y; if(dy2 < min_y) break; b = under_l - o2->x; if(*b & (o2->pattern[0]<pattern[1]<w > 2) { b2_end = b + o2->w; b += 2; pat = o2->pattern + 2; do if(*b & (*pat<w < b_start) { b_mark = 0; pat = o2->pattern + o2->x; qat = o->under + (under_l-b_start); do { mask = (*qat<= b_start); if(b_mark && ((*b|(*pat< min_y || o2->maxUnder) && dy2 + o2->h - min_y <= pieceMinMax && dy2 + o2->maxUnder < REPDIAMETER) { #if 1 b_mark = 0; dy2mask = (1<x; pat = o2->under + o2->x; --b, --pat; do { mask = (*pat<= b2_end); if(b_mark && (*b&mask) == mask) { if(b_mark-b < pieceMinMax) goto nextOrientL; goto afterleft; } #else if(!holeTest(b0, o2, under_l-b0-o2->x, dy2, min_y, min_y_bit)) goto nextOrientL; #endif } goto afterleft; /* this orientation works! */ nextOrientL: ; } while(++o2 != o_end); rc = false; /* no valid orientations */ goto unplace; } /* left overhang */ afterleft: unplace: b = b_start; pat = o->pattern; do *b &= ~(*pat< ea) return k; } return k0; } /* backMargin */ static int forMargin(const shapebits *b0, int k) { int ea, eb; int n; int k0 = k; ea = lowEmpty[b0[k-1]]; for(n=0; n<3; ++n, ea=eb, ++k) { eb = lowEmpty[b0[k]]; if(eb > ea) return k; } return k0; } /* forMargin */ static void expandNode(long this_idx, const uchar *base) { int lev = -1; /* placement level */ struct PLACE *p = placeTry - 1; const struct PLACE *q; const struct ORIENT *o; const struct ORIENT *o_start; const struct ORIENT *o_end; const shapebits *pat; shapebits *b; /* pointer to test, place, and unplace */ const shapebits *b_end; int i, j; shapebits mask; shapebits onleft, onright; shapebits thisval; int ly; /* location y coordinate */ int min_y; shapebits min_y_bit; int dy; /* delta y, shift the piece up this much */ int x0; /* b_start - b0 */ int best_x, best_y, best_val; char whichlist, best_whichlist; int reset = -1; char breakLine = pieceMaxDimension/2 + 1; int prevStart, prevEnd; int searchStart, searchEnd, searchPass; bool children = false; bool ambinclude, ambnode; ulong orients[3]; /* bitmap of viable orientations */ /* The primary board, padded on the left and right. */ /* This is where the tiling takes place. */ shapebits b0pad[REPDIAMETER+BOARDWIDTH]; #define b0 (b0pad+REPDIAMETER) shapebits b1[BOARDWIDTH]; struct NODE newnode, compnode, looknode; if(nodesPending < 0) bailout("pending negative %d", nodesDisk - this_idx); if(nodesCache < 0) bailout("nodesCache negative %d", nodesCache); if(!nodesCache && curDepth) bailout("nothing in cache, %d pending", nodesPending); if(checkBits&PERFORMCHECK) { static int pcnt = 0; static long lastDisk = 0; if(++pcnt == 200) { printf("+%d", nodesDisk - lastDisk); lastDisk = nodesDisk; pcnt = 0; } } min_y = 0; min_y_bit = 1; for(j=0; j= BOARDWIDTH) bailout("placement stack overflow", 0); ++p; if(inTerm) exit(0); if(inPause) { char getbuf[12]; fgets(getbuf, 12, stdin); if(getbuf[0] == 'q') exit(0); if(getbuf[0] == 's') checkBits ^= PERFORMCHECK; if(getbuf[0] == 'l') { if(getbuf[1] == '\n') printf("%d", lookahead); if(isdigit(getbuf[1])) lookahead = getbuf[1] - '0'; } if(getbuf[0] == 'r') printf("?%d@%d", curWidth, curDepth); if(getbuf[0] == 'a') { checkBits ^= LOOKALLCHECK; if(checkBits&LOOKALLCHECK) printf("back solutions"); else printf("no back solutions"); } if(getbuf[0] == 'd') printf("%d", curDepth); if(getbuf[0] == 'b') { if(getbuf[1] == '\n') printf("%d", bestOrder); if(isdigit(getbuf[1])) { j = atoi(getbuf+1); if(j > bestOrder && noincrease) { printf("cannot increase the bound\n"); } else { bestOrder = j; setBestRow(); } } } if(getbuf[0] == '?') { for(i=0; i j) j = lookahead; if(min_y > j) goto complete; /* find location to place the piece */ best_x = 0; best_val = O_MAX+1; /* It helps if we look near the last piece placed. */ /* That's most likely to create an unfillable hole. */ if(lev) { q = p - 1; o = o_whichlist[q->whichlist] + q->o; prevStart = q->x - o->x; prevEnd = prevStart + o->w; prevStart = backMargin(b0, prevStart); prevEnd = forMargin(b0, prevEnd); while(q > placeTry && q->choices == 1) { int start, end; --q; o = o_whichlist[q->whichlist] + q->o; start = q->x - o->x; end = start + o->w; start = backMargin(b0, start); end = forMargin(b0, end); if(start < prevStart) prevStart = start; if(end > prevEnd) prevEnd = end; } if(q->choices == 1) prevEnd=curWidth1; } else { prevStart = 1, prevEnd=curWidth1; } for(searchPass=1; searchPass <= 3; ++searchPass) { if(searchPass == 1) { searchStart = prevStart; searchEnd = prevEnd; } if(searchPass == 2) { if(prevEnd == curWidth1) continue; searchStart = prevEnd; searchEnd = curWidth1; } if(searchPass == 3) { if(prevStart == 1) continue; searchStart = 1; searchEnd = prevStart; } for(i=searchStart; i min_y+7) goto nextColumn; if(ly > 12) goto nextColumn; mask = 1<y; /* This is the point where we assume the orientations are sorted */ if(dy < min_y) break; x0 = i - o->x; b = b0 + x0; if(*b & (o->pattern[0]<pattern[1]<w > 2) { b_end = b + o->w; b += 2; pat = o->pattern + 2; do if(*b & (*pat< min_y || o->maxUnder) && dy + o->h - min_y <= pieceMinMax && dy + o->maxUnder < REPDIAMETER) { if(!holeTest(b0, o, x0, dy, min_y, min_y_bit)) goto nextOrient; } /* not to high to run the under tests */ if(wallRestrict && !wallTest(o, x0, dy)) continue; ++j; if(j > 1 && ly > min_y) goto nextColumn; if(j >= best_val) goto nextColumn; setOrientBit(orients, o-o_start); nextOrient: ; } while(++o != o_end); /* loop over orientations */ if(!j) goto backup; best_x = i; best_y = ly; best_val = j; best_whichlist = whichlist; copyOrientBits(p->orients, orients); if(j == 1) goto squareSelected; if(j <= goodEnough && searchPass > 1) goto squareSelected; nextColumn: ; } /* loop across the board */ if(best_val <= goodEnough) goto squareSelected; } /* three search passes */ squareSelected: if(!best_x) { printf("\n"); showPattern(b0); bailout("\nbest_x not selected, min_y = %d", min_y); } p->x = best_x; p->y = best_y; p->choices = best_val; p->whichlist = best_whichlist; p->breakLine = breakLine; p->min_y = min_y; p->o = -1; if(checkBits&NODECHECK) printf("choice %d.%d=%x\n", p->x-1, p->y, p->orients[0]); next: if(++p->o >= o_max) goto backup; if(!testOrientBit(p->orients, p->o)) goto next; o = o_whichlist[p->whichlist] + p->o; /* place piece */ pat = o->pattern; b = b0 + p->x - o->x; b_end = b + o->w; dy = p->y - o->y; do *b |= (*pat<x-1, p->y, p->o); for(j=1; j<=curWidth; ++j) printf("%x", b0[j]); printf("\n"); } /* downgrade breakLine */ j = o->breakLine + p->y; if(j < breakLine) breakLine = j; /* find lowest level */ mask = 0xffff; for(i=curWidth; i; --i) { if(!(b0[i]&min_y_bit)) goto advance; mask &= b0[i]; } min_y = lowEmpty[mask]; min_y_bit = (1 << min_y); goto advance; backup: --lev, --p; if(lev < 0) { /* If this node has no descendants, there's no strong * reason to keep it around in cache. */ if(!children && this_idx) { readNode(this_idx, &compnode); compnode.dead = true; writeNode(this_idx, &compnode); markOldNode(this_idx, compnode.hash); } --nodesPending; return; } /* unplace piece */ unplace: o = o_whichlist[p->whichlist] + p->o; pat = o->pattern; b = b0 + p->x - o->x; b_end = b + o->w; dy = p->y - o->y; do *b &= ~(*pat<= 0) { if(p->y - o->y > reset) goto backup; reset = -1; } breakLine = p->breakLine; if(p->min_y != min_y) { min_y = p->min_y; min_y_bit = (1 << min_y); } goto next; complete: children = true; ambinclude = ambnode = false; reset = breakLine - (pieceMinDimension-1)/2; recomplete: /* build a new instance of the board, with only those pieces * that would be included on the lower side of the breakLine. */ for(j=0; jwhichlist] + q->o; dy = o->breakLine + q->y - breakLine; if(dy > 0) continue; if(dy == 0 && o->ambig && !ambinclude) { ambnode = true; continue; } /* place piece */ pat = o->pattern; b = b1 + q->x - o->x; b_end = b + o->w; dy = q->y - o->y; do *b |= (*pat< 8) bailout("depth difference %d is too high", i); for(j=1; j<=curWidth; ++j) b1[j] >>= i; } newnode.depth = curDepth + i; if(ambnode && !i) { /* did we make the same node again? */ for(j=1; j<=curWidth; ++j) if(b1[j] != base[j]) break; if(j == curWidth1) goto ambtest; } mask = 0; for(j=1; j<=curWidth; ++j) mask |= newnode.pattern[j-1] = b1[j]; for(i=0; mask; ++i, mask>>=1) ; newnode.gap = i; if(i > 8) bailout("gap %d is too high", i); if(i == 0) bailout("zero gap at depth %d", newnode.depth); newnode.dead = false; newnode.parent = this_idx; if(checkBits&NODECHECK) { printf("%d:%d:", newnode.depth, newnode.gap); showSmallPattern(newnode.pattern); printf(" from "); showPattern(b0+1); printf("\n"); } if(!stopstore(newnode)) { if(findNode(&newnode, true, &looknode)) goto ambtest; } else noincrease = true; if(newnode.depth + reachup >= leastRow || checkBits&LOOKALLCHECK) { /* by inserting first, this complement check now tests whether * the node matches itself. */ mask = (1<> (8-newnode.gap)); if(checkBits&NODECHECK) { printf("complement:"); showSmallPattern(compnode.pattern); printf("\n"); } if(findNode(&compnode, false, &looknode)) matchFound(&newnode, &looknode); } else noincrease = true; ambtest: if(ambnode && !ambinclude) { ambnode = false; ambinclude = true; goto recomplete; } goto backup; #undef b0 } /* expandNode */ /* Expand nodes off the floor when floor patterns are provided */ static void expandFloor(void) { int lev = -1; /* placement level */ struct PLACE *p = placeTry - 1; shapebits mask, *o; int i, j, k; shapebits b0[BOARDWIDTH]; shapebits b1[BOARDWIDTH]; struct NODE newnode, looknode; memset(b0, 0, sizeof(b0)); b0[0] = b0[curWidth1] = 0xffff; if(checkBits&NODECHECK) printf("expand floor\n"); advance: if(++lev >= BOARDWIDTH) bailout("placement stack overflow", 0); ++p; /* find location to place the piece */ for(j=1; j<=curWidth; ++j) if(!(b0[j]&1)) break; if(j > curWidth) goto complete; /* definitely testing this square */ p->x = j; p->o = -1; next: if(++p->o >= floor_n) goto backup; o = floorShapes[p->o]; for(k=0; !(o[k]&1); ++k) ; if(k >= j) goto next; for(i=0; o[i]; ++i) if(b0[j-k+i]&o[i]) goto next; for(i=0; o[i]; ++i) b0[j-k+i] |= o[i]; if(checkBits&NODECHECK) printf("place %d.%d=%d\n", p->x-1, 0, p->o); goto advance; backup: --lev, --p; if(lev < 0) { --nodesPending; return; } /* unplace piece */ j = p->x; o = floorShapes[p->o]; for(k=0; !(o[k]&1); ++k) ; for(i=0; o[i]; ++i) b0[j-k+i] &= ~o[i]; goto next; complete: /* compute depth and shift the patttern back down to the floor */ mask = 0xffff; for(j=1; j<=curWidth; ++j) mask &= (b1[j] = b0[j]); i = lowEmpty[mask]; if(i) { for(j=1; j<=curWidth; ++j) b1[j] >>= i; } newnode.depth = i; mask = 0; for(j=1; j<=curWidth; ++j) mask |= newnode.pattern[j-1] = b1[j]; for(i=0; mask; ++i, mask>>=1) ; newnode.gap = i; newnode.dead = false; newnode.parent = 0; if(checkBits&NODECHECK) { printf("%d:%d:", newnode.depth, newnode.gap); showSmallPattern(newnode.pattern); printf("\n"); } findNode(&newnode, true, &looknode); goto backup; } /* expandFloor */ static void expandFirstNode(void) { static struct NODE floor; if(floor_n) { expandFloor(); } else { expandNode(0, floor.pattern); } } /* expandFirstNode */ /* Expand all the nodes in the pending list at the current depth. */ static void expandNodes(void) { long n; /* index of node being expanded */ int i, j; static struct NODE buf; /* node buffer */ workEnd = 0; i = mon_idx; if(restartParent > i) i = restartParent; j = 0; while(i < nodesDisk || j < workEnd) { if(j < workEnd) { n = workList[j++]; printf(">"); } else n = i++; readNode(n, &buf); if(buf.dead) continue; if(buf.depth != curDepth) continue; expandNode(n, buf.pattern); /* Wait a minute - we might have found a better solution. */ /* Can we stop searching? */ if(stopsearch) break; if(bestRow < curWidth && !(checkBits&LOOKALLCHECK)) break; } /* loop over pending nodes */ } /* expandNodes */ /********************************************************************* We found a match. Two nodes complement each other perfectly. Follow both nodes backwards to the floor to build both halves of the tiled rectangle. Then put the two halves together. Dump the solution to a file and return, whence we can look for a better one. *********************************************************************/ static char *leftBoard, *rightBoard; static int better_h, better_area; /* better than our last solution */ static struct PLACE placeSolve[BOARDWIDTH]; static int pno; /* piece number */ /* place pieces between two nodes */ static int betweenNodes(const struct NODE *nb, const struct NODE *nt) { int lev = -1; /* placement level */ struct PLACE *p = placeSolve - 1; struct ORIENT *o; shapebits b[BOARDWIDTH]; int i, j, k; int best_x, best_y, best_val; shapebits mask; ulong orients[3]; /* bitmap of viable orientations */ int diff = nt->depth - nb->depth; if(checkBits&SOLVECHECK) { printf("between %d and %d:", nb->depth, nt->depth); showSmallPattern(nb->pattern); printf(":"); showSmallPattern(nt->pattern); printf("\n"); } b[0] = b[curWidth1] = 0xffff; for(i=0; ipattern[i]; mask ^= 0xffff; mask <<= diff; if(mask & nb->pattern[i]) return 0; mask |= nb->pattern[i]; b[i+1] = mask; } if(checkBits&SOLVECHECK) { showPattern(b+1); printf("\n"); } advance: if(++lev >= BOARDWIDTH) bailout("placement stack overflow", 0); ++p; /* find location to place the piece */ best_x = 0; best_val = O_MAX + 1; for(i=1; i<=curWidth; ++i) { j = lowEmpty[b[i]]; if(j == REPDIAMETER) continue; mask = 1<x = i, p->y = j; /* count orientations */ j = 0; clearOrientBits(orients); o = o_leftlist; for(p->o=0; p->oo, ++o) { if(o->y > p->y) continue; if(p->x <= o->x) continue; if(p->x - o->x + o->w > curWidth1) continue; for(k=0; kw; ++k) if(b[p->x-o->x+k] & (o->pattern[k]<<(p->y-o->y))) break; if(k < o->w) continue; if(++j >= best_val) goto nextColumn; setOrientBit(orients, p->o); } /* loop over orientations */ if(j == best_val) continue; if(!j) goto backup; best_x = p->x, best_y = p->y; best_val = j; copyOrientBits(p->orients, orients); if(j == 1) break; nextColumn: ; } if(!best_x) return lev; p->x = best_x; p->y = best_y; p->o = -1; next: if(++p->o >= o_max) goto backup; if(!testOrientBit(p->orients, p->o)) goto next; o = o_leftlist + p->o; /* place piece */ for(i=0; iw; ++i) b[p->x-o->x+i] |= (o->pattern[i]<<(p->y-o->y)); goto advance; backup: --lev, --p; if(lev < 0) return 0; o = o_leftlist + p->o; /* unplace piece */ for(i=0; iw; ++i) b[p->x-o->x+i] &= ~ (o->pattern[i]<<(p->y-o->y)); goto next; } /* betweenNodes */ /* do the two half boards overlap? */ static bool boardsOverlap(void) { int i; for(i=0; idepth); showSmallPattern(top->pattern); printf("\n"); } n2 = *top; memset(&floor, 0, sizeof(floor)); do { parent = n2.parent; if(parent) { readNode(parent, &n1); } else { n1 = floor; } added = betweenNodes(&n1, &n2); if(!added) { /* try flipping the pattern */ k = curWidth-1; for(j=0; j+jx - 1; int y = p->y; struct ORIENT *o = o_leftlist + p->o; shapebits mask; bool used[26]; memset(used, 0, sizeof(used)); for(i=0; iw; ++i) { mask = o->pattern[i]; k = x - o->x + i; for(j=n1.depth+y-o->y; mask; ++j, mask>>=1) { if(!(mask&1)) continue; if(k && board[j*curWidth+k-1] != '?') used[board[j*curWidth+k-1]-'a'] = true; if(k < curWidth-1 && board[j*curWidth+k+1] != '?') used[board[j*curWidth+k+1]-'a'] = true; if(j && board[(j-1)*curWidth+k] != '?') used[board[(j-1)*curWidth+k]-'a'] = true; if(board[(j+1)*curWidth+k] != '?') used[board[(j+1)*curWidth+k]-'a'] = true; } } /* loop over columns in the piece */ k = pno + 1; do { if(k == 26) k = 0; if(!used[k]) break; } while(++k != pno); if(k == pno) bailout("surrounded by 25 colors", 0); pno = k; for(i=0; iw; ++i) { mask = o->pattern[i]; k = x - o->x + i; for(j=n1.depth+y-o->y; mask; ++j, mask>>=1) { if(!(mask&1)) continue; board[j*curWidth + k] = pno + 'a'; } } /* loop over columns in the piece */ } /* loop over pieces between the nodes */ n2 = n1; } while(parent); /* loop down through the depths */ } /* downToFloor */ static void matchFound(const struct NODE *left, const struct NODE *right) { int newOrder; char solname[40]; int i, fd; better_h = left->depth + right->depth + left->gap; better_area = better_h*curWidth; if(better_h%dimFactor || better_area % (nsq*ordFactor)) bailout("impossible dimensions, height %d", better_h); newOrder = better_area/nsq; if(newOrder > bestOrder) return; printf(" *%d[%dx%d", newOrder, curWidth, better_h); leftBoard = emalloc(better_area); rightBoard = emalloc(better_area); memset(leftBoard, '?', better_area); memset(rightBoard, '?', better_area); pno = 0; downToFloor(leftBoard, left); /* Make it a bit less likely that letters will collide when we put * the two half boards together. */ pno = 13; downToFloor(rightBoard, right); printf("]"); if(boardsOverlap()) { flipBoard(rightBoard); if(boardsOverlap()) bailout("cannot put the two halves of the solution together", 0); } mergeBoards(); sprintf(solname, "dotile/sol%dx%d", curWidth, better_h); fd = open(solname, O_CREAT|O_TRUNC|O_WRONLY, 0666); if(fd < 0) bailout("cannot create solution file %s", (int)solname); for(i=0; iw == o->w && q->h == o->h && !memcmp(q->pattern, o->pattern, o->w*sizeof(shapebits))) { if(o->x + o->y < q->x + q->y || o->x + o->y == q->x + q->y && o->y < q->y) *q = *o; /* structure copy */ continue; } ++n_idx; ++q; if(q != o) *q = *o; /* structure copy */ } o_max = n_idx; o = o_leftlist; for(o_idx=0; o_idxw; ++i) { mask = o->pattern[i]; for(j=0; mask; ++j, mask>>=1) { if(!(mask&1)) continue; if(i == o->x && j == o->y) continue; qori[o_idx][k++] = (j-o->y)*QBWIDTH + i-o->x; } } qori[o_idx][k++] = 0; if(k != nsq) bailout("quad convert found %d squares in a piece", k); } /* loop over orientations */ } /* quadConvert */ static inline bool testQori(int loc, int o) { const short *s = qori[o]; for(; *s; ++s) if(qboard[loc + *s]) return false; return true; } /* testQori */ static inline void placeQori(int loc, int o) { const short *s = qori[o]; for(; *s; ++s) qboard[loc + *s] = true; qboard[loc] = true; } /* placeQori */ static inline void unplaceQori(int loc, int o) { const short *s = qori[o]; for(; *s; ++s) qboard[loc + *s] = false; qboard[loc] = false; } /* unplaceQori */ static void quadAction(int x, int y) { int loc; int o; struct ORIENT *op; while(true) { loc = QBWIDTH*y+x; if(!qboard[loc]) break; --x, ++y; if(x) continue; ++y; x = y; y = 0; if(x == DIAGLIMIT) { puts("ok"); exit(0); } if(x > diagMax) diagMax = x; --x, ++y; } op = o_leftlist; for(o=0; ox || y <= op->y) continue; if(!testQori(loc, o)) continue; placeQori(loc, o); quadAction(x, y); unplaceQori(loc, o); } /* loop over orientations */ } /* quadAction */ static void quadTest(void) { int i; quadConvert(); for(i=0; i= BOARDWIDTH) bailout("placement stack overflow", 0); ++p; /* find location to place the piece */ relook: for(j=0; j= curWidth) { ++min_y, min_y_bit <<= 1; if(min_y < lookahead) goto relook; goto complete; } p->x = j; p->min_y = min_y; p->o = -1; next: if(++p->o >= o_max) goto backup; o = o_leftlist + p->o; dy = min_y-o->y; if(dy < 0) { if(dy+curDepth < 0) goto next; dymask = (1<<-dy) - 1; } k = j - o->x; if(k < 0) goto next; width = o->w; if(k+width > curWidth) width = curWidth - k; pat = o->pattern; for(i=0; iw; ++i) { if(dy >= 0) { if(b0[k+i]&(pat[i]<>-dy)) goto next; } for(i=0; iw; ++i) { if(dy >= 0) b0[k+i] |= (pat[i]<>-dy); } goto advance; backup: --lev, --p; if(lev < 0) return false; /* unplace piece */ min_y = p->min_y; min_y_bit = 1<x; o = o_leftlist + p->o; dy = min_y-o->y; k = j - o->x; pat = o->pattern; for(i=0; iw; ++i) { if(dy >= 0) b0[k+i] &= ~(pat[i]<>-dy); } if(reset && min_y) goto backup; reset = false; goto next; complete: reset = true; /* compute depth and shift the patttern back down to the floor */ memset(b1, 0, curWidth*sizeof(shapebits)); for(q=placeTry; qmin_y) continue; o = o_leftlist + q->o; j = q->x; k = j - o->x; width = o->w; if(k+width > curWidth) width = curWidth - k; pat = o->pattern; for(i=0; i>o->y); } mask = 0xffff; for(j=0; j>= i; mask = 0; for(j=0; j= maxNodes) bailout("too many nodes", 0); *hb = (long)(oenArray + curWidth*nodesCache); memcpy(oenArray + nodesCache*curWidth, b2, curWidth); oenDepth[nodesCache] = newDepth; ++nodesCache; if(checkBits&NODECHECK) { printf("%d=", newDepth); showSmallPattern(b2); printf("\n"); } goto backup; } /* expandOen */ static void oenTest(void) { static uchar base0[BOARDWIDTH]; int i, j; int lastDepth; reversableHash = false; maxNodes = startMega * 1000000; slopNodes = maxNodes / 8 * 9; oenDepth = emalloc(maxNodes*sizeof(ushort)); hashIdx = emalloc(slopNodes*sizeof(long)); for(; curWidth < BOARDWIDTH-pieceMaxDimension; curWidth += dimFactor) { curWidth1 = curWidth + 1; printf("?%d", curWidth); oenArray = emalloc(maxNodes*curWidth); memset(hashIdx, 0, slopNodes*sizeof(long)); nodesCache = 0; lastDepth = 0; curDepth = 0; if(!floor_n) { if(expandOen(base0)) goto ok; } else { for(i=0; i lastDepth) { lastDepth = curDepth; printf(" @%d", curDepth); } if(expandOen(oenArray+j*curWidth)) goto ok; } printf(" :%d failed\n", nodesCache); exit(1); ok: free(oenArray); } free(hashIdx); free(oenDepth); exit(0); } /* oenTest */