+
+ 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]
+ *
+ * A positive or zero value indicates what it sounds as if it
+ * should; -1 indicates that this square _cannot_ be part of
+ * this rectangle; and -2 indicates that it _definitely_ is
+ * (which is distinct from 1, because one might very well know
+ * that _if_ square S is part of rectangle R then it must be
+ * because R is placed in a certain position without knowing
+ * that it definitely _is_).
+ */
+ 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;
+
+ if (overlaps[(i * h + y) * w + x] <= 0) {
+ ret = 0; /* inconsistency */
+ goto cleanup;
+ }
+#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) {
+ if (overlaps[(i * h + yy) * w + xx] <= 0) {
+ ret = 0; /* inconsistency */
+ goto cleanup;
+ }
+#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;
+ }
+