+ int x, y, xx, yy;
+
+#ifdef SOLVER_DIAGNOSTICS
+ printf("ruling out rect %d placement at %d,%d w=%d h=%d\n", rectnum,
+ rectpositions[rectnum].rects[placement].x,
+ rectpositions[rectnum].rects[placement].y,
+ rectpositions[rectnum].rects[placement].w,
+ rectpositions[rectnum].rects[placement].h);
+#endif
+
+ /*
+ * Decrement each entry in the overlaps array to reflect the
+ * removal of this rectangle placement.
+ */
+ for (yy = 0; yy < rectpositions[rectnum].rects[placement].h; yy++) {
+ y = yy + rectpositions[rectnum].rects[placement].y;
+ for (xx = 0; xx < rectpositions[rectnum].rects[placement].w; xx++) {
+ x = xx + rectpositions[rectnum].rects[placement].x;
+
+ assert(overlaps[(rectnum * h + y) * w + x] != 0);
+
+ if (overlaps[(rectnum * h + y) * w + x] > 0)
+ overlaps[(rectnum * h + y) * w + x]--;
+ }
+ }
+
+ /*
+ * Remove the placement from the list of positions for that
+ * rectangle, by interchanging it with the one on the end.
+ */
+ if (placement < rectpositions[rectnum].n - 1) {
+ struct rect t;
+
+ t = rectpositions[rectnum].rects[rectpositions[rectnum].n - 1];
+ rectpositions[rectnum].rects[rectpositions[rectnum].n - 1] =
+ rectpositions[rectnum].rects[placement];
+ rectpositions[rectnum].rects[placement] = t;
+ }
+ rectpositions[rectnum].n--;
+}
+
+static void remove_number_placement(int w, int h, struct numberdata *number,
+ int index, int *rectbyplace)
+{
+ /*
+ * Remove the entry from the rectbyplace array.
+ */
+ rectbyplace[number->points[index].y * w + number->points[index].x] = -1;
+
+ /*
+ * Remove the placement from the list of candidates for that
+ * number, by interchanging it with the one on the end.
+ */
+ if (index < number->npoints - 1) {
+ struct point t;
+
+ t = number->points[number->npoints - 1];
+ number->points[number->npoints - 1] = number->points[index];
+ number->points[index] = t;
+ }
+ number->npoints--;
+}
+
+static int rect_solver(int w, int h, int nrects, struct numberdata *numbers,
+ game_state *result, random_state *rs)
+{
+ struct rectlist *rectpositions;
+ int *overlaps, *rectbyplace, *workspace;
+ int i, ret;
+
+ /*
+ * Start by setting up a list of candidate positions for each
+ * rectangle.
+ */
+ rectpositions = snewn(nrects, struct rectlist);
+ for (i = 0; i < nrects; i++) {
+ int rw, rh, area = numbers[i].area;
+ int j, minx, miny, maxx, maxy;
+ struct rect *rlist;
+ int rlistn, rlistsize;
+
+ /*
+ * For each rectangle, begin by finding the bounding
+ * rectangle of its candidate number placements.
+ */
+ maxx = maxy = -1;
+ minx = w;
+ miny = h;
+ for (j = 0; j < numbers[i].npoints; j++) {
+ if (minx > numbers[i].points[j].x) minx = numbers[i].points[j].x;
+ if (miny > numbers[i].points[j].y) miny = numbers[i].points[j].y;
+ if (maxx < numbers[i].points[j].x) maxx = numbers[i].points[j].x;
+ if (maxy < numbers[i].points[j].y) maxy = numbers[i].points[j].y;
+ }
+
+ /*
+ * Now loop over all possible rectangle placements
+ * overlapping a point within that bounding rectangle;
+ * ensure each one actually contains a candidate number
+ * placement, and add it to the list.
+ */
+ rlist = NULL;
+ rlistn = rlistsize = 0;
+
+ for (rw = 1; rw <= area && rw <= w; rw++) {
+ int x, y;
+
+ if (area % rw)
+ continue;
+ rh = area / rw;
+ if (rh > h)
+ continue;
+
+ for (y = miny - rh + 1; y <= maxy; y++) {
+ if (y < 0 || y+rh > h)
+ continue;
+
+ for (x = minx - rw + 1; x <= maxx; x++) {
+ if (x < 0 || x+rw > w)
+ continue;
+
+ /*
+ * See if we can find a candidate number
+ * placement within this rectangle.
+ */
+ for (j = 0; j < numbers[i].npoints; j++)
+ if (numbers[i].points[j].x >= x &&
+ numbers[i].points[j].x < x+rw &&
+ numbers[i].points[j].y >= y &&
+ numbers[i].points[j].y < y+rh)
+ break;
+
+ if (j < numbers[i].npoints) {
+ /*
+ * Add this to the list of candidate
+ * placements for this rectangle.
+ */
+ if (rlistn >= rlistsize) {
+ rlistsize = rlistn + 32;
+ rlist = sresize(rlist, rlistsize, struct rect);
+ }
+ rlist[rlistn].x = x;
+ rlist[rlistn].y = y;
+ rlist[rlistn].w = rw;
+ rlist[rlistn].h = rh;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("rect %d [area %d]: candidate position at"
+ " %d,%d w=%d h=%d\n",
+ i, area, x, y, rw, rh);
+#endif
+ rlistn++;
+ }
+ }
+ }
+ }
+
+ rectpositions[i].rects = rlist;
+ rectpositions[i].n = rlistn;
+ }
+
+ /*
+ * Next, construct a multidimensional array tracking how many
+ * candidate positions for each rectangle overlap each square.
+ *
+ * Indexing of this array is by the formula
+ *
+ * overlaps[(rectindex * h + y) * w + x]
+ */
+ overlaps = snewn(nrects * w * h, int);
+ memset(overlaps, 0, nrects * w * h * sizeof(int));
+ for (i = 0; i < nrects; i++) {
+ int j;
+
+ for (j = 0; j < rectpositions[i].n; j++) {
+ int xx, yy;
+
+ for (yy = 0; yy < rectpositions[i].rects[j].h; yy++)
+ for (xx = 0; xx < rectpositions[i].rects[j].w; xx++)
+ overlaps[(i * h + yy+rectpositions[i].rects[j].y) * w +
+ xx+rectpositions[i].rects[j].x]++;
+ }
+ }
+
+ /*
+ * Also we want an array covering the grid once, to make it
+ * easy to figure out which squares are candidate number
+ * placements for which rectangles. (The existence of this
+ * single array assumes that no square starts off as a
+ * candidate number placement for more than one rectangle. This
+ * assumption is justified, because this solver is _either_
+ * used to solve real problems - in which case there is a
+ * single placement for every number - _or_ used to decide on
+ * number placements for a new puzzle, in which case each
+ * number's placements are confined to the intended position of
+ * the rectangle containing that number.)
+ */
+ rectbyplace = snewn(w * h, int);
+ for (i = 0; i < w*h; i++)
+ rectbyplace[i] = -1;
+
+ for (i = 0; i < nrects; i++) {
+ int j;
+
+ for (j = 0; j < numbers[i].npoints; j++) {
+ int x = numbers[i].points[j].x;
+ int y = numbers[i].points[j].y;
+
+ assert(rectbyplace[y * w + x] == -1);
+ rectbyplace[y * w + x] = i;
+ }
+ }
+
+ workspace = snewn(nrects, int);
+
+ /*
+ * Now run the actual deduction loop.
+ */
+ while (1) {
+ int done_something = FALSE;
+
+#ifdef SOLVER_DIAGNOSTICS
+ printf("starting deduction loop\n");
+
+ for (i = 0; i < nrects; i++) {
+ printf("rect %d overlaps:\n", i);
+ {
+ int x, y;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printf("%3d", overlaps[(i * h + y) * w + x]);
+ }
+ printf("\n");
+ }
+ }
+ }
+ printf("rectbyplace:\n");
+ {
+ int x, y;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printf("%3d", rectbyplace[y * w + x]);
+ }
+ printf("\n");
+ }
+ }
+#endif
+
+ /*
+ * Housekeeping. Look for rectangles whose number has only
+ * one candidate position left, and mark that square as
+ * known if it isn't already.
+ */
+ for (i = 0; i < nrects; i++) {
+ if (numbers[i].npoints == 1) {
+ int x = numbers[i].points[0].x;
+ int y = numbers[i].points[0].y;
+ if (overlaps[(i * h + y) * w + x] >= -1) {
+ int j;
+
+ assert(overlaps[(i * h + y) * w + x] > 0);
+#ifdef SOLVER_DIAGNOSTICS
+ printf("marking %d,%d as known for rect %d"
+ " (sole remaining number position)\n", x, y, i);
+#endif
+
+ for (j = 0; j < nrects; j++)
+ overlaps[(j * h + y) * w + x] = -1;
+
+ overlaps[(i * h + y) * w + x] = -2;
+ }
+ }
+ }
+
+ /*
+ * Now look at the intersection of all possible placements
+ * for each rectangle, and mark all squares in that
+ * intersection as known for that rectangle if they aren't
+ * already.
+ */
+ for (i = 0; i < nrects; i++) {
+ int minx, miny, maxx, maxy, xx, yy, j;
+
+ minx = miny = 0;
+ maxx = w;
+ maxy = h;
+
+ for (j = 0; j < rectpositions[i].n; j++) {
+ int x = rectpositions[i].rects[j].x;
+ int y = rectpositions[i].rects[j].y;
+ int w = rectpositions[i].rects[j].w;
+ int h = rectpositions[i].rects[j].h;
+
+ if (minx < x) minx = x;
+ if (miny < y) miny = y;
+ if (maxx > x+w) maxx = x+w;
+ if (maxy > y+h) maxy = y+h;
+ }
+
+ for (yy = miny; yy < maxy; yy++)
+ for (xx = minx; xx < maxx; xx++)
+ if (overlaps[(i * h + yy) * w + xx] >= -1) {
+ assert(overlaps[(i * h + yy) * w + xx] > 0);
+#ifdef SOLVER_DIAGNOSTICS
+ printf("marking %d,%d as known for rect %d"
+ " (intersection of all placements)\n",
+ xx, yy, i);
+#endif
+
+ for (j = 0; j < nrects; j++)
+ overlaps[(j * h + yy) * w + xx] = -1;
+
+ overlaps[(i * h + yy) * w + xx] = -2;
+ }
+ }
+
+ /*
+ * Rectangle-focused deduction. Look at each rectangle in
+ * turn and try to rule out some of its candidate
+ * placements.
+ */
+ for (i = 0; i < nrects; i++) {
+ int j;
+
+ for (j = 0; j < rectpositions[i].n; j++) {
+ int xx, yy, k;
+ int del = FALSE;
+
+ for (k = 0; k < nrects; k++)
+ workspace[k] = 0;
+
+ for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) {
+ int y = yy + rectpositions[i].rects[j].y;
+ for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) {
+ int x = xx + rectpositions[i].rects[j].x;
+
+ if (overlaps[(i * h + y) * w + x] == -1) {
+ /*
+ * This placement overlaps a square
+ * which is _known_ to be part of
+ * another rectangle. Therefore we must
+ * rule it out.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("rect %d placement at %d,%d w=%d h=%d "
+ "contains %d,%d which is known-other\n", i,
+ rectpositions[i].rects[j].x,
+ rectpositions[i].rects[j].y,
+ rectpositions[i].rects[j].w,
+ rectpositions[i].rects[j].h,
+ x, y);
+#endif
+ del = TRUE;
+ }
+
+ if (rectbyplace[y * w + x] != -1) {
+ /*
+ * This placement overlaps one of the
+ * candidate number placements for some
+ * rectangle. Count it.
+ */
+ workspace[rectbyplace[y * w + x]]++;
+ }
+ }
+ }
+
+ if (!del) {
+ /*
+ * If we haven't ruled this placement out
+ * already, see if it overlaps _all_ of the
+ * candidate number placements for any
+ * rectangle. If so, we can rule it out.
+ */
+ for (k = 0; k < nrects; k++)
+ if (k != i && workspace[k] == numbers[k].npoints) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("rect %d placement at %d,%d w=%d h=%d "
+ "contains all number points for rect %d\n",
+ i,
+ rectpositions[i].rects[j].x,
+ rectpositions[i].rects[j].y,
+ rectpositions[i].rects[j].w,
+ rectpositions[i].rects[j].h,
+ k);
+#endif
+ del = TRUE;
+ break;
+ }
+
+ /*
+ * Failing that, see if it overlaps at least
+ * one of the candidate number placements for
+ * itself! (This might not be the case if one
+ * of those number placements has been removed
+ * recently.).
+ */
+ if (!del && workspace[i] == 0) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("rect %d placement at %d,%d w=%d h=%d "
+ "contains none of its own number points\n",
+ i,
+ rectpositions[i].rects[j].x,
+ rectpositions[i].rects[j].y,
+ rectpositions[i].rects[j].w,
+ rectpositions[i].rects[j].h);
+#endif
+ del = TRUE;
+ }
+ }
+
+ if (del) {
+ remove_rect_placement(w, h, rectpositions, overlaps, i, j);
+
+ j--; /* don't skip over next placement */
+
+ done_something = TRUE;
+ }
+ }
+ }
+
+ /*
+ * Square-focused deduction. Look at each square not marked
+ * as known, and see if there are any which can only be
+ * part of a single rectangle.
+ */
+ {
+ int x, y, n, index;
+ for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
+ /* Known squares are marked as <0 everywhere, so we only need
+ * to check the overlaps entry for rect 0. */
+ if (overlaps[y * w + x] < 0)
+ continue; /* known already */
+
+ n = 0;
+ index = -1;
+ for (i = 0; i < nrects; i++)
+ if (overlaps[(i * h + y) * w + x] > 0)
+ n++, index = i;
+
+ if (n == 1) {
+ int j;
+
+ /*
+ * Now we can rule out all placements for
+ * rectangle `index' which _don't_ contain
+ * square x,y.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("square %d,%d can only be in rectangle %d\n",
+ x, y, index);
+#endif
+ for (j = 0; j < rectpositions[index].n; j++) {
+ struct rect *r = &rectpositions[index].rects[j];
+ if (x >= r->x && x < r->x + r->w &&
+ y >= r->y && y < r->y + r->h)
+ continue; /* this one is OK */
+ remove_rect_placement(w, h, rectpositions, overlaps,
+ index, j);
+ j--; /* don't skip over next placement */
+ done_something = TRUE;
+ }
+ }
+ }
+ }
+
+ /*
+ * If we've managed to deduce anything by normal means,
+ * loop round again and see if there's more to be done.
+ * Only if normal deduction has completely failed us should
+ * we now move on to narrowing down the possible number
+ * placements.
+ */
+ if (done_something)
+ continue;
+
+ /*
+ * Now we have done everything we can with the current set
+ * of number placements. So we need to winnow the number
+ * placements so as to narrow down the possibilities. We do
+ * this by searching for a candidate placement (of _any_
+ * rectangle) which overlaps a candidate placement of the
+ * number for some other rectangle.
+ */
+ if (rs) {
+ struct rpn {
+ int rect;
+ int placement;
+ int number;
+ } *rpns = NULL;
+ size_t nrpns = 0, rpnsize = 0;
+ int j;
+
+ for (i = 0; i < nrects; i++) {
+ for (j = 0; j < rectpositions[i].n; j++) {
+ int xx, yy;
+
+ for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) {
+ int y = yy + rectpositions[i].rects[j].y;
+ for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) {
+ int x = xx + rectpositions[i].rects[j].x;
+
+ if (rectbyplace[y * w + x] >= 0 &&
+ rectbyplace[y * w + x] != i) {
+ /*
+ * Add this to the list of
+ * winnowing possibilities.
+ */
+ if (nrpns >= rpnsize) {
+ rpnsize = rpnsize * 3 / 2 + 32;
+ rpns = sresize(rpns, rpnsize, struct rpn);
+ }
+ rpns[nrpns].rect = i;
+ rpns[nrpns].placement = j;
+ rpns[nrpns].number = rectbyplace[y * w + x];
+ nrpns++;
+ }
+ }
+ }
+
+ }
+ }
+
+#ifdef SOLVER_DIAGNOSTICS
+ printf("%d candidate rect placements we could eliminate\n", nrpns);
+#endif
+ if (nrpns > 0) {
+ /*
+ * Now choose one of these unwanted rectangle
+ * placements, and eliminate it.
+ */
+ int index = random_upto(rs, nrpns);
+ int k, m;
+ struct rpn rpn = rpns[index];
+ struct rect r;
+ sfree(rpns);
+
+ i = rpn.rect;
+ j = rpn.placement;
+ k = rpn.number;
+ r = rectpositions[i].rects[j];
+
+ /*
+ * We rule out placement j of rectangle i by means
+ * of removing all of rectangle k's candidate
+ * number placements which do _not_ overlap it.
+ * This will ensure that it is eliminated during
+ * the next pass of rectangle-focused deduction.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("ensuring number for rect %d is within"
+ " rect %d's placement at %d,%d w=%d h=%d\n",
+ k, i, r.x, r.y, r.w, r.h);
+#endif
+
+ for (m = 0; m < numbers[k].npoints; m++) {
+ int x = numbers[k].points[m].x;
+ int y = numbers[k].points[m].y;
+
+ if (x < r.x || x >= r.x + r.w ||
+ y < r.y || y >= r.y + r.h) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("eliminating number for rect %d at %d,%d\n",
+ k, x, y);
+#endif
+ remove_number_placement(w, h, &numbers[k],
+ m, rectbyplace);
+ m--; /* don't skip the next one */
+ done_something = TRUE;
+ }
+ }
+ }
+ }
+
+ if (!done_something) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("terminating deduction loop\n");
+#endif
+ break;
+ }
+ }
+
+ ret = TRUE;
+ for (i = 0; i < nrects; i++) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("rect %d has %d possible placements\n",
+ i, rectpositions[i].n);
+#endif
+ assert(rectpositions[i].n > 0);
+ if (rectpositions[i].n > 1) {
+ ret = FALSE;
+ } else if (result) {
+ /*
+ * Place the rectangle in its only possible position.
+ */
+ int x, y;
+ struct rect *r = &rectpositions[i].rects[0];
+
+ for (y = 0; y < r->h; y++) {
+ if (r->x > 0)
+ vedge(result, r->x, r->y+y) = 1;
+ if (r->x+r->w < result->w)
+ vedge(result, r->x+r->w, r->y+y) = 1;
+ }
+ for (x = 0; x < r->w; x++) {
+ if (r->y > 0)
+ hedge(result, r->x+x, r->y) = 1;
+ if (r->y+r->h < result->h)
+ hedge(result, r->x+x, r->y+r->h) = 1;
+ }
+ }
+ }
+
+ /*
+ * Free up all allocated storage.
+ */
+ sfree(workspace);
+ sfree(rectbyplace);
+ sfree(overlaps);
+ for (i = 0; i < nrects; i++)
+ sfree(rectpositions[i].rects);
+ sfree(rectpositions);
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Grid generation code.
+ */
+
+/*
+ * This function does one of two things. If passed r==NULL, it
+ * counts the number of possible rectangles which cover the given
+ * square, and returns it in *n. If passed r!=NULL then it _reads_
+ * *n to find an index, counts the possible rectangles until it
+ * reaches the nth, and writes it into r.
+ *
+ * `scratch' is expected to point to an array of 2 * params->w
+ * ints, used internally as scratch space (and passed in like this
+ * to avoid re-allocating and re-freeing it every time round a
+ * tight loop).
+ */
+static void enum_rects(game_params *params, int *grid, struct rect *r, int *n,
+ int sx, int sy, int *scratch)
+{
+ int rw, rh, mw, mh;
+ int x, y, dx, dy;
+ int maxarea, realmaxarea;
+ int index = 0;
+ int *top, *bottom;