char const *p = string;
ret->width = atoi(p);
- while (*p && isdigit(*p)) p++;
+ while (*p && isdigit((unsigned char)*p)) p++;
if (*p == 'x') {
p++;
ret->height = atoi(p);
- while (*p && isdigit(*p)) p++;
+ while (*p && isdigit((unsigned char)*p)) p++;
} else {
ret->height = ret->width;
}
} else if (*p == 'b') {
p++;
ret->barrier_probability = atof(p);
- while (*p && isdigit(*p)) p++;
+ while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
} else if (*p == 'a') {
p++;
ret->unique = FALSE;
- }
+ } else
+ p++; /* skip any other gunk */
}
}
ret[len++] = 'w';
if (full && params->barrier_probability)
len += sprintf(ret+len, "b%g", params->barrier_probability);
- if (!params->unique)
+ if (full && !params->unique)
ret[len++] = 'a';
assert(len < lenof(ret));
ret[len] = '\0';
return "Barrier probability may not be negative";
if (params->barrier_probability > 1)
return "Barrier probability may not be greater than 1";
+
+ /*
+ * Specifying either grid dimension as 2 in a wrapping puzzle
+ * makes it actually impossible to ensure a unique puzzle
+ * solution.
+ *
+ * Proof:
+ *
+ * Without loss of generality, let us assume the puzzle _width_
+ * is 2, so we can conveniently discuss rows without having to
+ * say `rows/columns' all the time. (The height may be 2 as
+ * well, but that doesn't matter.)
+ *
+ * In each row, there are two edges between tiles: the inner
+ * edge (running down the centre of the grid) and the outer
+ * edge (the identified left and right edges of the grid).
+ *
+ * Lemma: In any valid 2xn puzzle there must be at least one
+ * row in which _exactly one_ of the inner edge and outer edge
+ * is connected.
+ *
+ * Proof: No row can have _both_ inner and outer edges
+ * connected, because this would yield a loop. So the only
+ * other way to falsify the lemma is for every row to have
+ * _neither_ the inner nor outer edge connected. But this
+ * means there is no connection at all between the left and
+ * right columns of the puzzle, so there are two disjoint
+ * subgraphs, which is also disallowed. []
+ *
+ * Given such a row, it is always possible to make the
+ * disconnected edge connected and the connected edge
+ * disconnected without changing the state of any other edge.
+ * (This is easily seen by case analysis on the various tiles:
+ * left-pointing and right-pointing endpoints can be exchanged,
+ * likewise T-pieces, and a corner piece can select its
+ * horizontal connectivity independently of its vertical.) This
+ * yields a distinct valid solution.
+ *
+ * Thus, for _every_ row in which exactly one of the inner and
+ * outer edge is connected, there are two valid states for that
+ * row, and hence the total number of solutions of the puzzle
+ * is at least 2^(number of such rows), and in particular is at
+ * least 2 since there must be at least one such row. []
+ */
+ if (params->unique && params->wrapping &&
+ (params->width == 2 || params->height == 2))
+ return "No wrapping puzzle with a width or height of 2 can have"
+ " a unique solution";
+
return NULL;
}
return ret;
}
-static int net_solver(int w, int h, unsigned char *tiles, int wrapping)
+static int net_solver(int w, int h, unsigned char *tiles,
+ unsigned char *barriers, int wrapping)
{
unsigned char *tilestate;
unsigned char *edgestate;
}
/*
+ * If we have barriers available, we can mark those edges as
+ * closed too.
+ */
+ if (barriers) {
+ for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
+ int d;
+ for (d = 1; d <= 8; d += d) {
+ if (barriers[y*w+x] & d) {
+ int x2, y2;
+ /*
+ * In principle the barrier list should already
+ * contain each barrier from each side, but
+ * let's not take chances with our internal
+ * consistency.
+ */
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ edgestate[(y*w+x) * 5 + d] = 2;
+ edgestate[(y2*w+x2) * 5 + F(d)] = 2;
+ }
+ }
+ }
+ }
+
+ /*
* Since most deductions made by this solver are local (the
* exception is loop avoidance, where joining two tiles
* together on one side of the grid can theoretically permit a
* dead ends of size 2 and 3 forms a subnetwork
* with a total area of 6, not 5.)
*/
- if (deadendtotal+1 < area)
+ if (deadendtotal > 0 && deadendtotal+1 < area)
valid = FALSE;
} else if (nnondeadends == 1) {
/*
assert(j > 0); /* we can't lose _all_ possibilities! */
if (j < i) {
- int a, o;
done_something = TRUE;
/*
*/
while (j < 4)
tilestate[(y*w+x) * 4 + j++] = 255;
+ }
- /*
- * Now go through them again and see if we've
- * deduced anything new about any edges.
- */
+ /*
+ * Now go through the tile orientations again and see
+ * if we've deduced anything new about any edges.
+ */
+ {
+ int a, o;
a = 0xF; o = 0;
+
for (i = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) {
a &= tilestate[(y*w+x) * 4 + i];
o |= tilestate[(y*w+x) * 4 + i];
/*
* Run the solver to check unique solubility.
*/
- while (!net_solver(w, h, tiles, params->wrapping)) {
+ while (!net_solver(w, h, tiles, NULL, params->wrapping)) {
int n = 0;
/*
* not yield a complete solution.
*/
ret = dup_game(state);
- net_solver(ret->width, ret->height, ret->tiles, ret->wrapping);
+ net_solver(ret->width, ret->height, ret->tiles,
+ ret->barriers, ret->wrapping);
} else {
assert(aux->width == state->width);
assert(aux->height == state->height);
~mdw / sgt / puzzles / blobdiff