+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ int *grid, *numbers = NULL;
+ int x, y, y2, y2last, yx, run, i, nsquares;
+ char *desc, *p;
+ int *enum_rects_scratch;
+ game_params params2real, *params2 = ¶ms2real;
+
+ while (1) {
+ /*
+ * Set up the smaller width and height which we will use to
+ * generate the base grid.
+ */
+ params2->w = params->w / (1.0F + params->expandfactor);
+ if (params2->w < 2 && params->w >= 2) params2->w = 2;
+ params2->h = params->h / (1.0F + params->expandfactor);
+ if (params2->h < 2 && params->h >= 2) params2->h = 2;
+
+ grid = snewn(params2->w * params2->h, int);
+
+ enum_rects_scratch = snewn(2 * params2->w, int);
+
+ nsquares = 0;
+ for (y = 0; y < params2->h; y++)
+ for (x = 0; x < params2->w; x++) {
+ index(params2, grid, x, y) = -1;
+ nsquares++;
+ }
+
+ /*
+ * Place rectangles until we can't any more. We do this by
+ * finding a square we haven't yet covered, and randomly
+ * choosing a rectangle to cover it.
+ */
+
+ while (nsquares > 0) {
+ int square = random_upto(rs, nsquares);
+ int n;
+ struct rect r;
+
+ x = params2->w;
+ y = params2->h;
+ for (y = 0; y < params2->h; y++) {
+ for (x = 0; x < params2->w; x++) {
+ if (index(params2, grid, x, y) == -1 && square-- == 0)
+ break;
+ }
+ if (x < params2->w)
+ break;
+ }
+ assert(x < params2->w && y < params2->h);
+
+ /*
+ * Now see how many rectangles fit around this one.
+ */
+ enum_rects(params2, grid, NULL, &n, x, y, enum_rects_scratch);
+
+ if (!n) {
+ /*
+ * There are no possible rectangles covering this
+ * square, meaning it must be a singleton. Mark it
+ * -2 so we know not to keep trying.
+ */
+ index(params2, grid, x, y) = -2;
+ nsquares--;
+ } else {
+ /*
+ * Pick one at random.
+ */
+ n = random_upto(rs, n);
+ enum_rects(params2, grid, &r, &n, x, y, enum_rects_scratch);
+
+ /*
+ * Place it.
+ */
+ place_rect(params2, grid, r);
+ nsquares -= r.w * r.h;
+ }
+ }
+
+ sfree(enum_rects_scratch);
+
+ /*
+ * Deal with singleton spaces remaining in the grid, one by
+ * one.
+ *
+ * We do this by making a local change to the layout. There are
+ * several possibilities:
+ *
+ * +-----+-----+ Here, we can remove the singleton by
+ * | | | extending the 1x2 rectangle below it
+ * +--+--+-----+ into a 1x3.
+ * | | | |
+ * | +--+ |
+ * | | | |
+ * | | | |
+ * | | | |
+ * +--+--+-----+
+ *
+ * +--+--+--+ Here, that trick doesn't work: there's no
+ * | | | 1 x n rectangle with the singleton at one
+ * | | | end. Instead, we extend a 1 x n rectangle
+ * | | | _out_ from the singleton, shaving a layer
+ * +--+--+ | off the end of another rectangle. So if we
+ * | | | | extended up, we'd make our singleton part
+ * | +--+--+ of a 1x3 and generate a 1x2 where the 2x2
+ * | | | used to be; or we could extend right into
+ * +--+-----+ a 2x1, turning the 1x3 into a 1x2.
+ *
+ * +-----+--+ Here, we can't even do _that_, since any
+ * | | | direction we choose to extend the singleton
+ * +--+--+ | will produce a new singleton as a result of
+ * | | | | truncating one of the size-2 rectangles.
+ * | +--+--+ Fortunately, this case can _only_ occur when
+ * | | | a singleton is surrounded by four size-2s
+ * +--+-----+ in this fashion; so instead we can simply
+ * replace the whole section with a single 3x3.
+ */
+ for (x = 0; x < params2->w; x++) {
+ for (y = 0; y < params2->h; y++) {
+ if (index(params2, grid, x, y) < 0) {
+ int dirs[4], ndirs;
+
+#ifdef GENERATION_DIAGNOSTICS
+ display_grid(params2, grid, NULL, FALSE);
+ printf("singleton at %d,%d\n", x, y);
+#endif
+
+ /*
+ * Check in which directions we can feasibly extend
+ * the singleton. We can extend in a particular
+ * direction iff either:
+ *
+ * - the rectangle on that side of the singleton
+ * is not 2x1, and we are at one end of the edge
+ * of it we are touching
+ *
+ * - it is 2x1 but we are on its short side.
+ *
+ * FIXME: we could plausibly choose between these
+ * based on the sizes of the rectangles they would
+ * create?
+ */
+ ndirs = 0;
+ if (x < params2->w-1) {
+ struct rect r = find_rect(params2, grid, x+1, y);
+ if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
+ dirs[ndirs++] = 1; /* right */
+ }
+ if (y > 0) {
+ struct rect r = find_rect(params2, grid, x, y-1);
+ if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
+ dirs[ndirs++] = 2; /* up */
+ }
+ if (x > 0) {
+ struct rect r = find_rect(params2, grid, x-1, y);
+ if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
+ dirs[ndirs++] = 4; /* left */
+ }
+ if (y < params2->h-1) {
+ struct rect r = find_rect(params2, grid, x, y+1);
+ if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
+ dirs[ndirs++] = 8; /* down */
+ }
+
+ if (ndirs > 0) {
+ int which, dir;
+ struct rect r1, r2;
+
+ which = random_upto(rs, ndirs);
+ dir = dirs[which];
+
+ switch (dir) {
+ case 1: /* right */
+ assert(x < params2->w+1);
+#ifdef GENERATION_DIAGNOSTICS
+ printf("extending right\n");
+#endif
+ r1 = find_rect(params2, grid, x+1, y);
+ r2.x = x;
+ r2.y = y;
+ r2.w = 1 + r1.w;
+ r2.h = 1;
+ if (r1.y == y)
+ r1.y++;
+ r1.h--;
+ break;
+ case 2: /* up */
+ assert(y > 0);
+#ifdef GENERATION_DIAGNOSTICS
+ printf("extending up\n");
+#endif
+ r1 = find_rect(params2, grid, x, y-1);
+ r2.x = x;
+ r2.y = r1.y;
+ r2.w = 1;
+ r2.h = 1 + r1.h;
+ if (r1.x == x)
+ r1.x++;
+ r1.w--;
+ break;
+ case 4: /* left */
+ assert(x > 0);
+#ifdef GENERATION_DIAGNOSTICS
+ printf("extending left\n");
+#endif
+ r1 = find_rect(params2, grid, x-1, y);
+ r2.x = r1.x;
+ r2.y = y;
+ r2.w = 1 + r1.w;
+ r2.h = 1;
+ if (r1.y == y)
+ r1.y++;
+ r1.h--;
+ break;
+ case 8: /* down */
+ assert(y < params2->h+1);
+#ifdef GENERATION_DIAGNOSTICS
+ printf("extending down\n");
+#endif
+ r1 = find_rect(params2, grid, x, y+1);
+ r2.x = x;
+ r2.y = y;
+ r2.w = 1;
+ r2.h = 1 + r1.h;
+ if (r1.x == x)
+ r1.x++;
+ r1.w--;
+ break;
+ }
+ if (r1.h > 0 && r1.w > 0)
+ place_rect(params2, grid, r1);
+ place_rect(params2, grid, r2);
+ } else {
+#ifndef NDEBUG
+ /*
+ * Sanity-check that there really is a 3x3
+ * rectangle surrounding this singleton and it
+ * contains absolutely everything we could
+ * possibly need.
+ */
+ {
+ int xx, yy;
+ assert(x > 0 && x < params2->w-1);
+ assert(y > 0 && y < params2->h-1);
+
+ for (xx = x-1; xx <= x+1; xx++)
+ for (yy = y-1; yy <= y+1; yy++) {
+ struct rect r = find_rect(params2,grid,xx,yy);
+ assert(r.x >= x-1);
+ assert(r.y >= y-1);
+ assert(r.x+r.w-1 <= x+1);
+ assert(r.y+r.h-1 <= y+1);
+ }
+ }
+#endif
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("need the 3x3 trick\n");
+#endif
+
+ /*
+ * FIXME: If the maximum rectangle area for
+ * this grid is less than 9, we ought to
+ * subdivide the 3x3 in some fashion. There are
+ * five other possibilities:
+ *
+ * - a 6 and a 3
+ * - a 4, a 3 and a 2
+ * - three 3s
+ * - a 3 and three 2s (two different arrangements).
+ */
+
+ {
+ struct rect r;
+ r.x = x-1;
+ r.y = y-1;
+ r.w = r.h = 3;
+ place_rect(params2, grid, r);
+ }
+ }
+ }
+ }