*/
#define DIFFLIST(A) \
A(EASY,Easy,e) \
- A(NORMAL,Normal,n)
+ A(NORMAL,Normal,n) \
+ A(RECURSE,Unreasonable,u)
#define ENUM(upper,title,lower) DIFF_ ## upper,
#define TITLE(upper,title,lower) #title,
#define ENCODE(upper,title,lower) #lower
int *graph;
int n;
int ngraph;
+ int depth;
};
static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
sc->n = n;
sc->ngraph = ngraph;
sc->possible = snewn(n, unsigned char);
+ sc->depth = 0;
return sc;
}
}
/*
- * We've run out of things to deduce. See if we've got the lot.
+ * See if we've got a complete solution, and return if so.
*/
for (i = 0; i < n; i++)
if (colouring[i] < 0)
- return 2;
+ break;
+ if (i == n)
+ return 1; /* success! */
- return 1; /* success! */
+ /*
+ * If recursion is not permissible, we now give up.
+ */
+ if (difficulty < DIFF_RECURSE)
+ return 2; /* unable to complete */
+
+ /*
+ * Now we've got to do something recursive. So first hunt for a
+ * currently-most-constrained region.
+ */
+ {
+ int best, bestc;
+ struct solver_scratch *rsc;
+ int *subcolouring, *origcolouring;
+ int ret, subret;
+ int we_already_got_one;
+
+ best = -1;
+ bestc = FIVE;
+
+ for (i = 0; i < n; i++) if (colouring[i] < 0) {
+ int p = sc->possible[i];
+ enum { compile_time_assertion = 1 / (FOUR <= 4) };
+ int c;
+
+ /* Count the set bits. */
+ c = (p & 5) + ((p >> 1) & 5);
+ c = (c & 3) + ((c >> 2) & 3);
+ assert(c > 1); /* or colouring[i] would be >= 0 */
+
+ if (c < bestc) {
+ best = i;
+ bestc = c;
+ }
+ }
+
+ assert(best >= 0); /* or we'd be solved already */
+
+ /*
+ * Now iterate over the possible colours for this region.
+ */
+ rsc = new_scratch(graph, n, ngraph);
+ rsc->depth = sc->depth + 1;
+ origcolouring = snewn(n, int);
+ memcpy(origcolouring, colouring, n * sizeof(int));
+ subcolouring = snewn(n, int);
+ we_already_got_one = FALSE;
+ ret = 0;
+
+ for (i = 0; i < FOUR; i++) {
+ if (!(sc->possible[best] & (1 << i)))
+ continue;
+
+ memcpy(subcolouring, origcolouring, n * sizeof(int));
+ subcolouring[best] = i;
+ subret = map_solver(rsc, graph, n, ngraph,
+ subcolouring, difficulty);
+
+ /*
+ * If this possibility turned up more than one valid
+ * solution, or if it turned up one and we already had
+ * one, we're definitely ambiguous.
+ */
+ if (subret == 2 || (subret == 1 && we_already_got_one)) {
+ ret = 2;
+ break;
+ }
+
+ /*
+ * If this possibility turned up one valid solution and
+ * it's the first we've seen, copy it into the output.
+ */
+ if (subret == 1) {
+ memcpy(colouring, subcolouring, n * sizeof(int));
+ we_already_got_one = TRUE;
+ ret = 1;
+ }
+
+ /*
+ * Otherwise, this guess led to a contradiction, so we
+ * do nothing.
+ */
+ }
+
+ sfree(subcolouring);
+ free_scratch(rsc);
+
+ return ret;
+ }
}
/* ----------------------------------------------------------------------
* Finally, check that the puzzle is _at least_ as hard as
* required, and indeed that it isn't already solved.
* (Calling map_solver with negative difficulty ensures the
- * latter - if a solver which _does nothing_ can't solve
- * it, it's too easy!)
+ * latter - if a solver which _does nothing_ can solve it,
+ * it's too easy!)
*/
memcpy(colouring2, colouring, n*sizeof(int));
if (map_solver(sc, graph, n, ngraph, colouring2,
/*
* Drop minimum difficulty if necessary.
*/
- if (mindiff > 0 && (n < 9 || n > 3*wh/2)) {
+ if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
if (tries-- <= 0)
mindiff = 0; /* give up and go for Easy */
}
for (y = 0; y < h; y++)
for (x = 0; x < w; x++) {
- int ex[3], ey[3], ea[3], eb[3], en = 0;
+ int ex[4], ey[4], ea[4], eb[4], en = 0;
/*
* Look for an edge to the right of this
* square, an edge below it, and an edge in the
- * middle of it.
+ * middle of it. Also look to see if the point
+ * at the bottom right of this square is on an
+ * edge (and isn't a place where more than two
+ * regions meet).
*/
if (x+1 < w) {
/* right edge */
ey[en] = y*2+1;
en++;
}
+ if (x+1 < w && y+1 < h) {
+ /* bottom right corner */
+ int oct[8], othercol, nchanges;
+ oct[0] = state->map->map[RE * wh + y*w+x];
+ oct[1] = state->map->map[LE * wh + y*w+(x+1)];
+ oct[2] = state->map->map[BE * wh + y*w+(x+1)];
+ oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
+ oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
+ oct[5] = state->map->map[RE * wh + (y+1)*w+x];
+ oct[6] = state->map->map[TE * wh + (y+1)*w+x];
+ oct[7] = state->map->map[BE * wh + y*w+x];
+
+ othercol = -1;
+ nchanges = 0;
+ for (i = 0; i < 8; i++) {
+ if (oct[i] != oct[0]) {
+ if (othercol < 0)
+ othercol = oct[i];
+ else if (othercol != oct[i])
+ break; /* three colours at this point */
+ }
+ if (oct[i] != oct[(i+1) & 7])
+ nchanges++;
+ }
+
+ /*
+ * Now if there are exactly two regions at
+ * this point (not one, and not three or
+ * more), and only two changes around the
+ * loop, then this is a valid place to put
+ * an error marker.
+ */
+ if (i == 8 && othercol >= 0 && nchanges == 2) {
+ ea[en] = oct[0];
+ eb[en] = othercol;
+ ex[en] = (x+1)*2;
+ ey[en] = (y+1)*2;
+ en++;
+ }
+ }
/*
* Now process the edges we've found, one by
};
/* Flags in `drawn'. */
-#define ERR_T 0x0100
-#define ERR_B 0x0200
-#define ERR_L 0x0400
-#define ERR_R 0x0800
-#define ERR_C 0x1000
-#define ERR_MASK 0x1F00
+#define ERR_BASE 0x0080
+#define ERR_MASK 0xFF80
#define TILESIZE (ds->tilesize)
#define BORDER (TILESIZE)
*/
xext = TILESIZE/16;
yext = TILESIZE*2/5 - (xext*2+2);
- draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3+1),
+ draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
COL_ERRTEXT);
- draw_rect(dr, x-xext, y+yext-xext*2, xext*2+1, xext*2+1, COL_ERRTEXT);
+ draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
}
static void draw_square(drawing *dr, game_drawstate *ds,
int x, int y, int v)
{
int w = params->w, h = params->h, wh = w*h;
- int tv, bv, errs;
+ int tv, bv, xo, yo, errs;
errs = v & ERR_MASK;
v &= ~ERR_MASK;
/*
* Draw error markers.
*/
- if (errs & ERR_T)
- draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y));
- if (errs & ERR_L)
- draw_error(dr, ds, COORD(x), COORD(y)+TILESIZE/2);
- if (errs & ERR_B)
- draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y+1));
- if (errs & ERR_R)
- draw_error(dr, ds, COORD(x+1), COORD(y)+TILESIZE/2);
- if (errs & ERR_C)
- draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y)+TILESIZE/2);
+ for (yo = 0; yo < 3; yo++)
+ for (xo = 0; xo < 3; xo++)
+ if (errs & (ERR_BASE << (yo*3+xo)))
+ draw_error(dr, ds,
+ (COORD(x)*2+TILESIZE*xo)/2,
+ (COORD(y)*2+TILESIZE*yo)/2);
unclip(dr);
for (i = 0; i < state->map->ngraph; i++) {
int v1 = state->map->graph[i] / n;
int v2 = state->map->graph[i] % n;
+ int xo, yo;
if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
continue;
x = state->map->edgex[i];
y = state->map->edgey[i];
- if (x % 2 && y % 2) {
- ds->todraw[(y/2)*w+(x/2)] |= ERR_C;
- } else if (x % 2) {
- ds->todraw[(y/2-1)*w+(x/2)] |= ERR_B;
- ds->todraw[(y/2)*w+(x/2)] |= ERR_T;
- } else {
- assert(y % 2);
- ds->todraw[(y/2)*w+(x/2-1)] |= ERR_R;
- ds->todraw[(y/2)*w+(x/2)] |= ERR_L;
+ xo = x % 2; x /= 2;
+ yo = y % 2; y /= 2;
+
+ ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
+ if (xo == 0) {
+ assert(x > 0);
+ ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
+ }
+ if (yo == 0) {
+ assert(y > 0);
+ ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
+ }
+ if (xo == 0 && yo == 0) {
+ assert(x > 0 && y > 0);
+ ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
}
}