X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/c0edd11f62b378695f9fbddbc4da8e0dd18c9ee6..6e8e5c5141cf8f754a1b468eb53ea91e494f97f7:/net.c diff --git a/net.c b/net.c index da9e54c..db8c3c4 100644 --- a/net.c +++ b/net.c @@ -201,11 +201,11 @@ static void decode_params(game_params *ret, char const *string) 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; } @@ -217,11 +217,12 @@ static void decode_params(game_params *ret, char const *string) } 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 */ } } @@ -235,7 +236,7 @@ static char *encode_params(game_params *params, int full) 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'; @@ -313,6 +314,55 @@ static char *validate_params(game_params *params) 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; } @@ -414,7 +464,8 @@ static int todo_get(struct todo *todo) { 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; @@ -522,6 +573,30 @@ static int net_solver(int w, int h, unsigned char *tiles, int wrapping) } /* + * 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 @@ -631,7 +706,7 @@ static int net_solver(int w, int h, unsigned char *tiles, int wrapping) * 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) { /* @@ -668,7 +743,6 @@ static int net_solver(int w, int h, unsigned char *tiles, int wrapping) assert(j > 0); /* we can't lose _all_ possibilities! */ if (j < i) { - int a, o; done_something = TRUE; /* @@ -677,12 +751,16 @@ static int net_solver(int w, int h, unsigned char *tiles, int wrapping) */ 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]; @@ -1263,7 +1341,7 @@ static char *new_game_desc(game_params *params, random_state *rs, /* * 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; /* @@ -1640,7 +1718,8 @@ static game_state *solve_game(game_state *state, game_aux_info *aux, * 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);