return ret;
}
+/*
+ * Return values: -1 means puzzle was proved inconsistent, 0 means we
+ * failed to narrow down to a unique solution, +1 means we solved it
+ * fully.
+ */
static int net_solver(int w, int h, unsigned char *tiles,
unsigned char *barriers, int wrapping)
{
#endif
}
- assert(j > 0); /* we can't lose _all_ possibilities! */
+ if (j == 0) {
+ /* If we've ruled out all possible orientations for a
+ * tile, then our puzzle has no solution at all. */
+ return -1;
+ }
if (j < i) {
done_something = TRUE;
/*
* Mark all completely determined tiles as locked.
*/
- j = TRUE;
+ j = +1;
for (i = 0; i < w*h; i++) {
if (tilestate[i * 4 + 1] == 255) {
assert(tilestate[i * 4 + 0] != 255);
tiles[i] = tilestate[i * 4] | LOCKED;
} else {
tiles[i] &= ~LOCKED;
- j = FALSE;
+ j = 0;
}
}
/*
* Run the solver to check unique solubility.
*/
- while (!net_solver(w, h, tiles, NULL, params->wrapping)) {
+ while (net_solver(w, h, tiles, NULL, params->wrapping) != 1) {
int n = 0;
/*
* Run the internal solver on the provided grid. This might
* not yield a complete solution.
*/
+ int solver_result;
+
memcpy(tiles, state->tiles, state->width * state->height);
- net_solver(state->width, state->height, tiles,
- state->barriers, state->wrapping);
+ solver_result = net_solver(state->width, state->height, tiles,
+ state->barriers, state->wrapping);
+
+ if (solver_result < 0) {
+ *error = "No solution exists for this puzzle";
+ sfree(tiles);
+ return NULL;
+ }
} else {
for (i = 0; i < state->width * state->height; i++) {
int c = aux[i];
return active;
}
-static int *compute_loops_inner(int w, int h, int wrapping,
- const unsigned char *tiles,
- const unsigned char *barriers)
+struct net_neighbour_ctx {
+ int w, h;
+ const unsigned char *tiles, *barriers;
+ int i, n, neighbours[4];
+};
+static int net_neighbour(int vertex, void *vctx)
{
- int W = w + 1, H = h + 1;
- int *loops, *dsf;
- int x, y;
+ struct net_neighbour_ctx *ctx = (struct net_neighbour_ctx *)vctx;
- /*
- * Construct a dsf covering _vertices_ of the grid, so we have one
- * more in each direction than we do squares.
- */
- dsf = snew_dsf(W*H);
+ if (vertex >= 0) {
+ int x = vertex % ctx->w, y = vertex / ctx->w;
+ int tile, dir, x1, y1, v1;
- /*
- * For each grid square, unify adjacent vertices of that square
- * unless there's a connection separating them. (We only need to
- * check the connection in _this_ square, without bothering to
- * look for one on the other side of the grid line, because the
- * loop will do that anyway when it gets to the other square.)
- *
- * Barriers break loops, so we disallow any connection which
- * terminates in a barrier.
- */
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int t = tiles[y*w+x];
- if (barriers)
- t &= ~barriers[y*w+x];
- if (!(t & L))
- dsf_merge(dsf, y*W+x, (y+1)*W+x);
- if (!(t & R))
- dsf_merge(dsf, y*W+(x+1), (y+1)*W+(x+1));
- if (!(t & U))
- dsf_merge(dsf, y*W+x, y*W+(x+1));
- if (!(t & D))
- dsf_merge(dsf, (y+1)*W+x, (y+1)*W+(x+1));
+ ctx->i = ctx->n = 0;
+
+ tile = ctx->tiles[vertex];
+ if (ctx->barriers)
+ tile &= ~ctx->barriers[vertex];
+
+ for (dir = 1; dir < 0x10; dir <<= 1) {
+ if (!(tile & dir))
+ continue;
+ OFFSETWH(x1, y1, x, y, dir, ctx->w, ctx->h);
+ v1 = y1 * ctx->w + x1;
+ if (ctx->tiles[v1] & F(dir))
+ ctx->neighbours[ctx->n++] = v1;
}
}
- /*
- * If the game is in wrapping mode, unify each edge vertex with
- * its opposite.
- */
- if (wrapping) {
- for (y = 0; y < H; y++)
- dsf_merge(dsf, y*W+0, y*W+w);
- for (x = 0; x < W; x++)
- dsf_merge(dsf, 0*W+x, h*W+x);
- }
+ if (ctx->i < ctx->n)
+ return ctx->neighbours[ctx->i++];
+ else
+ return -1;
+}
+
+static int *compute_loops_inner(int w, int h, int wrapping,
+ const unsigned char *tiles,
+ const unsigned char *barriers)
+{
+ struct net_neighbour_ctx ctx;
+ struct findloopstate *fls;
+ int *loops;
+ int x, y;
+
+ fls = findloop_new_state(w*h);
+ ctx.w = w;
+ ctx.h = h;
+ ctx.tiles = tiles;
+ ctx.barriers = barriers;
+ findloop_run(fls, w*h, net_neighbour, &ctx);
loops = snewn(w*h, int);
- /*
- * Now we've done the loop detection and can read off the output
- * flags trivially: any piece of connection whose two sides are
- * not in the same dsf class is part of a loop.
- */
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
- int t = tiles[y*w+x];
+ int x1, y1, dir;
int flags = 0;
- if ((t & L) && (dsf_canonify(dsf, y*W+x) !=
- dsf_canonify(dsf, (y+1)*W+x)))
- flags |= LLOOP;
- if ((t & R) && (dsf_canonify(dsf, y*W+(x+1)) !=
- dsf_canonify(dsf, (y+1)*W+(x+1))))
- flags |= RLOOP;
- if ((t & U) && (dsf_canonify(dsf, y*W+x) !=
- dsf_canonify(dsf, y*W+(x+1))))
- flags |= ULOOP;
- if ((t & D) && (dsf_canonify(dsf, (y+1)*W+x) !=
- dsf_canonify(dsf, (y+1)*W+(x+1))))
- flags |= DLOOP;
+
+ for (dir = 1; dir < 0x10; dir <<= 1) {
+ if ((tiles[y*w+x] & dir) &&
+ !(barriers && (barriers[y*w+x] & dir))) {
+ OFFSETWH(x1, y1, x, y, dir, w, h);
+ if ((tiles[y1*w+x1] & F(dir)) &&
+ findloop_is_loop_edge(fls, y*w+x, y1*w+x1))
+ flags |= LOOP(dir);
+ }
+ }
loops[y*w+x] = flags;
}
}
- sfree(dsf);
+ findloop_free_state(fls);
return loops;
}
/*
* Check whether the game has been completed.
*
- * For this purpose it doesn't matter where the source square
- * is, because we can start from anywhere and correctly
- * determine whether the game is completed.
+ * For this purpose it doesn't matter where the source square is,
+ * because we can start from anywhere (or, at least, any square
+ * that's non-empty!), and correctly determine whether the game is
+ * completed.
*/
{
- unsigned char *active = compute_active(ret, 0, 0);
- int x1, y1;
+ unsigned char *active;
+ int pos;
int complete = TRUE;
- for (x1 = 0; x1 < ret->width; x1++)
- for (y1 = 0; y1 < ret->height; y1++)
- if ((tile(ret, x1, y1) & 0xF) && !index(ret, active, x1, y1)) {
+ for (pos = 0; pos < ret->width * ret->height; pos++)
+ if (ret->tiles[pos] & 0xF)
+ break;
+
+ if (pos < ret->width * ret->height) {
+ active = compute_active(ret, pos % ret->width, pos / ret->width);
+
+ for (pos = 0; pos < ret->width * ret->height; pos++)
+ if ((ret->tiles[pos] & 0xF) && !active[pos]) {
complete = FALSE;
- goto break_label; /* break out of two loops at once */
- }
- break_label:
+ break;
+ }
- sfree(active);
+ sfree(active);
+ }
if (complete)
ret->completed = TRUE;
* Update the status bar.
*/
{
- char statusbuf[256];
+ char statusbuf[256], *p;
int i, n, n2, a;
+ int complete = FALSE;
+
+ p = statusbuf;
+ *p = '\0'; /* ensure even an empty status string is terminated */
- n = state->width * state->height;
- for (i = a = n2 = 0; i < n; i++) {
- if (active[i])
- a++;
- if (state->tiles[i] & 0xF)
- n2++;
+ if (state->used_solve) {
+ p += sprintf(p, "Auto-solved. ");
+ complete = TRUE;
+ } else if (state->completed) {
+ p += sprintf(p, "COMPLETED! ");
+ complete = TRUE;
}
- sprintf(statusbuf, "%sActive: %d/%d",
- (state->used_solve ? "Auto-solved. " :
- state->completed ? "COMPLETED! " : ""), a, n2);
+ /*
+ * Omit the 'Active: n/N' counter completely if the source
+ * tile is a completely empty one, because then the active
+ * count can't help but read '1'.
+ */
+ if (tile(state, ui->cx, ui->cy) & 0xF) {
+ n = state->width * state->height;
+ for (i = a = n2 = 0; i < n; i++) {
+ if (active[i])
+ a++;
+ if (state->tiles[i] & 0xF)
+ n2++;
+ }
+
+ /*
+ * Also, if we're displaying a completion indicator and
+ * the game is still in its completed state (i.e. every
+ * tile is active), we might as well omit this too.
+ */
+ if (!complete || a < n2)
+ p += sprintf(p, "Active: %d/%d", a, n2);
+ }
status_bar(dr, statusbuf);
}
const struct game thegame = {
"Net", "games.net", "net",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,
~ian / sgt-puzzles.git / blobdiff