static int is_solved(const game_params *params, clue *clues,
borderflag *border)
{
- int wh = params->w * params->h, k = params->k, *dsf = snew_dsf(wh), i;
+ int w = params->w, h = params->h, wh = w*h, k = params->k;
+ int i, x, y;
+ int *dsf = snew_dsf(wh);
assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */
+ /*
+ * A game is solved if:
+ *
+ * - the borders drawn on the grid divide it into connected
+ * components such that every square is in a component of the
+ * correct size
+ * - the borders also satisfy the clue set
+ */
for (i = 0; i < wh; ++i) {
if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE);
if (dsf_size(dsf, i) != k) goto error;
if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error;
}
+ /*
+ * ... and thirdly:
+ *
+ * - there are no *stray* borders, in that every border is
+ * actually part of the division between two components.
+ * Otherwise you could cheat by finding a subdivision which did
+ * not *exceed* any clue square's counter, and then adding a
+ * few extra edges.
+ */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (x+1 < w && (border[y*w+x] & BORDER_R) &&
+ dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1)))
+ goto error;
+ if (y+1 < h && (border[y*w+x] & BORDER_D) &&
+ dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x))
+ goto error;
+ }
+ }
+
sfree(dsf);
return TRUE;
int w = params->w, h = params->h, wh = w*h, squares = 0;
for (/* nop */; *desc; ++desc) {
- if (islower(*desc)) {
+ if (islower((unsigned char)*desc)) {
squares += *desc - 'a' + 1;
- } else if (isdigit(*desc)) {
+ } else if (isdigit((unsigned char)*desc)) {
if (*desc > '4') {
static char buf[] = "Invalid (too large) number: '5'";
- assert (isdigit(buf[lenof(buf) - 3]));
+ assert (isdigit((unsigned char)buf[lenof(buf) - 3]));
buf[lenof(buf) - 3] = *desc; /* ... or 6, 7, 8, 9 :-) */
return buf;
}
++squares;
- } else if (isprint(*desc)) {
+ } else if (isprint((unsigned char)*desc)) {
static char buf[] = "Invalid character in data: '?'";
buf[lenof(buf) - 3] = *desc;
return buf;
setmem(state->shared->clues, EMPTY, wh);
for (i = 0; *desc; ++desc) {
- if (isdigit(*desc)) state->shared->clues[i++] = *desc - '0';
- else if (isalpha(*desc)) i += *desc - 'a' + 1;
+ if (isdigit((unsigned char)*desc)) state->shared->clues[i++] = *desc - '0';
+ else if (isalpha((unsigned char)*desc)) i += *desc - 'a' + 1;
}
snewa(state->borders, wh);
const struct game thegame = {
"Palisade", "games.palisade", "palisade",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,